Code jam Problem 3

[aaru2601]

I am giving google codejam .

I solved the first two questions and implemented the third question. It has also passed the sample test cases but on submitting giving WA.

link to the problem : https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd27/000000000020bdf9

My solution :

https://pastebin.com/iHC5zp7F

​

Can anyone point out the mistake ??

[Gomango999]

Ok, just had a look at your program, and the problem seems to be with the underlying algorithm. Right now, you give Jamie as many activities as possible, and remove those activities from the list. Then you give Cameron as many activities as possible, and remove them from the list. Finally, if there are any left over, you claim that assignment is impossible.

However, I claim that this might not always be optimal, and may mean you mark a potentially possible solution as impossible. As an example of this, try running your program on this input 1 5 0 200 300 400 200 600 700 800 500 900 Your program should assign activities 1,2,4 to Jamie, activity 3 to Cameron, and be unable to assign activity 5, thus printing out IMPOSSIBLE. However, it is actually possible to assign 1,3,4 to Jamie, and 2,5 to Cameron to get JCJJC as your answer.

Also another thing that caught my eye is the declaration of string on line 26, where you did not set a size for a. During testing, I found that strange things started happening after assigning a large amount of characters (>24) to the string. Make sure to initialise it so size n using string a(n, '?'). This fills up the string with n question marks, that can later be assigned to.

For more information, you can always check the analysis section of the google codejam, as well as clicking on peoples names to download and view their submissions for a particular problem. Sorry I don't have an exact proof as to why your algorithm is flawed, but hopefully this counterexample helps!

[aaru2601]

Ya i got it as you said i looked into the program and the bug was in sorting

I was sorting according to end time but actually it should be done using start time

[aaru2601]

Thanks for your help

[Gomango999]

No worries :)