I couldn't find a blog post about Round 1C. So let's discuss the solutions! :)

# | User | Rating |
---|---|---|

1 | tourist | 3619 |

2 | Um_nik | 3493 |

3 | ecnerwala | 3446 |

4 | Radewoosh | 3383 |

5 | ksun48 | 3357 |

6 | yosupo | 3324 |

7 | Benq | 3299 |

8 | maroonrk | 3243 |

9 | apiadu | 3238 |

10 | Petr | 3217 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 195 |

4 | vovuh | 189 |

5 | pikmike | 186 |

5 | Um_nik | 186 |

5 | antontrygubO_o | 186 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

I couldn't find a blog post about Round 1C. So let's discuss the solutions! :)

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/29/2020 04:24:08 (i3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by adhoc_king (previous revision, new revision, compare).At the end of the contest my submissions for problem "Power Arrangers" were being checked for quite long time and were getting TLE verdict. But I am sure that my latest solutions work in the given time limit(they do approximately $$$50*5*5!=30000$$$ operations, which should certainly fit in the time limit, also it works OK on my computer). Can it be some technical issue? Has anyone else had similiar issues?

UPD:As Adhami told, my solution was wrong and should get WA. But because I didn't handle 'N' I got TLE.Did you handle "N"?

If you didn't terminate the program after reading "N" you will get TLE.

No, I did not.I'll check if it is the problem in the practice mode. Thanks for your help.

UPD:Yes, you were right. I changed my solution so that it terminates after reading 'N', and it got WA.But even if it is a TLE without handling N, it does not guarantee the correctness of solution even if you handle 'N'. If your solution is correct you don't need to handle 'N'.

Yes, TLE in GCJ interactive problems are misleading. Most of TLEs are actually wrong answers not an actual TLE.

None of TLEs are AC, since "N" is only sent if the solution did something wrong.~~Maybe~~my solution was wrong(though it worked on many random test cases on my computer) and should get WA. But because I didn't handle 'N' I got TLE.I couldn't get the interaction working, my C++ code TLE's both with the provided local grader and on the server. If somebody has a working C++ code, I would like to see it.

Submissions are public.

Solving easy — 20 min

Solving hard — 20 min

Solving med — 20 min

Figuring out how tf do I use these stupid interactive runnners and testers and noting that judge returns "Y" or "N", not "1" and "0" — 30 min

I can't manage to make the script provided to work. Can some explain that ;-; ?

You have to use the interactive_runner.py as mentioned in the problem too. You have to run it as

`python interactive_runner.py python testing_tool.py 0 -- your_binary`

I can't make interactive runner work if the solution is Python, does anyone have an idea?

'python your-solution.py' instead of 'your-binary-file'

I dropped their runners as soon as I took a glance at it.

It turned way too easier to test and debug a solution with a handwritten runner, with using a bit of OOP. You would just change a line in the code before sending the solution. I guess it saved me a real amount of time. It looked like this — https://gist.github.com/Izaron/b5ccd047d69d315d005557791bdea9ca

(But anyway I've got 2 TLE because of printing "Case #" and not reading F)

Haha, true!

Luckily, there's a reminder on how to run it in the comments in

`interactive_runner.py`

, right at the top.P.S: Congrats on making it into top50!

40 min for me

I must say I was very excited when I first read problem 2: "interactive problem, answer chosen uniformly at random? Must be some clever and cool elegant solution!".

Then I noticed that 119 + 23 + 5 + 1 < 150.

I calculate that 119+23+5+1=153 during the contest. It caused this problem to waste me a lot of time.

I'm having some trouble figuring how someone can calculate 153 from that...

Add 5 couple of times.

I got TLE in B because I was reading F for each testcase, maybe that helps some of you

Also don't print "Case" stuff and read a char after printing the answer, maybe that helps some of you

Same. Was able to debug this just 3/4minutes after the end.

Rank would have been around ~1K. :|

Bonjour everyone! ;(

Can someone please help me with the first problem :(

I got a WA but i am missing some corner case maybe.

My solution is similar to the one in editorial.

Thanks in advance!

Code = https://ideone.com/hq1PC9

So I am ruling out 2 cases before creating the string and they are:

1: When the count of unique characters in an index i for all the strings is not 1 for any index then answer is impossible. 2: If this index whose count is 1 (first 1 we get) occurs after an index with 3 different characters then answer is again impossible.

Now other than this, i will iterate till the first 1 and create string accordingly (mp2 in my code) and for the last 1 (mp1 is used in my code)

s'il vous plaît! :(

I'm bad at debugging but I can give you a hint.

Is this true? Think about when the count is 2.

Yes. when the count is 2 then i was adding the character according to the below mapping.

Example: RP,PS (counts = 2,2) answer will be impossible but for RP, SP (counts = 2,1), answer can be RS.

Can someone help? I am stuck :(

Your idea is wrong. Don't bother debugging your code. It fails on this test case:

$$$1$$$

$$$2$$$

$$$RP$$$

$$$PR$$$

Your output:$$$Case #1: IMPOSSIBLE$$$Example answer:$$$Case #1: PP$$$$$$PP$$$ wins $$$RP$$$ after the

firstmove.$$$PP$$$ wins $$$PR$$$ after the

secondmove.There is no number $$$i$$$ such, that $$$PP$$$ wins both $$$PR$$$ and $$$RP$$$ after the $$$i^{th}$$$ move. Your outputted strategy doesn't

haveto win his opponents after the same move. Remember, the matches are played independantly.Ah!! Damn! Thank you for taking the time out to help! :

My pleasure :)

Hey my solution was handling this case. Like after every round I was eliminating weaker robot . Like for above test case after 1st round I will eliminate 1st robot i.e. RP. In second round I am left with only one robot i.e. PR and hence PP would be the answer. I am still not able to find out where m I failing. https://ideone.com/zuLpnB

Hello. I think I have found couple of bugs in your code. I am in computer lab of my school, and the lesson has nothing to do with computer science,

~~so I'll type your bugs here in a while~~:DYou should change lines 32, 33 of your code from this:

to this:

Still not working. I tried downloading working solution of others and trying random test cases but it is working fine with them.

~~You have another bug in your code. I have added it in my previous answer.~~I was mislead. I don't understand whats the problem in your solution :(Damn me. Got my mistake. The mistake is in conversion of array of character into string.

Learning : We should always take care of basics.

======================================

Your main mistake is not learning the language you use.

True that.

Do they still publish official analysis after the round? I can't find it anywhere!!

open the question. Click on Analysis Tab

Are there statistics for this round?

UPD:My answer was wrong. This blog post contains information about Google codejam stats.In the second problem. Inputs & outputs are huge. I don't have any idea about this except typing 148 numbers from my solution to the running test_tool.py and type the result back by hand. Any way easier?

You can use

interactive_runner.pyprovided in the problem (Testing Tool):Can someone explain the solution for the 2nd subtask of last problem?

I have read the analysis but didn't get the part where they tell that our problem gets divided into 2 sub-problems?

Can someone please explain that or any other approach?

Try looking for any good introductory text to game theory. Look for Sprague-Grundy theorem.

Can anyone explain the solution of Problem 1(Robot Programming Strategy).

I have done exactly mentioned in analysis. First stored all the program of other robots in vector . Then accessed i-th character of all robot and put it in a set. Then I have checked for 3 cases.

If set size is 3 (R,P,S) it mean there cannot be any solution with our program can win.

If size of set is 1 it means that iteration only have 1 value and we can choose corresponding winning value and return the solution

If size of set is 2 then choose the stronger character (like "R" in "RS") and proceed till we get size of set 3 or 1 , or our program length reaches 500 .

Here is my solution https://ideone.com/KJ8ovE It would be so grateful if anyone can help me debugging the solution.I have tried downloading working solution of other and tried random test cases but it is working fine.

I didn't read the code fully but this might be one possible mistake, suppose you defeated player 1 in the first move then you don't need to include its other characters in the subsequent moves. If you include it then you might get all the characters (PRS) at some position which would result in a false impossible result.

Yes I am eliminating those robots which are defeated once.

Actually he does not include them.

Damn me. Got my mistake. The mistake is in conversion of array of character into string.

Learning : We should always take care of basics.