MikeMirzayanov's blog

Testing Round #10
By MikeMirzayanov, 11 years ago, translation, In English

We've introduced API and now we want to test the system before Round 251.

I invite you to take part in Testing Round 10. It starts on usual time, June 3rd. It will be unofficial unrated round.

I tried to pick up the problem to make the round interesting for many of you. Pretests are unusually weak to trigger more hack.

If you see any unexpected behavior or bugs, please inform us via comments.\

Thanks.

Announcement of Testing Round 10
  • Vote: I like it
  • +99
  • Vote: I do not like it

Comments Comments (42)
| Write comment?
»
11 years ago, # |
  Vote: I like it -47 Vote: I do not like it

This contest give points to the rankings?

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

It's my first contest but it's unrated ..... :(

it's great cause it's a testing round ..... :)

Wish you luck everybody

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it -13 Vote: I do not like it

a

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

when trying to register, i get the following message:
"You are registering out of competition, reason: rating should be between 0 and 1699 in order to register for the contest"

this makes me assume that there is some difference if participant is Div-1 or Div-2 at start of the round.
but i guess there shouldn't be, coz this is only a Testing Round.

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

    Perhaps it's built in the platform that a normal contest has to be flagged as either div1 or div2 ?!?!

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

    For fear of too much hacking maybe.

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

I am unable to register/participate :(

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

    next time try to register before starting time by 5 minutes or more.

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

What was approach to solve Problem B?

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

    when ur at ith index, just keep taking (or giving) the required number of matches from i+1th index.
    even if i+1 doesnt contain enough, it will become negative temporarily, but later it will take whatever it needs from i+2.
    this process will go on until n-1 takes (or gives) something from n. after this last operation, all boxes will contain same number of matches.

    PS: be careful of integer overflow (use long long instead of int)!

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

      how to prove that this method will give the min number of moves needed in order to reach the wanted state?

      edit:

      I think I got it. But there's still a problem. Suppose in position i of the array we have a number Array[i] which is less than or more than the needed number. The additions or subtractions that we need to make in order to make Array[i] = needed is equals to abs(Array[i] - needed) Now, we have to take that extra supplement of numbers from somewhere. What are the choices available? If we take a supplement from the element in position i+2 or more, then the swaps would be more than 1 per each number supplement. So why don't we simply get what we want from the next number where we would have one swap per each number supplement? It doesn't matter if the next number goes negative, the sum in the end won't change. Now here is the part that I don't understand. Since we are dealing with matches, how can the negative amount of matches be represented in the real world? So if A[0] = 1 and A[1] = 2 and needed = 4 We would take 3 number supplements from A[1] so that would mean that A[0] = 4 and A[1] = -1 now what exactly is this -1 in the real world? How can Petya take a match that doesn't exist and put it in A[0]?

      finaledit:

      I finally got it. That negative number represents the amount of extra moves that you need to take from a position that is higher than i+1 in order to bring those number supplements to the position i+1.

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

I didn't lock my answer. then also my problem was hacked by someone.

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

    If your solution has passed the pretests , it can be hacked by anyone in your room who has locked his/her solution.

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

How to solve C?

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

    My solution is brute force, which I'm not quite sure whether it's correct or not but sounds "correct enough" to worth implementing.

    Let an be the number with n ones, so a1 = 1, a2 = 11, a3 = 111, ....

    Suppose we have the number n, satisfying ak ≤ n < ak + 1. We either try to represent n = p1ak + m1 for some p1, m1 such that 0 ≤ m1 < ak, or n = ak + 1 - p2ak - m2 for some p2, m2 such that 0 ≤ m2 < ak. In other words, put as many ak's as possible while leaving the result nonnegative, or otherwise put ak + 1 and negate the remaining number. We then take the minimum of number of ones used in each possibility.

    Thus we can induct downward, doubling the number of subproblems but reducing k by 1, or in other words cutting n by roughly a factor of 10. This gives a runtime of approximately , fast enough for our purposes. The "proof" of why we only need to test those two possibilities follows.

    We're wasting ones if we include any of ai with i ≥ k + 2; if we have some such ai, then we need at least eleven  - ai - 1 (or otherwise  - ai, but that's clearly useless) to bring the value close enough to n, and there we waste i + 11(i - 1) = 12i - 11 ones just to obtain the number ai - 11ai - 1 = 1. So the largest ai that might be included in n's representation is ak + 1.

    Moreover, since n < ak + 1, we cannot have two or more ak + 1 for a similar reason; the second ak + 1 must be negated with eleven  - ak. So we have at most one ak + 1. We can thus represent n = ak + 1 - m for some m.

    Now, the only way to get rid of the first digit of n is by including as many ak as possible, because the next alternative of including 9 ak - 1 uses too many ones. Thus the result: either we include as many ak as possible to n, or include as many ak as possible to m. Because I was uncertain which of these gives quicker result, I just coded both possibilities and took the minimum.

    Here's my submission: 6789561. Unfortunately it's not commented, and it's in Python which is not as popular as C++ for competitive programming. If you don't understand any, just point out and I'll try to explain.

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

      Thanks. Nice explanation. I saw some dp solution of this problem, but couldnt undestand it. How to solve C with dp?

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

        can you please explain these two lines in your code:

         dfs(n%next, (n/next)*cnt + v);
 dfs(next*10+1-n, v+cnt+1);

        and how did you come up with this idea ??

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

          Note that next contains the largest number in the form 111...1 that is less than n, and cnt is the number of 1s. (n is the number we try to find the minimum representation for, and v is the current count of 1s.)

          In the first line, we remove several next's from n, equivalent to finding a, b such that n = a·next + b with 0 ≤ b < next. Here, b is the remaining number; that is, n%next, and a is the number of times we subtract next from; that is, n/next. Thus the first line: continue the search, now by using b as the number, but by incrementing the number of ones by (n/next)*cnt.

          In the second line, we take the smallest 111...1 that is larger than n and subtract n from that number. This is equivalent to n = 111... 1 - m, where m is the remainder. Hence the second line: compute the case where the second number is m, or next*10+1-n, where the number of ones increase by cnt+1.

          Regarding how coollooc comes with this idea, clearly only said person can answer, although I guess the same idea as my explanation above is followed: try both cases.

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

