MikeMirzayanov's blog

Testing Round #13
By MikeMirzayanov, history, 8 years ago, translation, In English

Hello, Codeforces!

I want to test the system before Good Bye 2016, to be sure that everything works as expected.

I invite you to take part in Testing Round 13. It will start soon, on December, 29, 09:05:00 (UTC). It will be unofficial unrated round. The duration is 75 minutes.

Pretests are unusually weak to trigger more hack.

You may expect interactive problems. Hope for hacks for them.

Thank you,
MikeMirzayanov

UPD: Many thanks to all the participants. It seems the system works as expected. We are ready to host Good Bye 2016!

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

Comments Comments (51)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I would help with the testing but the time is so early for me :(

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

Since there will be an interactive problem in the Good Bye contest, will the testing round also have an interactive one?

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

    "You may expect interactive problems. Hope for hacks for them."

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

      Yeah guess I just skipped over that while reading.

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

Anyone else is desiring to change nickname like me? :)

nice presents(cf round) for saying Goodybye 2016

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

How many problems?

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

When we can change Nickname?

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

This reminds me the great Education Codeforces Round by Edvard .

Ahh missing those Educational Codeforces Round .Sir do you have any plan to restart this Round?

Happy Hacking for All.

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

I have a lot of games did not attend, in The hope that The contest Goodbye2017 would it be possible for me to rise!

→ Reply
»
8 years ago, # |
  Vote: I like it -66 Vote: I do not like it

** ** *****? :P

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

