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.

This contest give points to the rankings?

`It will be unofficial unrated round.`

ok, thanks

Why do not you read blog clearly?

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

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

Wish you luck everybody

a

when trying to register, i get the following message:

"You are registering

out of competition, reason: rating should be between0and1699in order to register for the contest"this makes me assume that there is some difference if participant is

Div-1orDiv-2at start of the round.but i guess there shouldn't be, coz this is only a

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

For fear of too much hacking maybe.

I think so

I am unable to register/participate :(

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

What was approach to solve Problem B?

when ur at

`i`

th index, just keep taking (or giving) the required number of matches from`i+1`

th index.even if

`i+1`

doesnt contain enough, it will become negativetemporarily, 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`

)!Thanks.

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`

.Spreading the wealth,OVa 11300

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

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

How to solve C?

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

a_{n}be the number withnones, soa_{1}= 1,a_{2}= 11,a_{3}= 111, ....Suppose we have the number

n, satisfyinga_{k}≤n<a_{k + 1}. We either try to representn=p_{1}a_{k}+m_{1}for somep_{1},m_{1}such that 0 ≤m_{1}<a_{k}, orn=a_{k + 1}-p_{2}a_{k}-m_{2}for somep_{2},m_{2}such that 0 ≤m_{2}<a_{k}. In other words, put as manya_{k}'s as possible while leaving the result nonnegative, or otherwise puta_{k + 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

kby 1, or in other words cuttingnby 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

a_{i}withi≥k+ 2; if we have some sucha_{i}, then we need at least eleven -a_{i - 1}(or otherwise -a_{i}, but that's clearly useless) to bring the value close enough ton, and there we wastei+ 11(i- 1) = 12i- 11 ones just to obtain the numbera_{i}- 11a_{i - 1}= 1. So the largesta_{i}that might be included inn's representation isa_{k + 1}.Moreover, since

n<a_{k + 1}, we cannot have two or morea_{k + 1}for a similar reason; the seconda_{k + 1}must be negated with eleven -a_{k}. So we have at most onea_{k + 1}. We can thus representn=a_{k + 1}-mfor somem.Now, the only way to get rid of the first digit of

nis by including as manya_{k}as possible, because the next alternative of including 9a_{k - 1}uses too many ones. Thus the result: either we include as manya_{k}as possible ton, or include as manya_{k}as possible tom. 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.

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

can you please explain these two lines in your code:

and how did you come up with this idea ??

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 findinga,bsuch thatn=a·next+bwith 0 ≤b<next. Here,bis the remaining number; that is,`n%next`

, andais the number of times we subtract`next`

from; that is,`n/next`

. Thus the first line: continue the search, now by usingbas 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 ton= 111... 1 -m, wheremis the remainder. Hence the second line: compute the case where the second number ism, 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.

i wonder how solution 6788320 passed pretests.

AFAIK, it should take

`n-1`

inputs and wait for the`n`

th one (which, ofcourse, will never come). so i think it should give eitherREorILE!Nice Observation !! Not sure of the reason !!

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.

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

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

Did you mean Editorial?

I'm sorry yes. I meant editorial. I was in a hurry so i wrote the incorrect word.

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

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

weak pretest contest more challenge contest than other contests

what is the best method for solving problem C ??

6791615 i don't know what's wrong ?

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

Accepted! thanks shawkat again :D

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

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

let

`k=34`

.`34=33+1`

`34=44-10`

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

Is the editorial published?

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.

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.

Editorial please !

did anyone try to use the

APIin this round? if so, can u give a brief idea as to what exactly u did (and how u did it)?I think the people who tested the system are not us but them.