Google Code Jam Round 1C 2019

6 лет назад, # |

← Rev. 4 →

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.

→ Ответить

6 лет назад, # ^ |

Did you handle "N"?

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

destinydrifter

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

pllk

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

Submissions are public.

→ Ответить

Swistakk

6 лет назад, # |

← 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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

MoritakaMashiro

6 лет назад, # ^ |

← 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

→ Ответить

alexwice

6 лет назад, # ^ |

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

→ Ответить

McDic

6 лет назад, # ^ |

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

→ Ответить

Sehnsucht

6 лет назад, # ^ |

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)

→ Ответить

Epiq

6 лет назад, # ^ |

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!

→ Ответить

kronos

6 лет назад, # ^ |

40 min for me

→ Ответить

-is-this-fft-

6 лет назад, # |

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

→ Ответить

SkyDec

6 лет назад, # ^ |

+40

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

→ Ответить

Chilli

6 лет назад, # ^ |

+13

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

→ Ответить

destinydrifter

6 лет назад, # ^ |

Add 5 couple of times.

→ Ответить

dioji

6 лет назад, # |

+15

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

→ Ответить

kalimm

6 лет назад, # ^ |

+16

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

→ Ответить

pk.

6 лет назад, # ^ |

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

Rank would have been around ~1K. :|

→ Ответить

knighthood

6 лет назад, # |

← Rev. 3 →

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

→ Ответить

knighthood

6 лет назад, # ^ |

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

→ Ответить

aryaman

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

knighthood

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

My pleasure :)

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 7 →

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;

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

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.

→ Ответить

dalex

6 лет назад, # ^ |

← Rev. 3 →

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

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

Your main mistake is not learning the language you use.

→ Ответить

aka.Sohieb

6 лет назад, # |

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

→ Ответить

v_kamani19

6 лет назад, # ^ |

open the question. Click on Analysis Tab

→ Ответить

nandonathaniel

6 лет назад, # |

Are there statistics for this round?

→ Ответить

6 лет назад, # ^ |

← Rev. 3 →

-8

UPD: My answer was wrong. This blog post contains information about Google codejam stats.

→ Ответить

yz6205

6 лет назад, # |

← Rev. 3 →

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?

→ Ответить

Igorjan94

6 лет назад, # ^ |

mkfifo input
mkfifo output
python testing_tool.py > input < output
./your_binary < input > output

→ Ответить

ppat

6 лет назад, # ^ |

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

python interactive_runner.py python testing_tool.py 0 -- ./program.o

→ Ответить

pk842

6 лет назад, # |

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?

→ Ответить

Shisuko

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

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.

→ Ответить

adhoc_king

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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()]);
    }
  }

→ Ответить