Program running slowly - please help find any inefficiencies

georgep (158)
I'm practicing for the Google Code Jam on this problem: http://code.google.com/codejam/contest/433101/dashboard

However, for the large test my program is exceeding the 8 minute time limit and even though it's just practice, I'd still like to have it working properly.

So my question: Can you please help find any places where my program could be made more efficient / where it is doing something unnecessary? I've had a look myself but it's always harder to spot yourself.

Thanks, here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
#include<iostream>
using namespace std;

int main()
{
	unsigned short int t, n;	
	bool state[31], powered[31];
	bool output[10001];
	unsigned int k;
	
	
	cin >> t;	//number of test cases
		for(int i=1; i <= t; i++){ //loops for each case
			
			state[0] = 1;	//set the socket to powered and the ON state to use later
			powered[0] = 1;
			
			for(int a=1; a <= 30; a++){	//initialise each array to 0
					state[a] = 0;			
					powered[a] = 0;
		}
			
			cin >> n >> k;	//get input for number of snappers and number of snaps
			
			for(int snaps=1; snaps <= k; snaps++){	//loops for each snap
				
				
				for(int a = 1; a <= n; a++){	//sets each state to powered or unpowered
					
					if(powered[a-1] && state[a-1])	//checks if each one is powered
						powered[a] = 1;
						
					else
						powered[a] = 0;
				
				}
				
				
				for(int a = n; a >= 1; a--){	//sets each snapper to ON or OFF state
					
					if(powered[a]){	//if it is powered (recieving power) it changes ON/OFF state
						
						if(state[a])
							state[a] = 0;
						
						else
							state[a] = 1;	
							
					}
					
				}
				
			}
			
			for(int a = 1; a <= n; a++){	//final update to powered (not very elegant but it works)
					
					if(powered[a-1] && state[a-1])	
						powered[a] = 1;
						
					else
						powered[a] = 0;
						
				
				}
			
			if(powered[n] && state[n])	//after all snaps, if specified snapper is receiving and sending power the light is on
				output[i] = 1;	//output is stored
				
			else
				output[i] = 0;
			
			
		}
	
	
	for(int i=1; i <= t; i++){
			
			cout << "Case #" << i << ": ";
			
			if(output[i])		//output for each case displayed
				cout << "ON" << endl;
			
			else
				cout << "OFF" << endl;
			
		}
	
	return 0;	
}


Edit: the tab size seems to have come out quite large, sorry if that makes the code harder to read.
Last edited on
Lowest0ne (1536)
Are we even allowed to help :)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
			for(int snaps=1; snaps <= k; snaps++){	//loops for each snap
				
				
				for(int a = 1; a <= n; a++){	//sets each state to powered or unpowered
					
					if(powered[a-1] && state[a-1])	//checks if each one is powered
						powered[a] = 1;
						
					else
						powered[a] = 0;
				
				}
				
				
				for(int a = n; a >= 1; a--){	//sets each snapper to ON or OFF state
					
					if(powered[a]){	//if it is powered (recieving power) it changes ON/OFF state
						
						if(state[a])
							state[a] = 0;
						
						else
							state[a] = 1;	
							
					}
					
				}
				
			}


This can probably be one loop, find some way to set the state at the same time as powered.

As a side:
1
2
 
for (int i = 0; i < "size of array"; i++)
{  // Do things to Array[i] }

is easier for me to understand than the way you have the for loops.
Last edited on
ui uiho (382)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
#include<iostream>
using namespace std;

int main()
{
	unsigned short int t, n;	
	bool state[31], powered[31];
	bool output[10001];
	unsigned int k;
	//you need to go over arrays and array references
	
	cin >> t;	//number of test cases
    for(int i = 0; i < t; i++){ //loops for each case 
        
        state[0] = 1;	//set the socket to powered and the ON state to use later
        powered[0] = 1;
        //do you want this loop to end here? or run EVERYTHING t times?
        for(int a = 1; a < 31; a++){
            state[a] = 0;	//maybe use true or false instead of 0 and 1 for bool type		
            powered[a] = 0;
		}
        
        cin >> n >> k;	//get input for number of snappers and number of snaps
        
        for(int snaps=1; snaps <= k; snaps++){	//loops for each snap
            
            
            for(int a = 1; a <= n; a++){	//sets each state to powered or unpowered
                
                if(powered[a-1] && state[a-1])	//checks if each one is powered //no boolstatement 
                    //here it will just check to see if they both are true or false. which they are. 
                    powered[a] = 1;
                
                else
                    powered[a] = 0;
				
            }
            
            
            for(int a = n; a >= 1; a--){	//sets each snapper to ON or OFF state
                
                if(powered[a]){	//if it is powered (recieving power) it changes ON/OFF state
                    
                    if(state[a])
                        state[a] = 0;
                    
                    else
                        state[a] = 1;	
                    
                }
                
            }
            
        }
        
        for(int a = 1; a <= n; a++){	//final update to powered (not very elegant but it works)
            
            if(powered[a-1] && state[a-1])	
                powered[a] = 1;
            
            else
                powered[a] = 0;
            
            
        }
        
        if(powered[n] && state[n])	//after all snaps, if specified snapper is receiving and sending power the light is on
            output[i] = 1;	//output is stored
        
        else
            output[i] = 0;
        
        
    }
	
	
	for(int i=1; i <= t; i++){
        
        cout << "Case #" << i << ": ";
        
        if(output[i])		//output for each case displayed
            cout << "ON" << endl;
        
        else
            cout << "OFF" << endl;
        
    }
	
	return 0;	
}
georgep (158)
LowestOne
Don't worry! This question is from the 2010 contest, I'm using it as practice for the one this Friday.

Sorry if it was hard to read. I never planned on sharing the code and my IDE makes everything very clear.

Good point about using one loop. Originally I didn't take power into account and so I simply added it in after.

Edit: Actually, I think I can't put it into one loop after all. The state is meant to change instantaneously and can only change if it is powered. However, I can't update all of them instantaneously and so I must work through them one by one. Unfortunately, working through them from 1 to n means that the states are affected by change of power (which shouldn't happen), whilst working through from n to 1 means power is not updated correctly.

ui uiho
Why should I use array references? I'm probably missing something but I'm not using any functions so I'm not sure why I would need to.

Yes, I want to run all the code - apart from the output and input - t (the number of test cases) times.

I suppose using true or false will be slightly quicker, given that 1 or 0 must first be evaluated to true or false - thanks for pointing that out.

A snapper is powered only if the snapper before it is: (receiving power && able to send power). It only evaluates to true if both powered[a-1] == true and state[a-1] == true. However, the way I've written it works in exactly the same way.

Last edited on
cire (8284)
Initially, all the Snappers are in the OFF state, so only the first one is receiving power from the socket, and the light is off. I snap my fingers once, which toggles the first Snapper into the ON state and gives power to the second one. I snap my fingers again, which toggles both Snappers and then promptly cuts power off from the second one, leaving it in the ON state, but with no power. I snap my fingers the third time, which toggles the first Snapper again and gives power to the second one. Now both Snappers are in the ON state, and if my light is plugged into the second Snapper it will be on.


Consider:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
	num of snappers
  ******************************
  |	1	2	 3
  ******************************
s |	0	00	000
t |	1	01	001
a |	0	10	010
t |	1	11	011
e |	0	00	100
s |	1	01	101
  |	0	10	110
  |	1	11	111
  |	0	00	000


If you look at the right side being the socket and left side being the light, the only time the light is lit is when all the numbers are 1's. Looks an awful lot like binary numbers.

Hmm, I wonder how one could take advantage?
Last edited on
Topic archived. No new replies allowed.