By adhoc_king, history, 18 months ago,

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

• +40

 » 18 months ago, # |   -7 Auto comment: topic has been updated by adhoc_king (previous revision, new revision, compare).
 » 18 months ago, # | ← Rev. 4 →   0 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.
•  » » 18 months ago, # ^ |   +7 Did you handle "N"?If you didn't terminate the program after reading "N" you will get TLE.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +18 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.
•  » » » 18 months ago, # ^ |   0 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'.
•  » » » » 18 months ago, # ^ |   0 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.
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 18 months ago, # ^ |   0 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.
•  » » » 18 months ago, # ^ |   0 Submissions are public.
 » 18 months ago, # | ← Rev. 2 →   +30 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
•  » » 18 months ago, # ^ |   0 I can't manage to make the script provided to work. Can some explain that ;-; ?
•  » » » 18 months ago, # ^ | ← Rev. 2 →   +11 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
•  » » 18 months ago, # ^ |   0 I can't make interactive runner work if the solution is Python, does anyone have an idea?
•  » » » 18 months ago, # ^ |   0 'python your-solution.py' instead of 'your-binary-file'
•  » » 18 months ago, # ^ |   0 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)
•  » » 18 months ago, # ^ |   0 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!
•  » » 18 months ago, # ^ |   0 40 min for me
 » 18 months ago, # |   +49 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.
•  » » 18 months ago, # ^ |   +40 I calculate that 119+23+5+1=153 during the contest. It caused this problem to waste me a lot of time.
•  » » » 18 months ago, # ^ |   +13 I'm having some trouble figuring how someone can calculate 153 from that...
•  » » » » 18 months ago, # ^ |   +4 Add 5 couple of times.
 » 18 months ago, # |   +15 I got TLE in B because I was reading F for each testcase, maybe that helps some of you
•  » » 18 months ago, # ^ |   +16 Also don't print "Case" stuff and read a char after printing the answer, maybe that helps some of you
•  » » 18 months ago, # ^ |   +8 Same. Was able to debug this just 3/4minutes after the end.Rank would have been around ~1K. :|
 » 18 months ago, # | ← Rev. 3 →   0 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!
•  » » 18 months ago, # ^ |   0 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! :(
•  » » » 18 months ago, # ^ |   0 I'm bad at debugging but I can give you a hint. When the count of unique characters in an index i for all the strings is not 1 for any index then answer is impossible. Is this true? Think about when the count is 2.
•  » » » » 18 months ago, # ^ |   0 Yes. when the count is 2 then i was adding the character according to the below mapping. mp2["RP"] = 'P'; mp2["PR"] = 'P'; mp2["RS"] = 'R'; mp2["SR"] = 'R'; mp2["SP"] = 'S'; mp2["PS"] = 'S';Example: RP,PS (counts = 2,2) answer will be impossible but for RP, SP (counts = 2,1), answer can be RS.
•  » » » » » 18 months ago, # ^ |   0 Can someone help? I am stuck :(
•  » » » 18 months ago, # ^ | ← Rev. 4 →   +11 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 first move.$PP$ wins $PR$ after the second move.There is no number $i$ such, that $PP$ wins both $PR$ and $RP$ after the $i^{th}$ move. Your outputted strategy doesn't have to win his opponents after the same move. Remember, the matches are played independantly.
•  » » » » 18 months ago, # ^ |   0 Ah!! Damn! Thank you for taking the time out to help! :
•  » » » » » 18 months ago, # ^ |   0 My pleasure :)
•  » » » » » » 18 months ago, # ^ |   0 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
•  » » » » » » » 18 months ago, # ^ | ← Rev. 7 →   0 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:  if (ch.size() == 0) return 0; to this:  if (ch.size() == 0) return 1; 
•  » » » » » » » » 18 months ago, # ^ |   0 Still not working. I tried downloading working solution of others and trying random test cases but it is working fine with them.
•  » » » » » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 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 :(
•  » » » » » » » » » 18 months ago, # ^ | ← Rev. 2 →   0 Damn me. Got my mistake. The mistake is in conversion of array of character into string. set ch; char curr[501]; int i = 0; for (auto xx : ch) { curr[i++] = xx; } //curr[i] = ‘\0’; Missed to introduce this terminater. string cur(curr); Learning : We should always take care of basics.
•  » » » » » » » » » 18 months ago, # ^ | ← Rev. 3 →   +3 ====================================== set ch; string s(ch.begin(), ch.end()); Your main mistake is not learning the language you use.
•  » » » » » » » » » 18 months ago, # ^ |   0 True that.
 » 18 months ago, # |   0 Do they still publish official analysis after the round? I can't find it anywhere!!
•  » » 18 months ago, # ^ |   +3 open the question. Click on Analysis Tab
 » 18 months ago, # |   0 Are there statistics for this round?
•  » » 18 months ago, # ^ | ← Rev. 3 →   -8 UPD: My answer was wrong. This blog post contains information about Google codejam stats.
 » 18 months ago, # | ← Rev. 3 →   0 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?
•  » » 18 months ago, # ^ |   0 mkfifo input mkfifo output python testing_tool.py > input < output ./your_binary < input > output 
•  » » 18 months ago, # ^ |   +5 You can use interactive_runner.py provided in the problem (Testing Tool): python interactive_runner.py python testing_tool.py 0 -- ./program.o 
 » 18 months ago, # |   0 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?
•  » » 18 months ago, # ^ |   0 Try looking for any good introductory text to game theory. Look for Sprague-Grundy theorem.
 » 18 months ago, # |   0 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 solutionIf 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.
•  » » 18 months ago, # ^ |   0 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.
•  » » » 18 months ago, # ^ |   0 Yes I am eliminating those robots which are defeated once.
•  » » » 18 months ago, # ^ |   0 Actually he does not include them. for (int i = 0; i < a; i++) { // Here. if(skip.find(i) != skip.end()) continue; if (idx < robot[i].length()) { ch.insert(robot[i][idx]); } else { ch.insert(robot[i][idx % robot[i].length()]); } } 
•  » » » 18 months ago, # ^ |   +6 Damn me. Got my mistake. The mistake is in conversion of array of character into string. set ch; char curr[501]; int i = 0; for (auto xx : ch) { curr[i++] = xx; } //curr[i] = ‘\0’; Missed to introduce this terminater. string cur(curr); Learning : We should always take care of basics.