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

Автор havaliza, 11 лет назад, перевод, По-русски

Всем привет! :{

Мы очень рады пригласить Вас поучаствовать в очередном Codeforces Round #173, который был подготовлен A.K.Goharshady, LGM и мной (havaliza). Я хочу традиционно поблагодарить Gerald, MikeMirzayanov и Delinur за помощь в подготовке раунда. Также большое спасибо dani1373, hhoomn, mruxim, MMJ и xorfire. Они тестировали задачи и в целом очень сильно нам помогли.

Кстати, сегодня день рождения у LGM's, а вчера был у gpac's. Давайте поздравим с днем рождения этих ребят! ^.^

Я надеюсь вам понравится сегодняшний раунд, и вы получите от него много фана! :)

  • Проголосовать: нравится
  • +279
  • Проголосовать: не нравится

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

Happy Birthday!!!

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

Hi. And tomorrow is my birthday. Hope to have a good contest to enjoy my birthday much more. :D

And Happy Birthday you guys. Glad to know it. Wish you bests in whole LIFE.

HF & GL!

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

I want to participate,but I'm too tired:(

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

Happy birthday to you guys(LGM,gpac,S.HASHEMI)!!! ^.^ and also Congratulations to havaliza,keivan,fab,dani1373 ,because of being selected for IOI team of IRAN for next year!!! hope you win 4 gold medals for IRAN!!!

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

Your prev contest was great! (at least for me!) I hope it will be like the prev! How is score distribution?

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

I was surprised a lot! thank you havaliza :)

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

happy birthday boys <:-P And special thanks for preparing the contest :-)

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

A bunch of Problemsetters from IRAN :D

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

Happy Birthday

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

Happy Birthday guys :) god bless you !!

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

wow! More than 3000 registered users :D .

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

please tell us about score distribution ?

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

Коль скоро почти никто не читает эту часть, я повторю, что Битландцы довольно необычные. У них свои работы, своя методика работы, свои жизни, свои сосиски и свои игры!

Вот так наркомания...

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

Срочно задача С: тест два — там опечатка или нет?

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

    А что там не так? Вроде всё верно. Строки могут иметь разную длину.

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

...d

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

Problem B: jury solution for test 3 1000 0 998 2 503 497

is "222". W T F???

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

Who solved D and how?

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

    For n=1 the situation is clear. For n=2 (two non-zero integers) if a[0]=a[1], first player wins, elsewhere he loses. For n=3 (three non-zero numbers) there are (300^3)/6 possible situations (excluding permutations of those), and for each of them we can calculate if the first player wins or loses in O(1).

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

      in testcase 2 1 5 your solution is wrong. because first player can make situation 1 2 which is bad for the second player and first will win

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

      2 2 3

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

      I think you meant vice versa for case n=2. didn't you?

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

      if n=2 you are logically wrong

      because if a[0]!=a[1] you said that second is winner but the first player can make a move that makes also a[0]!=a[1] then and become the second then he is winner , so how become both first and second winners?

      e.g

      let n=2 , a[0]=1 , a[1]=3

      the first is the winner and the winning move is subtract 1 from a[1]

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

    Use dp[i][j][k] to stand for whether (i,j,k) is a state in which the first person will win. It can be easily proved that the number of (i,j,k) such that dp[i][j][k] is false is O(n^2). We can use dp[i][j][k]=false to update dp[i+t][j+t][k+t] dp[i+t][j][k] dp[i][j+t][k] dp[i][j][k+t]. And it takes O(n). So we can get an O(n^3) solution by this way.

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

      May you please give further explanation about the O(N^2) bound on losing situations (i,j,k) ?

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

        Because if (i,k,j) is false than (i',j,k) is true when i'>i, which means the number of tuples (i,j,k) that is false is O(1) for each pair (j,k).As there is O(n^2) such pair (j,k), it is obvious that the number of tuples (i,j,k) that is false is O(n^2).

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

    My submission 3308449

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

How to solve E?

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

I notice a code will get TLE so I make generation to this testcase

string a="";
for (int i = 0; i < 1000000; ++i){
  a+='1';
}
cout<<a<<endl;
cout<<a;

so what's wrong he till me Invalid Input

FAIL Input can't contain two or more consecutive spaces, but line 31 (1-based) contains [validator wfval.exe returns exit code 3]

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

It is really hard to solve problems in Java, and Petr is really great, because he uses Java and he is the fastest coder.

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

    Come on mate , This should have been well thought before taking petr as prefix in your handle. Now you are expected to code in Java :P

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

Problem C was very interesting....a lot of people's solutions ( and also my solution!! ) has been hacked

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

    I hacked 2 user with this testcase:

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

    Very simple problem, but it has some pitfalls.

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

    Why do you have this weird if statement in your code?

    if ( yek1 >= ceil((float)yek2/(float)2) ){...}
    

    After some analysis you will know that one can construct every string(except a '0'-string that consists only of '0's), iff we have at least one '1' in our string.

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

      Yes, I think i was very lucky that my solution has been hacked, because my algorithm has a lot of bugs and finally I found the answer!!

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

        I hoped my soloution had been hacked too, then I could submit the correct one... Grammere jomlam dorost bud??

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

нет, ребята, так пить нельзя. Только решая Е вспомнил что такое на самом деле xor и переделал С) в результате сдал одну задачу через 3 минуты после начала и одну за 3 минуты до конца. Пора менять систему подготовки к раунду

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