How to solve C task? I couldn't invent something with smaller than 15 queries :(

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

    Most solutions I see in my room uses Brute Force (always query one possible candidate and then eliminate all the impossible numbers. Repeat until your set of possible candidates is of size 1). However, I don't think this will work because I hacked 2 other people in my room who passed pretests with 9431. I might fail System Test as well.

    UPD : I failed System Test as expected.

    P.S. There is a decision tree here that claims to solve the problem in 7 moves.

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

      I think that what you should also be doing, is not just choosing one possible candidate, but the one that minimizes the number of remaining candidates in the worst outcome.

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

        I submitted your idea using unordered_set and got WA on test61: 23664758

        when I submitted same code using set my code accepted: 23665361

        I can't figure out what is the problem with my first submission and what is difference between unordered_set and set in this case? :(

        UPD: unordered_set is a container based on hash, and hash is hackable! I guess it is the reason.

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

      That's interesting. I precomputed "optimal" decision tree (always choose a query which minimises the maximum candidature of the outcome) on my computer and copied it into an array. Managed to fit solution size into 38kb.

      Check out 23395909

      Update: actually, I just realised my decision tree isn't optimal at all. Minimising maximum number of remaining candidates is actually greedy: I should be minimising the maximum depth of remaining candidate subsets! I wonder if you can find the optimal tree deterministically faster than NP...

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

      Thanks !

      I thought all the time about some greedy algorithm :)

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

    0123,1234,2345...6789 gives 7 queries to ask. I could not figure out how to infer the string from them in the time left..Just a guess. :)

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

      You can only ask 6 because the 7th one should be a correct guess.

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

    There's a five-guess algorithm (https://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm) by Knuth for Mastermind.

    Same idea applies here as well, except for there are ten possible digits instead of six, thus giving not five, but a little bit more moves (7-ish or so)

    UPD: Yet it failed system tests :(

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

    http://slovesnov.users.sourceforge.net/bullscows/bullscows.pdf

    I can't endure these academic papers.

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

no hacks !! lets enjoy system testing now

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

I had one solution in 8 queries but none in 7 queries :(

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

someone got Runtime error on test 367 in Problem C

LOL XD

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

    It's quite easy to get a Runtime error if you forget about the fact that the program must terminate after it makes a correct guess. It's unlikely to happen on a random test case (as the test which such a solution fails depends on the way the queries are generated, and there are very few such tests for any reasonable way of generation), but it's likely to happen on at least one test case of a few hundreds.

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

    It's me. :(

    The RE is from that if I can't guess out the hidden string, it will trigger an assertion fail.

    But, after changing random first guess to fixed first guess, it got AC now. However, I'm still not sure why random first guess will fail to guess the hidden string in 7 queries.

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

Now that's what I call exhaustive testing.

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

Hello,

Why did http://codeforces.net/contest/753/submission/23394205 pass, given that it does not terminate after it makes a correct guess?

:D

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

Sorry, possible I am not enough good at Interactive problems and maybe I didn't read careful Interactive guide, but I have question :D

I spent a lot of time to find mistake at my program and it was printf without "\n" (new line). Is somewhere written that we need to use "\n" ?

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

    White space is enough. You just need to separate your answers: 23397246

    Bad:  12341235
    Good:  1234 1235

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

      Thanks, now I understand.

      Somehow I thought they will separate answers without my help :D

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

real programmers always defeat cheaters

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

What is the logic behind Problem A? I tried it by finding a number 'd' such that given number 'n' lies between 1+2+....d and 1+2+...(d+1). But i was unable to do any further. Any help of explaining the approach would be helpful. Also, i have went through some of the accepted solutions and they did some "add n to the last element". Why?

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

    The number of kids to which we will give n candies is k + 1. We will give 1 + 2 + ... + k candies to the first k kids and remaining n - 1 - 2 - ... - k candies to the last (k + 1)'th kid.
    1. This sum is strictly less than n. That is 1 + 2 + ... + k = k·(k + 1) / 2 < n.
    2. The remaining amount of candies is strictly larger than k. That is r = n - k·(k + 1) / 2 > k.

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

      Could you shed some more light on second inference. I am having trouble in finding why this method should work OR more clearly, intuition with which you came to such solution. Thanks a lot.

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

        I've gained intuition after solving this problem.

        For now you could try looking into examples:
        10 = 1 + 2 + 3 + 4
        11 = 1 + 2 + 3 + 5
        12 = 1 + 2 + 3 + 6
        13 = 1 + 2 + 3 + 7
        15 = 1 + 2 + 3 + 8

        In the last case n = 15, we can try to improve our distribution by splitting 8 into two parts.
        Here are all the possible partitions of 8 into two parts:
        8 = 1 + 7
        8 = 2 + 6
        8 = 3 + 5
        8 = 4 + 4
        We know that the next number we can use has to be at least 4, because we have used numbers {1, 2, 3} already. This automatically discards 3 out of 4 partitions: {(1, 7), (2, 6), (3, 5)}, because these partitions contain forbidden numbers 1, 2 and 3. The only partition that is not discarded because of the already used numbers is the following: 8 = 4 + 4. But we cannot use the number more than once in our distribution, so the following partition is invalid: 15 = 1 + 2 + 3 + 4 + 4.

        But we can improve k from 4 to 5 if we are given n = 16:
        16 = 1 + 2 + 3 + 4 + 9 = 1 + 2 + 3 + (4 + 5).

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

    Let d be the minimal number such that 1 + 2 + ... + d > n. Denote this sum 1 + 2 + ... + d as s.

    We are almost finished, just output all numbers from 1 to d, except s — n.

    E.g. if n = 13, it's 1 + 2 + 3 + 4 + 5, s = 15, output 1, 3, 4, 5 and don't output 15 — 13 = 2.

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

:D

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

I'm a bit curious of how the run time is determined for the interactive problem, e.g. is running time of the testing machine (that we interactive with) is counted?

I submitted the same solution for C 3 times and got 3 different results:

  1. TLE test 25

  2. TLE test 259

  3. AC

The problem is the 3rd submission run in ~300 ms less than the 2nd submission at test 259 (they are run with same source code, and same input)

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

editorial?

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

In the Hard version of Bulls & Cows, were all the test cases static numbers to guess? Or we need to guess the number from a smarter adversary. I think the latter is more challenging.

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

    arent both same,since testcaes consisted of all possible strings

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

      No, since an smart adversary doesn't need to pick the hidden number from the beginning. He only needs to keep their answer consistent, it means, at least one valid answer must exist, but he can guide you through a path of outcomes that force you to do more than 7 question, analyzing your guesses.

      It can be guaranteed as you say, if all possible numbers are asked and the solution is deterministic, otherwise I'm not so sure. Btw, I don't think all possible numbers are asked, but only ~400.

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

        But if all possible strings are included, a 'killer adversary' won't make a difference (your guess will still be the same), unless your algorithm included something random (well, it's not the fault of adversary :p)

        → Reply