Google codejam solution

[vasiqisbewildered]

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:

https://code.google.com/codejam/contest/351101/dashboard#s=p0

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.

#include <iostream>
#include <vector>
#include <math.h>
#include <stdio.h>
using namespace std;
 
//The type of elements the array holds
struct STRUCT
{
  vector<int> 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<int> VECT1;
    vector<int> VECT2;
    vector<int> 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;
}

[ne555]

> PARSE INPUT: CONVERT CHAR TO INTEGERS
¿why bother?

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.

[ar2007]

are problem in line 108:

[vasiqisbewildered]

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?

ar2007, please elaborate.

[Smac89]

In python (not tested yet)

#!/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

[vasiqisbewildered]

Smac89, I am not familiar with Python. Sorry. If you tell me in words where my program is inefficient that would be great.

[ne555]

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.

for(int K=0; K<I; ++K)
   std::cin >> price[K];

If you insist in reading all the line at once

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.

[Duthomhas]

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.

[Smac89]

@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.

The only thing that made your code inefficient was that you were storing the values you got instead of using them immediately. In most programming contests, you will not have enough time within the maximum run time to store the values, then read them again then store the answer and print the answers later. You just have to read in as much as you need to solve the first case, then move on to the next. Since input will be coming from stdin and the tester does not wait for each output before giving the next input, your program will already have all the input it needs loaded onto a reserved memory space and it will just read from that until it runs out of things to read and your job is to print the correct answer to stdout in the format specified

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

#!/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++:

#include <iostream>
#include <deque>
#include <algorithm>
#include <stdio.h>

typedef std::deque<int> 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;
}

[ne555]

> What if I want to buy two of the same thing?
Read the clarification
- Can i buy the same item twice?
- No, the store has only one copy of each item. You must buy two different items.

[Duthomhas]

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)

[JLBorges]

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

#include <iostream>
#include <sstream>
#include <unordered_map>
#include <cstdlib>

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<int,int> 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

[vasiqisbewildered]

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.

      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?

[vasiqisbewildered]

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

[Smac89]

>>Most of my code is convering a char array into integer values.

http://stackoverflow.com/a/5738922

#include <iostream>
#include <deque>
#include <algorithm>
#include <stdio.h>

typedef std::deque<int> 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;
}

[ar2007]

sorry everyone, but this solution is off track?

#include <iostream>
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<I; i++)
    {
        for (int j=0; j<I; j++)
        {
            if (i!=j || j!=i)
            {
                int z = p[i]+p[j];
                if (z==C)
                {
                    if (i<j)
                    {
                        cout<<" case #"<<counter<<" "<<i+1<<" "<<j+1<<'\n';
                        return 0;
                    }
                    else
                    {
                        cout<<" case #"<<counter<<" "<<j+1<<" "<<i+1<<'\n';
                        return 0;
                    }
                }
                
            }
        }
    }
    return 0;
}


int main()
{
    cout<<"input number of the case: "<<'\n';
    cin>>N;
    
    while (counter<N)
    {
        cout<<" input your bonus credit: "<<'\n';
        cin>>C;
        cout<<" input number of the items: "<<'\n';
        cin>>I;
        
        for (int i=0; i<I; i++)
            p[i] = rand() % 150 + counter;  // generator of random values​​, not to find special solutions. may also occur the case that no two items compatible with C
        
        for (int i=0; i<I; i+=10)
            cout<<p[i]<<" "<<p[i+1]<<" "<<p[i+2]<<" "<<p[i+3]<<" "<<p[i+4]<<" "<<p[i+5]<<" "<<p[i+6]<<" "<<p[i+7]<<" "<<p[i+8]<<" "<<p[i+9]<<'\n';
        
        seekItems();
        counter++;             
        
    }
    return 0;
}

[vasiqisbewildered]

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.