adhoc_king's blog

Google Code Jam Round 1C 2019
By adhoc_king, history, 6 years ago, In English

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

  • Vote: I like it
  • +40
  • Vote: I do not like it

Comments Comments (49)
| Write comment?
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Auto comment: topic has been updated by adhoc_king (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Did you handle "N"?

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +18 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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'.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +30 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    40 min for me

    → Reply
»
6 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    Rank would have been around ~1K. :|

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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! :(

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah!! Damn! Thank you for taking the time out to help! :

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My pleasure :)

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 7   Vote: I like it 0 Vote: I do not like it

              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 :D

              You should change lines 32, 33 of your code from this:

                if (ch.size() == 0)
    return 0;

              to this:

                if (ch.size() == 0)
    return 1;
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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 :(

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                  ← Rev. 3   Vote: I like it +3 Vote: I do not like it

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

                  set<char> ch;
string s(ch.begin(), ch.end());

                  Your main mistake is not learning the language you use.

                  → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there statistics for this round?

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    mkfifo input
mkfifo output
python testing_tool.py > input < output
./your_binary < input > output
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can use interactive_runner.py provided in the problem (Testing Tool):

    python interactive_runner.py python testing_tool.py 0 -- ./program.o
    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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()]);
    }
  }
      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      → Reply