Last active
June 10, 2017 16:46
-
-
Save YashasSamaga/ef16a4bc2979ac14be371b4b5bbb832b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
using namespace std; | |
int cases, note_count, required_money; | |
//cases - no of cases | |
//note_count - no of notes | |
//required money - money asked by the monster | |
vector<int> notes(20); //stores the values of the notes (there can be at most 20 notes; so let's reserve space for them - insignificant optimization) | |
bool issubset(int spos, int current_notes) | |
{ | |
for (int i = spos; i >= 0; i--) | |
{ | |
if (notes[i] + current_notes > required_money) continue; | |
int new_current_notes = current_notes + notes[i]; | |
if (new_current_notes == required_money) return true; | |
if (issubset(i - 1, new_current_notes)) return true; | |
} | |
return false; | |
} | |
int main() | |
{ | |
cin >> cases; | |
while (cases--) | |
{ | |
bool success = false; | |
cin >> note_count >> required_money; | |
notes.clear(); //empty the notes vector | |
for (int i = 0, note; i < note_count; i++) | |
{ | |
cin >> note; | |
if(note < required_money) //if the value of note is more than the required money, it obviously won't help in forming a subset; these are useless notes and let's not add them to the note pool | |
notes.push_back(note); | |
else if (note == required_money) //if there is a note whose value is equal to the required money, then we hit a jackpot; let's finish the case without further computation | |
{ | |
success = true; | |
break; | |
} | |
} | |
if (success) | |
{ | |
cout << "Yes" << endl; | |
continue; //goes to next case | |
} | |
note_count = notes.size(); //we might have removed some notes; so let's update the note_count with the correct number of notes in notes vector | |
sort(notes.begin(), notes.end()); //sort the notes in increasing order | |
int minpos = 0; //1 3 5 7 ... if the required number is 20, there is no combination of notes of the first 3 notes (1, 3, 5) which can give 20; minpos is the index of the next highest note after the notes in the set (in this case 7) | |
for (int count = 0; minpos < note_count; minpos++) | |
{ | |
count += notes[minpos]; //add the next note to the sum | |
if (count > required_money) break; //the sum exceeds the required money so we need to take the note at this location seriously | |
} | |
for (int i = note_count - 1; i >= minpos; i--) | |
{ | |
if (issubset(i - 1, notes[i])) | |
{ | |
success = true; | |
break; | |
} | |
} | |
if(success) cout << "Yes" << endl; | |
else cout << "No" << endl; | |
} | |
return 0; | |
} | |
/* | |
ALGORITHM | |
------------------- | |
let notes be: 1 2 4 6 12 14 23 29 43 | |
required money: 26 | |
29, 43 are greater than 26; so they are useless; we will treat the situation as if they weren't even there | |
so the useful notes are: 1 2 4 6 12 14 23 | |
LABLE1: | |
we start from the last number: 23 | |
23 + 14 exceeds 26; so any combination having these two notes are of no help | |
23 + 12 exceeds 26 too; so any combo with these notes is of no use | |
23 + 6 and 23 + 4 exceed 26 too; so this combo is useless as well | |
23 + 2 is less than 26; so we need to check from here | |
let us combine the two notes 23 and 2; we get 25; having two notes of 23 and 2 is as good as having a note of 25 | |
LABLE2: | |
now let us jump to LABLE1 and start with the number 25 and check notes smaller than 2 | |
25 + 1 = 26!!!! this works!! | |
Suppose 25 + 1 hadn't worked, we would try the next number after 2; try with 23 + 1 + x combo | |
(in this case there can't be any x becaz 1 is the smallest) | |
so the next change can happen with 23 | |
now we know that no combination having 23 can give the required money | |
so let's go to next number: 14 | |
GOTO LABLE1 with next number as 14 | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment