albertg's blog

By albertg, 9 years ago, translation, In English

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.

493C - Vasya and Basketball

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.

  • Vote: I like it
  • +11
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Super short editorial :)

Not necessarily a bad thing!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    Why u send this message 2 times?

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

    Can you please explain D in little detail. Thank you in advance

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

      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.

»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Thanks for posting editorial so fast!

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is it contest too??? Why, problem D very simple, than A,B,C?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

    There were many testcases that can be used to hack B and C. Unfortunately, no one hacked my obviously wrong solution. :(

»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

russian translation needs to be edited. for A:

` ~~~~~

Нам придется хранить два массива — для игроков хозяев и гостей. В каждом из них мы должны сохранять статусы игроков "чист", "желтая карточка" или статус "игрок удален". И с каждом вводом просто проверить — если игрок удален, то ничего не предпринимать, иначе менять его статус в зависимости от того какую карточку он получает и от его статуса. При получении красной карточки в любом статусе, или желтой, находясь в статусе "желтая карточка" игрок удаляется с поля, и печатается строка в стандартный вывод.

~~~~~

`

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Is contest rated?

»
9 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I can't understand anything about problem E.

The editorial is awfully short and hardly understandable :(

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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/

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

»
9 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
9 years ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

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

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

    The player isn't receiving a red card twice. He committed a foul worth receiving a red card twice.

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

      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.

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

      If ever a foul can worth two red cards, they should be given at the same time.

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

 How does a player get 2 red cards (problem A)? is it your common sense albertg?

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

    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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

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

Can anyone explain the solution for E ???

»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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/

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

    What about adaptive queries for guessing real valued coefficient polynomials?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for the explanation for problem C, what does "and one of our numbers we decrease on 1" mean?? kindly elaborate..

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't understand the solution to problem C can anyone re explain it to me?

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

    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.

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

      thank you for the explanation :)

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

      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.

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

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

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an english version of the editorial?

I missed a case in problem E :'(

»
9 years ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

I wrote an editorial about problem E in Chinese. http://hzwer.com/5390.html

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did one arrive at the observation for problem D? Editorial is too short.

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

    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.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ?

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

        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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    There can be a situation in which there are 2 throws form the same distance. You must be careful in that case!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please why my solution(9017211) for A is being wrong on test 1 though it is showing correct answer in my compiler :\

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

    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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some one explain solution to question E please.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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.