June CookOff Contest Problem Editorials

 

Problem Tester for the June Cook-off was Rajiv Kumar

 

SINSUMQ (written by Anton Lunyov)

 

 

Problem Setter Solution

Problem Tester Solution

 

ARITHPR (written by Anton Lunyov)

 

 

Problem Setter Solution

Problem Tester Solution

 

DPOWPERM (written by Anton Lunyov)

 

 

Problem Setter Solution

Problem Tester Solution

 

KNIGHTMV (written by Anton Lunyov)

 

You just simply need to check that string has the length 5, 1st and 4th symbols are in the range 'a'..'h', 2nd and 5th are in the range '1'..'8', 3rd symbol is '-'. After that you need to check is this a correct knight move which is easy exercise. Also you should be careful with spaces. If you use C++ and start your program with something like this scanf(“%d\n”,&TST) then you get wrong answer because the first string in the test contains only spaces and using this command you simply skip it and the second one starts with one space followed by the correct string. Using this command you skip this first space and analyze the string as correct however it's not.

 

Problem Setter Solution

Problem Tester Solution

 

SUPERPLN (written by Anton Lunyov)

 

At each step Dunno is in some city at some time. If Roly-Poly lives in this city and the start time of the birthday party is not less than the time when Dunno get this city then the answer is "Yes". Otherwise you need to find the closest flight from this city for the given time. If there is no flights in that city after this moment of time then the answer is "No" because Dunno will be stuck in that city forever. If he have already use the closest flight then the answer is also "No" because he will flight forever using the same sequence of flights and never gets the party. Otherwise you should use this flight, mark it as used, change your city and time to the corresponding ones and continue this procedure. Obviously we will use each flight at most once so we will have in total no more than N steps. The closest flight can be found using binary search. For example you can sort all flights by the city of arrival and then by the time of arrival and use binary search for such array. So the overall time complexity is O(N log N).

 

Problem Setter Solution

Problem Tester Solution

Comments

For problem SINSUMQ. It can

cgy4ever @ 20 Jun 2011 01:46 AM
For problem SINSUMQ. It can also solved online, but it will be a little slow. The main idea of this problem is sin(x) = Im[e^(ix)], so we can maintain a complex number or a 'phaser' and sum them up.

For SUPERPLN, what would be

pratikmoona @ 20 Jun 2011 08:28 AM
For SUPERPLN, what would be the answer for n = 0?

@pratik , that depends on

mkagenius @ 20 Jun 2011 01:46 PM
@pratik , that depends on values in the next line . i.e c1t1c2t2.

So much maths... :(

havaliza @ 20 Jun 2011 05:52 PM
So much maths... :(

For problem SUPERPLN. We can

NR @ 20 Jun 2011 07:20 PM
For problem SUPERPLN. We can also form graph consisting of an edge between two cities if there is a flight and then apply modified DFS search (also considering time ) to find the destination city. The complexity will be O(n) to form the graph and O(VE) for searching.

@pratik If n=0 then the

anton_adm @ 21 Jun 2011 12:21 AM
@pratik If n=0 then the answer is "Yes 0" if Dunno_city==Roly-Poly_city and Dunno_time<=party_time and "No" otherwise.

sir in problem correctness of

pprateek @ 21 Jun 2011 10:22 PM
sir in problem correctness of knight move , the problem setter solution has used string length to be 111 ... while it is 10 in the given problem ... and when i run my program with 111 it runs and with 11 even it runs bt it fails with 10 .... why is it so....

sir please ans my question

pprateek @ 22 Jun 2011 12:39 PM
sir please ans my question