Блог пользователя albertg

Автор albertg, 9 лет назад, По-русски

493A - Вася и футбол

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

493B - Вася и борьба

Надо делать то, что сказано в условии. Хранить двe vector-ы, в одном из них очки первого борца, а во втором — очки второго. Еще две переменные — в первом сумма всех очков, что дано в вводе, а во втором — кто выполнил последний прием. Если Sum всех не 0, то выводить номер борца, иначе пройти над векторами и проверить — имеются ли неравные элементы. При равенстве выводить ответ зависимо от того, кто выполнял последний прием.

493C - Вася и баскетбол

Храним один большой массив pair-ов — дистанция бросков и кто это выполнил. Сортируем весь этот массив, потом предлагаем, что все броски — трехочковые. Потом пройдем над массивом, и зависимо от второго элемента на одно уменьшаем наши очки на единицу и сравниваем с наилучшим ответом и при необходимости меняем. В самом конце выводим ответ.

493D - Вася и шахматы

Заметим, что если n — нечетное, то черные могут сделать симметричные шаги относительно центральной линии — победив таким образом. А если n — четное, то белые могут ставить ферзь на поле (1;2) (что лексикографически наименьший возможный ход), никогда не входить в первую строку, и победить.

493E - Вася и многочлен

Рассмотрим две случая. 1) t!=1 и 2) t=1.

1) Если наша функция — разная от константа, то а больше всех коэффициентов, и в ответ может быть только представление числа b в а-ичной системе счисления. Еще и надо проверить — является ли константа решением?

2) при t=1 надо быть осторожнее:

при 1 1 1: ответ inf,

при 1 1 n: ответ 0

при 1 а, а^x(x-натуральное): ответ 1

при других случаях P(1) больше всех коэффициентов.

Разбор задач Codeforces Round 281 (Div. 2)
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Super short editorial :)

Not necessarily a bad thing!

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

В самом конце выводим ответ.

А я думал не надо... Вот почему упала...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain the case 2 in E when input is of the form: 1 a b and b!=a^x , then how should we proceed , i couldnt get a short and general answer for this one...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can barely understand what you are saying. "reduce our glasses" what is glasses??

»
9 лет назад, # |
  Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Thanks for posting editorial so fast!

»
9 лет назад, # |
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.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Я один, кто задачу D решил вот так: "ой, как-то её быстро все решают, ну давайте вот такой иф зашлём. Если не зайдёт, подумаем ещё"?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну, там доказательство придумывается за 5 минут, все равно слишком просто

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Задача D - скажем так, не очень-то.  Я ее сдал не очень-то задумываясь, исходя из двух соображений. Во-первых - все ее сдают, почему бы и мне не сдать. Во-вторых, явно что-то связанное с четностью n, и тогда остается 2-3 варианта с учетом разбора в условии задачи. Мне еще не повезло, только третий вариант оказался правильным. В общем, полагаю, подобные задачи на угадывание правильного ответа из не очень-то большого количества возможных вариантов далеко не самый лучший жанр на олимпиадах.
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Таких трололо задач я и не видел нигде, разве что на первое апреля

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can somebody explain C, I cant understand what the editorial is saying

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Lets have a massive of pairs — distance and team. Sort this, then suggest that all shots are 3pt — shots. Lets go from first to last element of massive, and using information about second element of pair we can decrease our answer by one and compare our answer with answer founded before.

    P.S. Sorry for mistakes at this text :(

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thanks but that explanation is no better than the editorial. Sort on what?, decrease 'score', what score, or d? using 'information' how do we use it?

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        You may have 3 arrays and all must be sortet by number. 1 array — the distances first comand throws. 2 array — the distances second command throws. 3 array — 1 array + 2 array.

        So, the better distance is 0 or one of the number in 3 array.

        You may go along 3 array, and calculate the number of elements in 1 and 2 array, wich are greater than current 3 array element. (All greater elements will give command 3 points, other — 2 points)

        Sorry for my English=)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

оказывается, в Д надо было лекс. мин. ход выводить xD

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

russian translation needs to be edited. for A:

` ~~~~~

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

~~~~~

`

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Is contest rated?

»
9 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

I can't understand anything about problem E.

The editorial is awfully short and hardly understandable :(

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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/

    • »
      »
      »
      9 лет назад, # ^ |
      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 :)

»
9 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Ничего не понятно. Если вы действительно хотите помочь людям понять ваши задачи, а не отделаться от них, не могли бы вы хотя бы чуть-чуть поподробнее объяснить решения?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Автор не из России — поэтому у него проблемы с русским языком.

»
9 лет назад, # |
  Проголосовать: нравится 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?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

if your solution gets hacked does that mean it would def. fail system tests?

»
9 лет назад, # |
  Проголосовать: нравится 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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

»
9 лет назад, # |
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.

»
9 лет назад, # |
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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Can anyone explain the solution for E ???

»
9 лет назад, # |
  Проголосовать: нравится +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/

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Лаконично однако :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thank you for the explanation :)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    9 лет назад, # ^ |
    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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there an english version of the editorial?

I missed a case in problem E :'(

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

    • »
      »
      »
      6 лет назад, # ^ |
      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 ?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Блин, а как может игрок получить две красных карточки,6 тест?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Дело в том, что игрок не может получить 2 красные карточки, но Вася думает, что он сделал 2 фола, которые заслуживают красной карточке.

»
9 лет назад, # |
  Проголосовать: нравится -24 Проголосовать: не нравится

Разбор хреновый. Если n — нечетное, то черные могут симметрично относительно центральной линии — победив таким образов. Это русский человек писал? Я тоже так могу: ввиду того, что уже не есть, получается всегда опять как будто потому. Но только ежели затем и потому что.

»
9 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Мне кажется, в Е забыли написать про вариант 1, a, ay + a - 1, в котором тоже будет ответ 1, в таком случае функция P(x) = xy + a - 1, P(1) = a, P(a) = ay + a - 1

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Не забыл. Я сказал, если если t=1, то либо эти случая которые были написаны, либо P(1) больше всех коэффициентов, и этот случай разбирается как первый случай.

»
9 лет назад, # |
  Проголосовать: нравится 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?

»
9 лет назад, # |
  Проголосовать: нравится 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 :\

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can some one explain solution to question E please.

»
9 лет назад, # |
  Проголосовать: нравится 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.

»
8 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    8 лет назад, # ^ |
    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.

»
7 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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.