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.
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 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.
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 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 fromi+1
th index.even if
i+1
doesnt contain enough, it will become negative temporarily, but later it will take whatever it needs fromi+2
.this process will go on until
n-1
takes (or gives) something fromn
. after this last operation, all boxes will contain same number of matches.PS: be careful of integer overflow (use
long long
instead ofint
)!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 numberArray[i]
which is less than or more than theneeded
number. The additions or subtractions that we need to make in order to makeArray[i] = needed
is equals toabs(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 positioni+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 ifA[0] = 1
andA[1] = 2
andneeded = 4
We would take 3 number supplements fromA[1]
so that would mean thatA[0] = 4
andA[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 inA[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 positioni+1
.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 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.
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 thann
, andcnt
is the number of 1s. (n
is the number we try to find the minimum representation for, andv
is the current count of 1s.)In the first line, we remove several
next
's fromn
, 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 subtractnext
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 subtractn
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, ornext*10+1-n
, where the number of ones increase bycnt+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 then
th one (which, ofcourse, will never come). so i think it should give either RE or ILE!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 k34=111-77
now we can calculate the number of
1
we need to getk
by calculate the number of1
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 four1
. but when k=99 we use99=111-11-1
and use six1
. 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 API in 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.