Dear fellow programming enthusiasts,

I have been sharpening my coding skills for the past few days and what better way to do that than solve Google's programming challenges. The following code is my solution to this problem:

My program, however, does not ask the user for the number of items (I). It counts that itself. Other than that, what shortcomings do you see in my code and what recommendations would you make. I have commented as much as I can to help you read through the code. Serious replies only. Thanks a bunch.

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167`` ``````#include #include #include #include using namespace std; //The type of elements the array holds struct STRUCT { vector VECT4; //holds the price values for each case int CREDIT; //holds credit for each case int INDEX1; // int INDEX2; //They hold the smaller and larger index //of items that add up to the given credit }; int main() { vector VECT1; vector VECT2; vector VECT3; int N; int C; cout << "Enter test cases: "; cin >> N; //Dynamically allocate an array of type STRUCT STRUCT *ARRAY; ARRAY = new STRUCT[N]; //BEGIN FOR OUTERMOST //This outermost for loop will iterate as many times as there are //test cases. For each iteration, it will ask the user for credit //and price values. It will assign the credit value and corresponding //price values, as integers, to the struct of the specific test. //Once this "outermost" for loop ends, the program will then calculate //the indices where the two numbers that add up to credit occur. for(int y = 0; y < N; y++) { cout << "Enter credit: "; cin >> C; //Char array to hold price values cout << "Enter prices: "; char INPUT[120]; cin.ignore(256, '\n'); gets(INPUT); //Assign credit to respective structs ARRAY[y].CREDIT = C; int counter = 0; int NUMBERCOUNT = 0; //Count the number of price values entered //Total numbers entered = total spaces + 1 for(int a = 0; INPUT[a] != '\0'; a++) { if(INPUT[a] == ' ') { NUMBERCOUNT++; VECT3.push_back(a + 1); } } //PARSE INPUT: CONVERT CHAR TO INTEGERS //Since the value entered by the user is stored into a char array, //I will extract each char and covert it into an int as long as it //is not a whitespace or as long as end of array hasn't reached. //Each number extracted will be put in vector VECT1. for(int x = 0; x <= NUMBERCOUNT; x++) { while(INPUT[counter] != ' ' && INPUT[counter] != '\0') { int temp = INPUT[counter] - '0'; VECT1.push_back(temp); counter++; } //temporary int holder int HOLDER = 0; //GET THE ACTUAL INTEGER VALUE //For instance, if VECT1 contains elements 1, 2 and 3 //then the following for loop will combine those elements //into 123 and store it in VECT2 for(int m = 0; m < VECT1.size(); m++) { HOLDER = HOLDER + (VECT1[VECT1.size() - (m + 1)] * pow(10, m)); } VECT2.push_back(HOLDER); VECT1.clear(); //VECT3 holds the indeces right after //the whitespace in INPUT array. //counter gets reinitialized to that index //with every iteration. counter = VECT3[x]; }//end parse for //Put price values into VECT4 of each array element. //VECT4 belonging to each struct will hold numbers //corresponding to price values for that test case for(int n = 0; n < VECT2.size(); n++) { ARRAY[y].VECT4.push_back(VECT2[n]); } //Clear vectors for reuse VECT2.clear(); VECT3.clear(); cout << endl; //The following nested loop calculates the output //i.e. at what positions in the input price list do the //values occur for(int e = 0; e < ARRAY[y].VECT4.size(); e++) { for(int f = e + 1; f < ARRAY[y].VECT4.size(); f++) { if(ARRAY[y].VECT4[e] + ARRAY[y].VECT4[f] == ARRAY[y].CREDIT) { ARRAY[y].INDEX1 = e + 1; ARRAY[y].INDEX2 = f + 1; }//endif }//endinnerfor }//endmiddlefor }//ENDFOR OUTERMOST //Display cout << "-------OUTPUT-------" << endl; cout << endl; for(int g = 0; g < N; g++) { cout << "Case #" << g + 1 << ": "; cout << ARRAY[g].INDEX1 << " " << ARRAY[g].INDEX2 << endl; } cout << endl; //endDisplay/* cin.ignore(256, '\n'); cout << "Press ANY key to exit..." << endl; cin.get(); return 0; }``````
Last edited on
> PARSE INPUT: CONVERT CHAR TO INTEGERS
¿why bother?
 ``12`` ``````int price; cin>>price;``````