I'm waiting system testing, for lunch!!! Please, hurry up... :D

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

Deleted.

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

И пусть этот момент длится вечно :D

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

XOR — фишка контестов на Codeforces:)

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

Testcase for problem C is to much (about 100 test). Systest will run very low.

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

Great Contest! I realy Liked problems D and E even though i didn't solve them

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

А возможно ли глянуть тест, на котором свалился?

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

Today during the contest I got two messages from MIT_1996 who was in my room, asking for help in problem B with algorithm. Where should I report ??

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

    i think you should forgive him and not report this.

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

    You could have asked where to report a dishonesty without saying the name of the competitor in public chat. Is not a good practice to a shame people for such reasons in front of all.

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

thx! very nice contest:)

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

Появился вопрос. Отправил решение С. WA3.
3303367

Забыл дать начальное объявление переменным f, g. Задал. AC.
3304751

Вопрос: По какому принципу в с++ задается начальное значение переменным?

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

    Вроде бы случайным образом.

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

      То есть если не задать начальное значение, то на одном тесте можно получить несколько ответов?

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

        Конечно, странно что с таким опытом соревнований, Вы еще этого не заметили о_о

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

        Даже хуже: в Visual Studio ответ будет зависеть от режима компиляции -- Debug или Release. В Debug значение хоть и будет мусорным, но стабильно одним и тем же, что может создать иллюзию правильности работы программы, а в Release раз от раза разным. Соответственно, если контестер проверяет решение, скомпилировав его в Realease, то ответ в контестере и локально может быть разным. (Навеяно недавним опытом по поиску ошибки в решении одного из моих олимпиадников. Решение проходило все наши тесты, а на контестере ловило огромное количество WA. Помог анализ кода и соображалка -- дело оказалось в значениях по-умолчанию. См. выше.)

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

          Да просто надо отучиваться от паскаля и объявлять переменные по мере необходимости, а не в начале программы.

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

            Всё верно. Лично я так делаю давно и подобных ошибок не получаю. И постоянно на эту тему делаю замечания. Но что делать тем кто учится по дурацким учебникам C++ или кого так учат...

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

              Да учитель ништяковый, просто обычно объявляю в глобальной, а там таких проблем нет.

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

    Все глобальные переменные изначально инициализируются нулями(это верно для g++, про VS ничего не могу сказать). Если переменная локальная, то, вроде бы, радномно

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

    Глобальные переменные обнуляются, локальные — нет.

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

Правильно ли я понял, что тут http://www.codeforces.ru/blog/entry/6954#comment-125915 человек выложил решение задачи E до конца контеста?

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

    Но зачем?

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

      Это загадка.

      Кстати нашел некоторых, кто воспользовался этим. Интересно, как на это смотрит жюри? Ведь тот кто скопирвал не виноват, в том что просто увидел решение и решил проверить.

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

        Те, кто скопировал, виноваты ровно на столько же, сколь и тот, кто заспойлил решение. Мы тут занимаемся спортивным программированием, а в спорте есть такое понятие — fairplay. Ну и совесть, конечно же.

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

That was a nice contest, thanks to havaliza and happy birthday to LGM and gpac...

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

I cant't exactly understand the meaning of problem E ! We are asked to find the maximum of what ? (BitHaval and BitAryo) what does 'and' mean here?

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

very good contest but I think test 26 from problem D should be in pretest , so many person got WA due to this test , thanks.

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

