KhaustovPavel's blog

By KhaustovPavel, history, 3 weeks ago, In English

Hey everyone!

At the Google Kick Start Round B 2021 I faced a very strange thing. After submitting solution for problem B "Longest Progression" I got RE on the large test. That was weird, because for my solution there was no much difference between small and large tests. But there was one static array in my solution of size (1 << 17). I double-checked that $$$N$$$ is not greater than $$$10^5$$$ in the problem statement. I had no idea, but finally I replaced the array with std::vector of dynamic size and the solution passed.

Then I submitted a question: "Some of my solutions got RE on the large test. After changing the static size of (1 << 17) which is larger than 10^5 to dynamic STL vector of size N the same solution passed this test. Probably something is wrong with the limits specified in the problem statement. Is that so?".

And the response was: "There is no problem with the limit. Please read the problem statement more carefully. Consider looking at the limits and the sample cases if those might help.".

After that I've looked at the problem statement again and the limit for $$$N$$$ was $$$3 \times 10^5$$$. I cannot believe I haven't noticed the $$$3 \times$$$ in the problem statement so many times.

Is there anyone, who faced the same problem during the contest? Or is it time for me to see a doctor?

UPD. I've finally managed to find out what happened. I've picked the wrong problem while asking a question. And for this problem the limits were initially incorrect. That explains everything except for three things:

  • Why the one who responded to me haven't guessed that I'm probably talking about another problem? The was only one problem with wrong limits in the problem statement.

  • How could I know that I need to refresh the problem statement (without going to questions tab)?

  • What is the logic behind ordering the problems in the following order B, A, D, C at the questions tab?

Probably I expect too much from Google Kick Start, but I was left with a lot of questions.

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

»
3 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

It was changed from $$$10^5$$$ to $$$3 \times 10^5$$$ during the contest, and this clarification happened during the contest as well:

so their response to your question was probably based on the updated statement (but still weird that they didn't consider that when responding to yours). And yeah, this also affected me :(

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Thank you for your response. I found out that all this happened because I've picked the wrong problem while asking a question. Updated the main post with that.

    But I still wonder if it was too difficult to understand that I'm talking about another problem? Or is it too difficult to throw alert with notification about the changes to everyone? Too weird for me :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

will we always get runtime error while trying to access out of bounds?

I had this solution with static $$$dp$$$ with $$$(1000 * 1000)$$$ size but for $$$n = 1500$$$ if should give runtime error right? but it's WA. later on, I found that [ ] operator will return any garbage value while accessing out of bound without any exception, I tried this with std::vector too it has the same situation for this particular solution. so, when will we can expect runtime error?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can find a detailed explanation here: https://stackoverflow.com/questions/14015632/c-vector-bounds

    And as suggested there it's possible to enforce bounds checking by using -D_GLIBCXX_DEBUG command line option. Or by adding "#define _GLIBCXX_DEBUG" at the top of your source file before any #include directives. If the compiler is GNU C++.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I didn't even realized that in the problem order B was first :waturr:

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Looks like they have rejudged submissions. Unlike Codejam IO so far they haven't added any update in the analysis section.
My TLE verdicts on B's large subtasks are now all converted to accepted. I finished the contest at 2:11:00 with 5 penalties. Now it's showing AC at 1:34:38 with 2 penalties.
My rank jumped from ~120-130 (just after the contest) to 70 right now.