You algorithm is O(n^2), try to improve it to O(n lg n)

Also, there is no need to read all the cases before processing.
are problem in line 108:
Last edited on
ne555, it says in the problem statement that the user enters the price values as one-line space-separated statement. I don't see how I can do that with ints. Also, for your other suggestion, what is the alternative?

In python (not tested yet)

 ``123456789101112131415`` ``````#!/usr/bin for c in xrange( input() ): credit = input() input() items = map( int, raw_input().split()) for i, t in enumerate(items): if t < credit: try: k = items.index(credit - t) except IndexError: k = null if ( k != null ): print "Case #" + str(-~c) + ":", i+1, k+1 break``````

E: @ne555, you do need to read in all the values at once because otherwise you are assuming that the 2 numbers will occur one after the other
Last edited on
Smac89, I am not familiar with Python. Sorry. If you tell me in words where my program is inefficient that would be great.
gcj wrote:
One line containing the value I, the number of items in the store.
One line containing a space separated list of I integers.
 ``12`` ``````for(int K=0; K> price[K];``````

If you insist in reading all the line at once
 ``123456`` ``````std::string line; getline( cin, line ); stringstream aux(line); K=0; while( aux>>price[K] ) ++K;``````

@Smac89: I said no need to read all the cases before processing.
One case is composed of `credit' and `prices', with that you can solve the case

Edit: OK, he process the cases online, but store the result. You are just wasting memory.
Last edited on
The Google test data has an error in it because they were not specific that the two items must be different items. (What if I want to buy two of the same thing?)

For the data they provide, the intersection of {x|x: all item prices} and {x|x:all (C - item price)} may be two or three (cardinality-wise).

Granted, I'm picking here, but it is an important nit-pick.
Last edited on
@vasiqisbewildered, your code produces a segmentation fault when run with the input file provided on the website. Using gdb, I found the error to be occuring on line 108.

Final one in python, confirmed that it works by submission:

 ``123456789101112131415`` ``````#!/usr/bin for c in xrange( input() ): credit = input() input() items = map( int, raw_input().split()) for i, t in enumerate(items): if t < credit: try: k = 1 + items[-~i:].index(credit - t) + i except ValueError or IndexError: k = -1 if ( k != -1 ): print "Case #" + str(-~c) + ":", i+1, k+1 break``````

In c/c++:
 ``12345678910111213141516171819202122232425262728293031323334`` ``````#include #include #include #include typedef std::deque d_i; using namespace std; int main() { d_i items; d_i::iterator ptr; int C, credit, l, temp, len; for ( scanf("%d", &C), len = 0; len++ < C; ) { scanf ("%d", &credit ); for ( scanf("%d", &l); l--; ) { cin >> temp; items.push_back (temp); } for ( d_i::iterator it = items.begin(); it != items.end(); ++it ) { if ( *it < credit ) if ( ( ptr = std::find( it+1, items.end(), (credit - *it) )) != items.end() ) { cout << "Case #" << len << ": " << -~( it - items.begin() ) << " " << -~( ptr - items.begin() ) << endl; break; } } items.clear(); } return 0; }``````
Last edited on
> What if I want to buy two of the same thing?
- Can i buy the same item twice?
- No, the store has only one copy of each item. You must buy two different items.
Ah, I missed that. (I've never looked at the code jam stuff before...)

My code created essentially a pair of sets - one with the prices - the other with the prices subtracted from C - and found the intersection.

Ah, well... time to go make popcorn balls for the children at school tomorrow... that I work with...

I've already made corn-cereal peanut-butter bars. (Some of the kids are allergic to peanuts, though, and so the popcorn balls.) A few of the other teachers will want some too...

...

:O)
Since the problem states that: 'Each test case will have exactly one solution',
it can be done in linear time (and linear space):

 ``12345678910111213141516171819202122232425`` ``````#include #include #include #include int main() { // read in the values instead of this const int value_of_credit = 200 ; const int available[] = { 1, 2, 67, 3, 4, 133, 5, 6, 7, 8, 9 } ; const std::size_t N = sizeof(available)/sizeof(*available) ; std::unordered_map map ; for( std::size_t pos = 0 ; pos < N ; ++pos ) { auto iter = map.find( available[pos] ) ; if( iter != map.end() ) { std::cout << iter->second << ' ' << pos << '\n' ; return EXIT_SUCCESS ; } else map[ value_of_credit - available[pos] ] = pos ; } // return EXIT_FAILURE ; // no solution }``````

http://ideone.com/mV4xmc
Smac89, so your 34 lines of c++ code are basically doing the same thing as my 167 lines? If so, bravo my friend! Also, would you be kind enough to go through your code (or maybe just comment) so I have an idea of what it is doing. The following snippet, however, does not take into account that price values are entered as space-separated values in one line.

 ``12345`` `````` for ( scanf("%d", &l); l--; ) { cin >> temp; items.push_back (temp); }``````

How would you implement input "25 5 75 15" by the user at runtime?

Also, how does -~(it - items.begin()) work?
Last edited on
And everyone, please don't forget how the price values are entered. Most of my code is convering a char array into integer values. The user will input price values as follows:

25 75 25

There is a space after every value
 >>Most of my code is convering a char array into integer values.

http://stackoverflow.com/a/5738922

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869`` ``````#include #include #include #include typedef std::deque d_i; using namespace std; int main() { /*Variable declarations Begin*/ d_i items; d_i::iterator ptr; int C, credit, l, temp, len; /*Variable declarations End*/ //Actual code //First we read in the number of test cases and store this value in C for ( scanf("%d", &C), len = 0; len++ < C; ) { //Next read in amount of credit scanf ("%d", &credit ); //Start reading in the items found as we go through the store for ( scanf("%d", &l); l--; ) { //http://stackoverflow.com/a/5738922 cin >> temp; //Store them in the container items.push_back (temp); } //Now we have all the items on the list //Time to determine the 2 which will take up all of our credit //Set an iterator at the start of our container for ( d_i::iterator it = items.begin(); it != items.end(); ++it ) { //This line is not needed, but was added by me to eliminate doing extraneous work for //numbers that obviously would not work if ( *it < credit ) /*Once we find a number in the container that is below the credit amount, *then we try to find another number such that when added to the one we found *will equal the credit amount. *For this I used the 'find' function in the algorithm library *http://www.cplusplus.com/reference/algorithm/find/ *The search starts at the next index after the index of the first value we find *This is to eliminate using the same amount as in the case where the value found is half of the credit *( I believe this is what threw @Duoas off ) */ if ( ( ptr = std::find( it+1, items.end(), (credit - *it) )) != items.end() ) { //If the find function finds such a number, it will return an iterator to that place in the container //So that means we have found the pair of numbers; and as there could only exist one such pair //as stated by the requirements we have a solution cout << "Case #" << len << ": " << -~( it - items.begin() ) << " " << -~( ptr - items.begin() ) << endl; //calulate the iterator distances from the start //and output the smaller one first and the larger one break; //Break out of the for-loop as we have found the only pairs in this container } } items.clear(); //Clear the list/container and go to next test case } return 0; }``````
Last edited on
sorry everyone, but this solution is off track?
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465`` ``````#include using namespace std; int counter = 0; int N = 0; int I = 0; int C = 0; int p[2000]; // number max items = 2000, for case N = 50; int seekItems() { for (int i=0; i>N; while (counter>C; cout<<" input number of the items: "<<'\n'; cin>>I; for (int i=0; i

Last edited on
Smac89, that is genius. So c++ does have various tools to make programmers life easy. I will now begin work on another google codejam, keeping your coding techniques in mind all the way through. Thanks a bunch. I look forward to learn more and more c++ here.
Topic archived. No new replies allowed.