### albertg's blog

By albertg, 6 years ago, translation,

493A - Vasya and Football

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.

493B - Vasya and Wrestling

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.

493D - Vasya and Chess

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.

493E - Vasya and Polynomial

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.

• +11

 » 6 years ago, # | ← Rev. 2 →   +2 Super short editorial :)Not necessarily a bad thing!
 » 6 years ago, # |   0 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.
•  » » 6 years ago, # ^ |   0 Why u send this message 2 times?
•  » » » 6 years ago, # ^ |   0 By mistake i sent the first one in russian that didnt get posted..
•  » » » » 6 years ago, # ^ |   0 No problems then)
•  » » 7 months ago, # ^ |   0 Can you please explain D in little detail. Thank you in advance
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 4 months ago, # ^ |   0 Thanks buddy!
 » 6 years ago, # |   +12 Thanks for posting editorial so fast!
 » 6 years ago, # | ← Rev. 2 →   0 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.
•  » » 6 years ago, # ^ |   +4 *That's an old feature to hide blogs.
 » 6 years ago, # |   +3 Is it contest too??? Why, problem D very simple, than A,B,C?
•  » » 6 years ago, # ^ |   +1 Because dynamic scoring...
 » 6 years ago, # | ← Rev. 2 →   0 Tests that I used to hack problem B:4 1000000000 1000000000 1000000000 -12 1 -12 -1 16 1 2 1 -1 -1 -2
•  » » 6 years ago, # ^ |   0 There were many testcases that can be used to hack B and C. Unfortunately, no one hacked my obviously wrong solution. :(
 » 6 years ago, # | ← Rev. 3 →   0 russian translation needs to be edited. for A: ~~~~~Нам придется хранить два массива — для игроков хозяев и гостей. В каждом из них мы должны сохранять статусы игроков "чист", "желтая карточка" или статус "игрок удален". И с каждом вводом просто проверить — если игрок удален, то ничего не предпринимать, иначе менять его статус в зависимости от того какую карточку он получает и от его статуса. При получении красной карточки в любом статусе, или желтой, находясь в статусе "желтая карточка" игрок удаляется с поля, и печатается строка в стандартный вывод.~~~~~
•  » » 6 years ago, # ^ |   0 can you explain C?
•  » » 6 years ago, # ^ |   0 thank you ... I have edited it.
 » 6 years ago, # |   -6 Is contest rated?
•  » » 6 years ago, # ^ |   +1 Why not?
 » 6 years ago, # |   +33 I can't understand anything about problem E.The editorial is awfully short and hardly understandable :(
•  » » 6 years ago, # ^ |   +16 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/
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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 :)
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ |   +6 no read the ruleshttp://codeforces.com/blog/entry/456
•  » » » 6 years ago, # ^ |   0 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**.
•  » » 6 years ago, # ^ |   0 No.
 » 6 years ago, # |   0 Where in DIV-2 C problem statement it is specified that any team can be considered winner/first? Problem statement "advantage of the points scored by the first team" and in input section it is n is "— the number of throws of the first team". Isn't problem statement tells that team with 'n' throws is first team?
 » 6 years ago, # |   0 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:8 Someone can explain me what happened?, please
•  » » 6 years ago, # ^ |   0 Typo: ll AA, BB; AA = BB == -1; Which I only noticed when I tried compiling with -Wall -O and got a warning about BB being uninitialized.
•  » » » 6 years ago, # ^ |   0 aaaaaaaaaaaaaaaaaaaaaaa...I corrected that and AC. :'-(merolish thanks for your help.
•  » » 4 years ago, # ^ |   0 Your code might exist some error,your compiler is different from the system judge.
 » 6 years ago, # | ← Rev. 3 →   0 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: 5 6 7 8 9 10 5 1 2 3 4 5 answer is 15:10, but on test: 5 1 2 3 4 5 5 6 7 8 9 10 answer is 15:15. Why? Tests are similar.
•  » » 6 years ago, # ^ |   +9 a - b is maximum, not |a - b|.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 Oh, I'm stupid and careless, thanks :)
 » 6 years ago, # | ← Rev. 4 →   +9 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  TANC XNCOR 2 15 h 27 r 28 h 27 r 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
•  » » 6 years ago, # ^ |   0 The player isn't receiving a red card twice. He committed a foul worth receiving a red card twice.
•  » » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 If ever a foul can worth two red cards, they should be given at the same time.
•  » » » » 6 years ago, # ^ |   0 My 'twice' refers to committing a foul.
•  » » » » » 6 years ago, # ^ |   0 Oh sorry, you are right.
 » 6 years ago, # |   +4 How does a player get 2 red cards (problem A)? is it your common sense albertg?
•  » » 6 years ago, # ^ |   0 This was a hint in problem statement: Vasya wants to know only the first moment of time when he would receive a red card from Vasya.
•  » » 6 years ago, # ^ |   +16 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.
•  » » 6 years ago, # ^ |   -10 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.
•  » » » 6 years ago, # ^ |   +5 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.
 » 6 years ago, # |   +11 Can anyone explain the solution for E ???
 » 6 years ago, # |   +19 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/
•  » » 6 years ago, # ^ |   0 What about adaptive queries for guessing real valued coefficient polynomials?
•  » » 6 years ago, # ^ |   0 Thank you so much! this blog have a great method to find coefficients and now i can resolve the E problem :)
 » 6 years ago, # |   0 for the explanation for problem C, what does "and one of our numbers we decrease on 1" mean?? kindly elaborate..
 » 6 years ago, # |   0 I can't understand the solution to problem C can anyone re explain it to me?
•  » » 6 years ago, # ^ |   0 i cant understand it eighter
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 thank you for the explanation :)
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   0 "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.
•  » » » » » 6 years ago, # ^ |   +5 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
•  » » » » » » 6 years ago, # ^ |   0 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 6 years ago, # ^ |   0 http://codeforces.com/contest/493/submission/8986100Key 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)].
•  » » » » 2 months ago, # ^ |   0 but in 1st test case, we have to take 0 as d and it is not in {A U B} space.
 » 6 years ago, # |   0 Is there an english version of the editorial?I missed a case in problem E :'(
 » 6 years ago, # |   0 I am getting wrong answer on testcase 53.i m not getting it. problem B
 » 6 years ago, # | ← Rev. 2 →   +12 I wrote an editorial about problem E in Chinese. http://hzwer.com/5390.html
 » 6 years ago, # |   0 How did one arrive at the observation for problem D? Editorial is too short.
•  » » 6 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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 ?
•  » » » » 13 months ago, # ^ |   0 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.
 » 6 years ago, # |   0 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.
•  » » 6 years ago, # ^ |   0 There can be a situation in which there are 2 throws form the same distance. You must be careful in that case!
 » 6 years ago, # |   0 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?
 » 6 years ago, # |   0 can anyone please why my solution(9017211) for A is being wrong on test 1 though it is showing correct answer in my compiler :\
•  » » 6 years ago, # ^ |   0 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++) with for(j = 0; j <= 2; j++) and I believe it'll be AC.
•  » » » 6 years ago, # ^ |   0 Indeed... :) Thanks..!!! Got ac :)
 » 6 years ago, # |   0 Can some one explain solution to question E please.
 » 6 years ago, # |   0 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.
 » 5 years ago, # |   0 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.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 3 months ago, # ^ |   0 Ternary search is applicable only on unimodal functions and here we can clearly see that f(d) is not unimodal.
 » 4 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 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.can any one explain this line -> checking are there respective elements which are not equal. If yes — then we know the answer