that was a nice contest thanks to havaliza but why Bitlandians are weird they are amazing

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

Thats funny. I solved my solution using Delphi compiler: http://codeforces.com/contest/282/submission/3302945 The same code, using FPC: http://codeforces.com/contest/282/submission/3311282

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

    Thats not funny I think... :D exactly like the diffrence between visual studio compiler and GNU...

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

      Something i have experienced while using CodeBlock for C++ and G++ compiler !!

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

.

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

When will the plus and minuses appear on the graph???

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

painting eggs is a very ancient and attractive custom in Iran and the children still do this

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

Very nice problems. Thanks to authors!

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

Люди, во многих решениях задачи D я для случая n=3 видел выражение a[0]^a[1]^a[2]. Выходит, в этом случае игра превращается в обычный ним. Но плиз, объясните, почему.

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

    Черт, во время контеста разобрал случай для н=2. Надо было для 3х послать ним. Ждем разбора, чтоб узнать, почему это работает.

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

    Например, это можно доказать вот так.

    Достаточно показать, что из тройки с неулевым XOR-ом можно попасть в тройку с нулевым, а из тройки с нулевым нельзя попасть в другую тройку с нулевым. Очевидно, что это и есть требуемое.

    Из тройки с ненулевым XOR-ом можно попасть в тройку с нулевым также, как в случае нима.

    Из тройки с нулевым XOR-ом можно пойти или как в ниме, то есть в ненулевой XOR, либо из тройки a, b, c (a xor b xor c = 0) в тройку a — x, b — x, c — x (x > 0).

    Предположим, что (a — x) xor (b — x) xor (c — x) = 0. Так как a xor b xor c = 0, то последние биты a, b, c либо две единицы и ноль, либо три нуля. Аналогично c (a — x), (b — x), (c — x). Отсюда легко понять, что последний бит x нулевой. Аналогично второй с конца бит x нулевой и так далее.

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

Да конечно контест был довольно интересен но будет ли рейтинг обновлен?

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

Happy birthday to all of you guys (gpac, LGM and S.HASHEMI)!!! and I hope that we get 4 Gold medals from havaliza, dani1373, fab and keivan!

The contest was very cool! Thank you for problems.

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

This is now 4 hours after contest but ratings had not changed yet... when does it want to change?? And I am right here in the site since the contest started... :D

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

Has anyone solved problem 'E' without a trie or with a easier solution to implement ?

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

    I have no idea what this does, but it looks suspicious: http://www.codeforces.com/contest/282/submission/3303893

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

      It seems to be the same ideia using trie. However, the code is a lot more clear and simply.

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

    Well, what I did was following: I replaced the given array by an array, where . BTW, The given array was a[1..n], I just added the 0th element to indicate we didn't give the first person anything to eat. Now imagine we gave the first person a piece [0..l] (it is equivalent to [1..l]) and the second — [r..n]. Then the tasty value of this is . We can replace the value r - 1 to m. Now we want to maximize . Notice two things: 1) l and m is the only variables since n is fixed, 2) 0 ≤ l ≤ m ≤ n. Then just sort the array s and then for any 0 ≤ m ≤ n use binary search for digits in the binary representation of to find l. Total complexity is .
    My submission: 3304910

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

i think this my solution still wrong, but get accepted http://codeforces.com/contest/282/submission/3309655

because 'is' never change,

and did this solution true after i add is++? http://codeforces.com/contest/282/submission/3312416

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

Problem D was a nice DP problem. I calculated the losing scenarios offline and found a formula for it. Then just applied the formula and solve the problem in O(1). It was very fun. Problem E was a very nice problem too. I scratched my head for a little while to make it run in time, until I thought of building a trie, and I really like building tries :)

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

Thanks for really interesting problems! But what mean's verdict Skipped? My solve of problem C — XOR and OR received Accepted in final tests. I see Skipped and only two solved problems today.

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

    hmm this is weird thing..happened to one once. let see if someone can explain it

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

I was actually shocked that problem B had a greedy solution to it. I was trying so hard to partition the numbers :P. But after end of competition when i saw some solutions which had got accepted i was surprised and confused. But then i came up with an inductive proof for the greedy method. Had fun. Will have to improve myself.

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

    I thought about knapsack problem,but when i saw many accepted code I wrote greedy solution.Now i know why this solution is correct(with an inductive proof,as you say).

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

I love this contest.