We need 2 arrays — for the first and second team, in which we must save "status" of the player — is he "clear", yellow carded or sent off. Then while inputing we must output the players name if he wasn't sent off, and after the event he must be sent off.
We need to vectors in which we will save points of first and second wrestlers, and two int-s, where we will save who made the last technique and what is the sum of all the numbers in the input. If the sum is not zero, we know the answer. Else we pass by the vectors, checking are there respective elements which are not equal. If yes — then we know the answer, else everything depends on who made the last technique.
We need an array of pairs — in each pair we save the distance and the number of team. Then we sort the array. Then we assume that all the throws bring 3 points. Then we pass by the array and one of our numbers we decrease on 1 (which one — it depends on the second element of array). Then we compare it with our answer. In the end — we print our answer.
If n is odd, then black can win white doing all the moves symetric by the central line. Else white can win putting his queen on (1,2) (which is the lexicographicly smallest place) and play symetricly — never using the first row.
Let's discuss 2 case. 1) t!=1 и 2) t=1.
1) If our function is not constant (n>=1) than a is greater all the coefficients, so the only polynom can be the number b — in the a-ary counting system. We must only check that one and constant function.
2)if t=1 must be careful:
in case 1 1 1: the answer is inf,
in case 1 1 n: the answer is 0
in case 1 а а^x(x-integer, x>0): the answer is 1
in the other cases P(1) is greater than other coefficients.
Super short editorial :)
Not necessarily a bad thing!
Can anyone explain the 2nd case in E when input is of the form: 1 a b, and b!=a^x ie a and b are some random numbers, how do we proceed in such a case. I couldnt derive a short and nice solution for this case.
Why u send this message 2 times?
By mistake i sent the first one in russian that didnt get posted..
No problems then)
Can you please explain D in little detail. Thank you in advance
Just do yourself for n = 2, 3, 4 ,5 ,6 and try to make white the winner. At the same time consider the fact that black is not dumb.
Thanks for posting editorial so fast!
97 minutes ago? What? Contest didn't even end by the time. Apparently that's a new feature to hide blogs, or you messed up.
Edit: Whoops, I messed up, sorry people.
*That's an old feature to hide blogs.
Is it contest too??? Why, problem D very simple, than A,B,C?
Because dynamic scoring...
Tests that I used to hack problem B:
4 1000000000 1000000000 1000000000 -1
2 1 -1
2 -1 1
6 1 2 1 -1 -1 -2
There were many testcases that can be used to hack B and C. Unfortunately, no one hacked my obviously wrong solution. :(
russian translation needs to be edited. for A:
` ~~~~~
Нам придется хранить два массива — для игроков хозяев и гостей. В каждом из них мы должны сохранять статусы игроков "чист", "желтая карточка" или статус "игрок удален". И с каждом вводом просто проверить — если игрок удален, то ничего не предпринимать, иначе менять его статус в зависимости от того какую карточку он получает и от его статуса. При получении красной карточки в любом статусе, или желтой, находясь в статусе "желтая карточка" игрок удаляется с поля, и печатается строка в стандартный вывод.
~~~~~
`
thank you ... I have edited it.
Is contest rated?
Why not?
I can't understand anything about problem E.
The editorial is awfully short and hardly understandable :(
For t!=1, P(P(t)) = b is just P(a) = b. Also recall that a polynomial looks like the base conversion formula, so we just convert b to base a (each digit in base a gives you the coefficient) and make sure the conversion works. Similarly, convert a to base t and make sure it works.
This breaks down for t=1 because you can't convert a to base 1, but when t=1, you can reduce it to a few cases and handle these individually. The case for t=1 is explained in more detail here: http://www.johndcook.com/blog/2012/03/27/polynomial-trick/
Polynomial need not always be a base conversion formula right ? P(a) can have coefficients >= a but base conversion has coefficients < a UPD : It can't. Because of the fact that P(t)=a :)
I submitted a correct solution at 37min for problem A. After that I submitted another correct solution at 1hour-20min for problem A. However the system skipped my first submission and accepted the second submission for testing. This affected the points earned. Is it possible to consider my first submision?
no read the rules
http://codeforces.net/blog/entry/456
Thanks. I resubmitted almost the same solution for the problem A after the announcement was made that:**You should output red cards in a chronological order. The statement will be updated soon**.
No.
hello, I need help, please.
I my submission of problem C. I get WA in test 11:
wrong answer 1st words differ - expected: '6:8', found: '0:0'But in my computer I get:
6:8Someone can explain me what happened?, pleaseTypo:
Which I only noticed when I tried compiling with -Wall -O and got a warning about BB being uninitialized.
aaaaaaaaaaaaaaaaaaaaaaa...
I corrected that and AC. :'-(
merolish thanks for your help.
I have submission on C with WA 3 8972083. Statements: "Print two numbers in the format a:b — the score that is possible considering the problem conditions where the result of subtraction a - b is maximum. If there are several such scores, find the one in which number a is maximum." Why on test:
answer is 15:10, but on test:
answer is 15:15. Why? Tests are similar.
a - b is maximum, not |a - b|.
Oh, I'm stupid and careless, thanks :)
Thank you for this interesting contest, statment of the problem A was a little bit fuzzy, I got it wrong answer twice during the contest, actually if a player got a red card, they would be sent off, and they properly won't continue playing, now I saw the test case which breaks my solution and it was
the same player is getting a red card twice, and that couldn't be true at all. It should be mentioned in the statment that, the player may receive multiple red cards
The player isn't receiving a red card twice. He committed a foul worth receiving a red card twice.
You're right, even though I read the problem statment many times, I couldn't get it . I wish the problem statment was more understandable, anyway it was my fault, I had to read the statment too carefully when I got it wrong.
If ever a foul can worth two red cards, they should be given at the same time.
My 'twice' refers to committing a foul.
Oh sorry, you are right.
This was a hint in problem statement:
Come on, people, are you really so silly?
Vasya is watching a recorded football match now and makes notes of all the fouls that he would give a card for. Help Vasya determine all the moments in time when players would be given red cards if Vasya were the judge. For each player, Vasya wants to know only the first moment of time when he would receive a red card from Vasya.
And it does make sense. Firstly he categorizes all fouls to yellow and red cards independently. And then he wants to know the time each player would be removed from the field if he would be a judge and give such cards sequence. And if a player was given a red card, he wouldn't get another card again from Vasya.
He should say it is not our known football. In football when a player takes red card he leaves match doesn't take red card again and again. Why didn't you say anything ?! Actually it is NOT football albertg.
He said if Vasya were the judge, the judge is not giving a red card, only Vasya believes that that foul is worth a red card, and so the player is not leaving the game, only Vasya believes that the player should leave.
Can anyone explain the solution for E ???
I believe this blog post will be helpful to many that are trying to understand the solution to E.
http://jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/
What about adaptive queries for guessing real valued coefficient polynomials?
for the explanation for problem C, what does "and one of our numbers we decrease on 1" mean?? kindly elaborate..
I can't understand the solution to problem C can anyone re explain it to me?
Well, I can explain my solution.
Basically, if you can try all values of D, and simulate the scores, you can find the answer, no?
And then you notice that only changing the value of D to a value in team A or team B will change the result. For example, if there are no shots taken between the distances of 10-15, a D of 12 will have the exact same result as a D of 13.
Thus, there are only 2*200000=4*10^5 possible values of D. Now, to simulate the number of points faster than linear time, you only need to search for the number of shots that are below D, and the number of shots that are above D for both teams. This can either be done through binary search, or keeping track of a pointer.
I hope this helps. I didn't solve this problem during the contest due to not realizing that the shot distances didn't need to be unique.
thank you for the explanation :)
Thanks Chili,
I look at your submitted solution (8973140) and found two things: 1) complexity of the solution is O(nlog(n) +mlog(m)) because of sorting of both arrays, so it in this sense, it doesn't really matter whether is the rest linear or binary search; 2) I didn't find binary search, instead there are two for loops up to n and m, making the remaining part is linear — so either I missed something in your code, or you didn't implement binary search.
"This can either be done through binary search, or keeping track of a pointer."
You can notice that the value of the binary search will never decrease, so you can simply keep track of the last index that works, and increment it until it works again.
My solution ends up being O(N) complexity.
I am sorry, but it cannot be O(N) complexity if you are talking about whole solution which uses sort procedures for input arrays. It is proven that lower bound for any deterministic comparison-based sort (which, I believe, is used in most libraries, and in your case as well) for arbitrary input is O(N log (N)): http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0130.pdf
Sorry, I messed up.
I forgot about the sorting portion of the problem.
I was simply meaning to explain that the pointer solution does not require any log N factor, so that other than the sort function, the solution is O(N).
Was trying to illustrate that I wasn't using binary search.
i too cant understand the logic behind C. please help. Atleast give a solution which implements the logic. You may post the code along with the tutorial. It will be helpful for beginners like me.
http://codeforces.net/contest/493/submission/8986100
Key observation is what chili mention, that we we only have to consider values of d in the space of the union of a and b's shot distances, not [0,upper(d)].
but in 1st test case, we have to take 0 as d and it is not in {A U B} space.
Is there an english version of the editorial?
I missed a case in problem E :'(
I wrote an editorial about problem E in Chinese. http://hzwer.com/5390.html
How did one arrive at the observation for problem D? Editorial is too short.
I arrived at it through induction. Basically, if white moves first on a board of size N to (1, 2), the resulting board is basically a board of size N-1, with the positions of black and white reversed.
So, a board of size 3 is black win if white goes first, but for a board of size 4, white can basically turn it into a board of size 3 with black going first.
I'll admit, my proof during the contest was watertight, but I wasn't quite sure how to proceed, so I tried my solution, and it ended up working.
I don't know whether to expect a reply or not, but can you extend this proof for n = 5 ? Or maybe can anyone else have a shot at trying to extend it for this case ?
Using the above method(of induction) ,it will be difficult to prove when n is ODD. I think that this method of induction works only for n =EVEN number and not for ODD number.For odd number ,some other method would be required.
What is wrong with my solution?I was trying to maximize the value of y-x, where y and x is number of shots lesser than chosen d value for the second and first team respectively.8989966 Thanks in advance.
There can be a situation in which there are 2 throws form the same distance. You must be careful in that case!
My submission for problem C ( 9005400 ) get Time Limit Exceeded as verdict in test case 1, but when I tested it in ideone ( here ), it passed with normal run time. Could somebody help me?
can anyone please why my solution(9017211) for A is being wrong on test 1 though it is showing correct answer in my compiler :\
Probably, the problem is with initialization of array "flag". You use falg[i][1] and flag[i][2], thus you need them to be initialized. But according to your code, you initialize only flag[i][0] and flag[i][1], so flag[i][2] is undefined.
Try to replace
for(j = 0; j < 2; j++)withfor(j = 0; j <= 2; j++)and I believe it'll be AC.Can some one explain solution to question E please.
When you look at this short editorials, you really see that the ideas which stands behind each problem, can be formulated in a few lines and it shows that it's simple.
Can C be solved using ternary search(on value of d)+binary search(to find the scores of teams a and b) ? I am getting WA, but I am curious to know if it is possible to do it this way.
Not but it can be done by binary search.
It is always optimal for the choice of d to be:
Let distances of the first team be array1, and the second team array2.
1) A value that is present in the first array. 2) A value that is present in the first array -1. 3) A value that is present in the second array. 4) A value that is present in the second array -1.
Sort array1 and array2.
Put all of these in a vector. Iterate on each value, and binary search on array1 to get the first value bigger than it. Multiply what is before it by 2 and what is after it by 3. Same goes for array2. ( Can easily be done by upper bound in C++ ).
Then just keep comparing and keep the optimal answer.
Runs in O((N+M)*(Log(N)+Log(M))) apart from sorting.
Hi All,
For the problem 493D — Vasya and Chess (Div2D/Div1B). I am a little confused with the explanation of the second sample input/output. The explanation goes like this (the part in bold is confusing me)-
In the second test from the statement if the white queen captures the green pawn located on the central vertical line, then it will be captured by the black queen during the next move. So the only move for the white player is to capture the green pawn located at (2, 1).
Similarly, the black queen doesn't have any other options but to capture the green pawn located at (2, 3), otherwise, if it goes to the middle vertical line, it will be captured by the white queen.
During the next move, the same thing happens — neither the white nor the black queen has other options rather than to capture green pawns situated above them. Thus, the white queen ends up on the square (3, 1), and the black queen ends up on the square (3, 3).
In this situation, the white queen has to capture any of the green pawns located on the middle vertical line, after that it will be captured by the black queen. Thus, the player who plays for the black queen wins
Now if I have understood it right, then it is possible for White Queen to win as well. Please can you help me understand why the answer provided by the author is the only possible solution?
I know it may be late, but check it out:
Help Vasya determine who wins if both players play with an optimal strategy on the board n × n.
It happens that, if the black plays optimally, he will "foresee" the white moves and won't do the move that leads the game to the alternative timeline you described.