i wonder how solution 6788320 passed pretests.
AFAIK, it should take n-1 inputs and wait for the nth one (which, ofcourse, will never come). so i think it should give either RE or ILE!

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

    Nice Observation !! Not sure of the reason !!

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

    Scanf fails to read the next integer, since there is no more input. It recognizes that input is over and won't wait for it. x remains uninitialized, and s.erase attempts to remove a garbage value. The chance of it removing the actual answer is about 1 in 4 billion, so it passes all test cases most of the time.

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

My solution for B was hacked , and it passed again after changing variables from long to long long .. :(

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

Please write a solution for this contest. It seemed interesting for some people. Especially problem B!

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

I saw a participant in the standings have -3 on a problem , but he had a submission in the queue during the system test .

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

weak pretest better than strong pretest . I hope all coming contests be like this round.

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

what is the best method for solving problem C ??

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

6791615 i don't know what's wrong ?

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

    num = tot/n ... In python 3.2 / denotes float division even if the operands are integers.

    For integer division you should use // instead of /

    Float division causes some problems due to round-off errors.

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

How to solve problem C? any suggestion pls....

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

    i have an idea to solve this problem, but i cannot make it recursive. here is my example:

    let k=34.

    • 1st way: from the largest number which has the same "number" in each poistion and still smaller than k, we add up to k.

    34=33+1

    • 2nd way: from the smallest number which has the same "number" in each position and still larger than k, we subtract down to k

    34=44-10

    • 3rd way: from the smallest number 111..1 which is still larger than k, we subtract down to k

    34=111-77

    now we can calculate the number of 1 we need to get k by calculate the number of 1 to get each addends. of course that the 3-way can also apply to each of addends.

    still, i cannot figure out when the recursive will stop. for example if k=22, obviously we have 22=11+11 and use four 1. but when k=99 we use 99=111-11-1 and use six 1. with larger k the calculation became more complex :(

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

      The second way is basically the first way, followed by the third way. For the third way, immediately follow it with the first way. This way, the remaining number will be roughly 10 times smaller (the largest 111...1 number less than it is at least one digit less). Stop the recursion by hardcoding the solutions for 1 to 11.

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

Is the editorial published?

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

    There are usually no editorials for Testing rounds, you can consider this round just being a bonus to other rated rounds. You can write one though and link it as an editorial to this contest.

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

I could not hack because I had not locked my solutions, but I was thinking that it is some fault in the new API! Oh no. i had hacked 15 solutions in #250 (div 2), so forgot that first stepping stone towards it is locking your own solutions.

Moral : Look before you leap.

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

Editorial please !

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

We've introduced API and now we want to test the system before Round 251.

did anyone try to use the API in this round? if so, can u give a brief idea as to what exactly u did (and how u did it)?

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

    I think the people who tested the system are not us but them.

    → Reply