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

Автор NBAH, история, 8 лет назад, По-русски

Всем привет!

11 августа в 19:35 MSK состоится рейтинговый раунд Codeforces #367 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

Автором задач являюсь я. Это мой первый раунд на Codeforces! Советую ознакомиться с условиями всех задач. Надеюсь каждый найдет себе задачу по вкусу.

Хочется выразить благодарность координатору раунда GlebsHP за помощь в подготовке контеста, Yury_Bandarchuk и IvanVan за помощь в подготовке задач и прорешивание раунда, а также MikeMirzayanov за замечательные платформы Codeforces и Polygon.

UPD: Разбалловка 500-1000-1500-2000-2500

UPD: Разбор

UPD: Соревнование завершено. Поздравляем победителей!

Div.1 winners:

1.anta

2.W4yneb0t

3.sugim48

4.uwi

5.Kmcode

Div.2 winners:

1.jiangzixiao

2.Shining

3.BurningHuie

4.AwD

5.stjepanp

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

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

Автокомментарий: текст был обновлен пользователем NBAH (предыдущая версия, новая версия, сравнить).

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

kiram to tarrahe in contest

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

Simple brief statement, thanks a lot and hope high rating change for everyone =D

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

And as usual... scoring will be announced later! (maybe just before the contest! or after the contest!) Whyyyyyyyyy?!

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

Hope this contest will be better than last Div2 only contest. Hope there won't be such a long queue during the contest because of so many people. (Hate the feeling knowing the contest is unrated after a 2hr-hardwork at midnight)

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

short GL & HF , I hope statement will be short as this :)

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

short GL & HF, I hope statement will be short as this :))

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

Hope for nice problems and strong pretests :)

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

    Could someone explain to me the reason for downvotes on this comment?

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

      It's Codeforces. You never know what happens to your comment.

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

        Well said Tweety. (y)

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

          Maybe you are new! but you can use up and down vote buttons instead of this comment!

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

            Well said TD. (y)

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

              In hindsight

              Maybe you are new! but you can use up and down vote buttons instead of this comment!

              FYI, I downvoted

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

                but downvoting others won't decrease your negative contributions.

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

                  I hope the community loves me again :) I wrote a lot of stupid downvote worthy stuff to earn -47. Guess I won't be doing that again.

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

                  actually we upvote a comment if it is useful, fun, interesting ,... and we downvote a comment if it is useless, spam, ugly,...

                  if you want upvote then interest us!

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

                  That's not how this works. You never know which comment will be upvoted and which ones will get downvoted.

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

            Downvote doesn't seem to work for me whenever I hit downvote the comment rating stays the same, is there any reason for this?

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

Today, give a stranger one of your smiles. It might be the only sunshine he sees all day.

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

I hope this round will be more interesting than previous one)

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

"Are we poisonous?" the young snake asked his mother. "Yes, dear," she replied — "Why do you ask?" "Cause I've just bitten my tongue! "

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

MSK means??

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

Round of div2 member?

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

Fact : 367 is a prime number

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

a round without the IOIers ?

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

Надеюсь никакой геометрии в С и адекватные D, E. Ну и конечно же без смакования момента после отправки решения до получения результата.

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

is it rated ??

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

I hope this contest won't have so many commercials for games and movies. Just clear tasks.

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

    You think the one about avengers was with help of commercials?, u think they ask codeforces community to create probs about them?..

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

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

Too late for Asia......

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

Randomness of likes and dislikes will one day be used as a random number generator :v

Like if you disagree :v

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

Today is Codeforces NBA match ;) Wow!! That's great to play on computer too. Thank u very much NBAH. Best of performance for everyone in this match :)

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

Is there anyone who could help me to solve this problem or give any other approach.Thanks in advance http://codeforces.me/blog/entry/46505

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

[user:jibancanyang]Come on,believe yourself,and tonight you must be the candidate master!

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

Anyone here knows how to unregister I'm not sure if I will be able to write codeforces today PELASE HELP

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

    Just don't submit anything or open page of participants >> find your handle >> click the red (X) button to the right of your handle to unregister yourself

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

    If you don't submit, your rating won't be affected.

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

We should wait 9 days for next contest :((

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

We should wait 9 days for next contest :((

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

The Olympic season is here and we have some Codeforces rounds scheduled too. We should have an Olympic themed contest.

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

Wish Good luck to all :)

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

Queue is back. :/

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

my source is still in queue for long time. does this happens to anyone else?

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

Codeforces queue :/ . Please do compensate for the time we have lost in this and are still losing.

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

queue 2 : the nightmare

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

make it unrated:/

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

Автокомментарий: текст был обновлен пользователем NBAH (предыдущая версия, новая версия, сравнить).

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

i hope it's not going to be unrated today!

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

i hope it's not going to be unrated again!

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

Auto comment: topic has been updated by NBAH (previous revision, new revision, compare).

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

20 pages of unjudged solutions

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

I guess it's another unrated contest, unfortunately.

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

I thought the queue problem was solved! I submitted B. Waited for 5 minutes, still in queue. Went to solve C, submitted C, found out B was WA. And now C has been on queue for 3 minutes. wtf! -_-
Thank god it's unrated for me. I'm out.

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

My solution to C is not even in the queue. I am not able to submit it! -_-

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

    Finally was able to submit by uploading the source file. I am having this problem since many days, not able to submit code that is copy-pasted in the editor.

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

Please, don't make it unrated.

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

    It would be unfair for participants who got WA after one hour. :/

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

      Who told you life is fair ;)

      Besides, it will be unfair to those who got their solutions judged in time. Its just like contest time. Some countries benefit from the time, some have troubles. You won't complain about that would you?

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

        if there's long queue, no one will get their solutions judged in time. and really a wa verdict after a long time makes it unfair for the contestant.

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

      R u sure u got wa after an hour? I really think what ur saying is false..All my submissions passed is <=10 mins...and just look at the number of people who solved each problems.. the stats say ur lying

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

      One hour :o ? I submitted program at 5min, 10min, 30min, and 70 mins. I had to wait for more then 5 mins for pretests only for 2nd (which was at 10 min) Rest all submissions were quick in judging (less then 5 mins for sure)

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

    Congrats, good work! ^==^'

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

Wow, really great curve of number solved. And this is only halfway through the contest.

a

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

Что-то баян задачи...

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

On a completely off topic, how many people on codeforces follow Silicon Valley (TV show) ?

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

    Well, I don't think you can get your answer if you ask this question here. After some yes/no, people will stop replying due to negative votes (spamming). You should rather create a poll externally and give the link here.

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

C was a dp problem right? I was starting to get it but I didn't have enough time to debug :(

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

    From the fact that it was called "Hard Problem" and that some people submitted it in 4 minutes, I am guessing there is a non DP solution but sadly I don't see it. Can anyone share their solution?

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

    Yup. You could view it as a graph problem and then it is finding the shortest path in dag from 1 to n that could be done in O(n + m) There are 2*n vertex and every vertex has max of 2 outgoing edges.

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

      I was considering representing it as a dag too. Thanks for the help.

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

    let's call l[i] is the list of strings and r[i] is reserved string of l[i]. Then we have dp[i][0] means min cost of list from 1->i that l[i] is not reserved, and dp[i][1] means l[i] is reserved. First dp[i][0] = Inf, if l[i] >= l[i-1] dp[i][0] = dp[i-1][0], if l[i] >= r[i-1] dp[i][0] = min(dp[i][0],dp[i-1][1]). Then dp[i][1] = Inf, if r[i] >= l[i-1] dp[i][1] = dp[i-1][0] + c[i], if r[i] >= r[i-1] dp[i][1] = min(dp[i][1],dp[i-1][1] + c[i]). Res = min(dp[n][0],dp[n][1]). If Res = Inf then Res = -1. That is my solution and it passed present test.

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

    I implemented a 1D DP solution. Here is the link to the solution.

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

I don't like man :P. When I get 20 minutes penalty and a WA just because I wrote a statement twice . :D

And by the way was it only me who took Manhattan distance in Problem A and passed 6 pretests? :D

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

Спасибо большое за интересные задачи!

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

Got response from judge after 20 min from submission.(long queue)

Also sad as i got to know it was wrong after 20 min. :(

Will this be a rated contest?

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

How to solve D? Thank you.

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

    I solved it using Trie

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

    It can be solved by trie, easily. I supposed that you know task to find the biggest xor of two elements in array ( you can find solution on internet easily too). Here you only need to story how many times you went through some node ( because sometime you must delete some edges).

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

    Look at Problem 1 in this article: Trie Tutorial

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

    In my solution we write every number in binary using 35 bits, we use leading zeroes if required.

    I let the map M[i,j] save how many integers x satisfy that when you only look at the bits in the first j positions you get i.

    Both updates and queries can be done in time

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

    Use Binary Trie.

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

    This is my idea, haven't tried it yet.

    Convert every input(number) to binary system. Put it in BST (1s go right, 0s go left). Make sure that all numbers in binary system are the same size. So 6 -> 110, but if max value is 1e9, it became 0000....110.

    When you search start from leftmost digit and go through BST and pick side different than current digit. When you reach the last node it's your answer.

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

      It looks like greedy solution, can you prove that it right in all cases?

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

      It's efficient for searching. But wouldn't it be hard when we're gonna do deleting operation on the tree?

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

        I would do same as search, when you reach last node, go up.

        while (true) {
          bool check = parent_has_one_child
          int digit = node_value
          go to parent
          delete child with value == digit
          if (!check) break;
        }
        
»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Wow, CF servers are fast, my first hack on this submission (19791945) takes over 5 × 109 iterations and it ran in sightly less than two seconds.

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

Had no idea Tries were this standard, so many people solved D.

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

I think my rating will drop to below 900 :/

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

Anyone else think that the time limit for E was a bit too strict?

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

    I don't know but if the target was split O(q(n + m)) and then it was not strict.

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

      There was a solution in q(n+m)? Wow... at least I managed to implement a working treap for the first time

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

        I wrote the same O(q*n*log n) with treaps as well. I think it was a bit too tempting to come up with some online algorithm that uses treaps of segment trees to fairy solve this problem.

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

        Yep, The good intuition to this solution represents the structure as beads that connecting by a thread with a neighborhood, in this case, you can split O(n + m) thread and connect it by another way.

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

          So, basically a quad-linked list? Thanks!

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

            Yes

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

              any full description of "quad-linked list"? is it smth like sqrt-decomposition of list? Google gives smth strange.

              Thanks in advance

              Tried treap but TA11:(

              UPD just wondering how the hell is possible to distinguish fast c++ qmlog(n) from slow java qm...

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

                Basically there is set of nodes representing the fields of the matrix. Each node is connected via a pointer to its upper, lower, left and right neighbor.

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

                  Statement that rectangles doesn't share common side makes so much more sense now ;) Actually I'm surprised that not much people came up with this solution, as it isn't complicated at all.

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

                  Ok thanks, already read it in solution, seems to me that coded something similar once

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

          Thanks! So trivial yet so hard to think!

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

      What about this O(QNM) solution?

      http://codeforces.me/contest/706/submission/19802812

      I know, this solution utilizes the fact that modern machines are very good at copying large amounts of memory around.

      This just proves that the time limit itself, although the problem and its solution are very interesting, doesn't make any sense.

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

This round is totaly interesting :) Although I couldn't solved problem D (wish that i could learn Trie earlier) but today it is fine!

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

That moment when ur solution is in queue for more than 15 min. And On top of that you get a verdict as a wrong answer . Ruins everything :(

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

i always thought that the feature of rejecting the exact same submission was useless. after this contest i really appreciate it. it saved lots of precious 50-points as i had to submit 10 solutions to see one of them got into the queue.

okay really codeforces what the fuck is happening!

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

i get WA after 30 min from submit ! :)
it should be unrated like Eran Contest

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

    yup...i got WA after 20 min of Submit.

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

      Same Here :(

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

      Yeah now lucky people who didn't get Wrong answer will vote down this comment :)

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

        if someone solved their solution correctly at one go, it doesnt make them lucky, it makes them more aware and smart

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

          they are smart because they didn't get WA ?
          they are smart yeah but they are lucky too because they don't wait 20 min and lose many points and resubmit solution also lose 50 point :)
          in 20 min i can solve B instead of fix small mistake in 'A' problem
          smart only isn't enough

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

Does anybody know why my submission 19801619 got compile error? Thank you!

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

the queue was so long in the start of this contest please consider this.

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

Who else has used graph to solve C?

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

I spent an hour implementing D using multiset, so I guess this will be my motivation to learn trie finally :D

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

I see many solutions who got WA#5 in problem D, like me. Good round!

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

I knew that the problem D could be solved by using Trie but I failed to implement it ;(

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

    same here...I had bugs in my remove number function...got it working 5 minutes after the contest ended. :(

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

    This is the second time I know that a problem can easily be solved by trie but failed to implement it. I think tries are tricky to implement so people must have coded them once and use their own code every time I guess.

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

Solved D 5 minutes after the contest ended! I'm too slow!

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

I think, this contest should be RATED.

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

I quite don't understand what everyone is so distraught by long queue of +/- 15 minutes. Every major competition. APIO 2016, CEOI 2016, JBOI 2015 all are really famous for their judging fuck ups. Why does CF need to make this unrated simply to prevent decrease of people's ratings, when such major competitions often end up deciding people's future and college etc.

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

    The competitions you mentioned don't have time penalties.
    When there are fuck-ups in our local onsite contests, we usually blame the system saying to the organizers that in respectful contests like Codeforces rounds such things would be considered very wrong and wouldn't be allowed. Codeforces should stay an example for a good platform with good contests.

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

It was a really bad idea to make Eran's contest unrated. Cuz now a lot of people are upset with the system's speed and it would be kind of unfair to leave it as it is.

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

E was very similar to problem G from Petrozavodsk Winter 2012 (standings)

(the problem is great anyway)

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

I think this contest should be rated. Judge lags were not bad than past contests.

umm... I wonder how to hack Q1. How did you hacked Question No.1?

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

Making this round rated proves how unserious this website is

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

Submissions are being judged after 20 minutes. I came to know about my run time Error of question after 20 minutes. This round should be unrated. Many people would have been affected by this.

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

What is the approach for D?

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

Any idea what Test 41 in A is? I assume it's one of the tests that was used to hack a bunch of solutions in A.

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

"In queue" for 15 minutes after submitting the question, has becomes a permanent feature of codeforces :(

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

Make it rated please i have solved A and B under 20 minutes. and i am happy to do that !

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

    19793914 00:20:53 Hazemzz A - Beru-taxi Java 8 Accepted 20 mins, 53 seconds is not ''under 20 minutes'' :)

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

      Make it rated please i have solved A and B under 20 minutes 54 seconds. and i am happy to do that ![user:latvian]

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

Nice contest! Brief statements. Unfortunately, finished D solution two minutes too late :/. Thoroughly enjoyable nonetheless.

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

In Problem C. I marked my dp[100005][2] with INF as 10e15 it gave a run time error. But when i use INF as 10e14 it works. Language used C++. Can anyone explain ? Thank you.

Edit1 : It's behaving in a weird manner. Sometimes i get correct answer but sometimes i get run time error in custom invocation. I will update once i get to know the reason behind it.

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

    There are 10^5 numbers, so if you add 10^15 10^5 times, you get long long overflow. Maybe that's why

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

    In c++ upto 1234567890123456789 is accepted(>1e18)..then its not possible that 1e15 will give any kind of runtime error :D Check again may be some kind of segmentation fault error must be there.

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

    Always better to keep it as -1 and then add additional checks :). I have made the same mistake before.

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

Only I get #WA41 on A?

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

    "Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed 1e-6."


    cout just give the answer that its absolute or relative error does not exceed 1e-5.

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

A solution for D without using trie (though it hasn't passed the systests yet). Let's store all numbers in STL multiset. To perform the third operation, we can find y that gives maximal xor going from the leftmost bit to the rightmost. Given the 10^9 constraint for x, 30 to 0 is enough. Let's say we know some binary prefix of the answer, and that a number in multiset with such binary prefix exists. If x has 1 in this bit, we can just find the the minimal y with such prefix (using multiset.lower_bound()), and if it has 1 in this bit, then add it to the answer. If x has 0 in this bit, we can find lower_bound(answer | (1 << i)) and see if it does exist and isn't greater than answer + (1 << (i + 1) — 1), in order to guarantee the existence of such prefix in multiset, then add to the answer.

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

It will be unfair towards Eran who has created good problems, if this contest is rated

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

    the lag in this contest wasnt as bad as the lag in the contest you are referring too, at most it was ~20 min, you could have moved on to some other question while it was in the queue

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

    No it won't. Just enjoy solving the good problems and stop complaining. The queue wasn't long enough for the contest to become unrated.

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

I got a weird WA61 on problem C. I am sure about the idea, and probably the WA is because of checking whether we can have an answer. Why is my check wrong?

I've changed the way for checking the possibility to have an answer and now have an AC. Does anybody know why did this happen?

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

O(nmq) solution for E. AC in 2464 ms =)

Can be improved to 2121 ms and 1669 ms with SSE.

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

Can we expect editorial today itself??

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

will there be an editorial ?

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

Here was my approach to D.

It is easy to keep up with the set by using std::set and std::map to count the multiplicities.

The real deal is how to deal with the query ?.

First, change the given number to binary. We notice that we can take the high-value digits greedily.

Therefore, we do the following. We set X as the optimal number in the set. Iterate through the bits 29 0. If the binary form of the given number is 0, we want 1 there. If not, we want 0 there. If there are no numbers in the set that satisfies this, we would have to go with alternate path.

Here's an example.

Assume that 111011, 011000, 101000, 000010 is in the set, and the original number is 001101. We want the first bit to be 1. Indeed, there are two such numbers — they are in the interval [32, 64). How do we check that there are numbers in that interval? By using lower_bound!

So we chose [32, 64). Now for the second bit we want 1 as well. Such numbers are in the interval [48, 64). We see that there is one. We want 0 to be the third bit, and such numbers are in the interval [48, 56). However, there are no numbers in that interval! Therefore, we would have to go with the third bit 1.

Continue this, and we would have our optimal X. Now compare ORIGIN XOR X and ORIGIN and return it. Complexity is

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

Kindly have a look at this test case generation program for Question 2 . I was unable to figure out why it was showing (invalid input verdict ) when I tried to hack this submission . (http://codeforces.me/contest/706/submission/[submission:19798157])

#include<bits/stdc++.h> using namespace std;

My code :

int main()
{
	int n=9;
	cout<<n<<endl;
	for(int i=1;i<=n-1;i++){
		cout<<i<<" ";
	}
	cout<<n;
	cout<<endl;
	int q=88888;
	cout<<q<<endl;
	for(int i=2;i<=q;i++)
	{
		cout<<2<<endl;
	}
	cout<<2;
	return 0;
}

Please comment below if any one know the reason. I don't want to do that mistake again. But I was unable to figure out my mistake. (http://codeforces.me/contest/706/hacks/246947/test)

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

Kindly have a look at this test case generation program for Question 2 . I was unable to figure out why it was showing (invalid input verdict ) when I tried to hack this submission . (http://codeforces.me/contest/706/submission/[submission:19798157])

My code :

#include<bits/stdc++.h> 
using namespace std;
int main()
{
	int n=99999;
	cout<<n<<endl;
	for(int i=1;i<=n-1;i++){
		cout<<i<<" ";
	}
	cout<<n;
	cout<<endl;
	int q=88888;
	cout<<q<<endl;
	for(int i=2;i<=q;i++)
	{
		cout<<2<<endl;
	}
	cout<<2;
	return 0;
}

Please comment below if any one know the reason. I don't want to do that mistake again. But I was unable to figure out my mistake. (http://codeforces.me/contest/706/hacks/246947/test)

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

in C anyone got WA in test case 18?

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

nice contest ,but slow system testing :P hoping to get high ratings

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

    Sum of lengths of strings <= 100000.

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

    The sum of lengths of all strings is at most 10^5, not the length of every string. So the worst case should contain all the strings with length , something like 315.

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

    Total length of all string is 1e5. Incase n = 1e5, length of each string is just 1. Totally it is O(n).

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

    It was given in the question that the total length of the strings won't exceed 10^5.

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

    Why did you change your comment? Nobody answered your question so far.

    The number of operations is linear because every string is compared a constant number of times.

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

Thank you guys for making this awesome contest.The difficulty of problems is moderate for Div.2 contestants and have great and beautiful "solved" distribution.I kept thinking and implementing the whole contest.It's really exciting and fun.

Some personal experience: I got 2 RE on D for missizing the trie node pool and got 1 WA on C for a typo.When I start to handle E, I first thought to cope with it by splay tree(considering the difficulty of previous rounds) and failed to finish it.Right after the contest I figured out a better way(maintaining the position of original elements and do some interval add/distract, which can be completed in O(n) time because there is no online requests).

Long queue appear again in this contest.I guess this is caused by problem A.Maybe the special judge part in A make the judging machine laggy.

This contest is made by and for Div.2, this is awesome.Although the difficulty may seems lower than previous Div.2s(finish 3 and you and done, finish 4 for a high rank,finish all to go Div.1 directly), but it is really enjoyable for Div.2 contestants.

Hope you guys can make more great contests.

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

    I don't hate this contest. I'm just expressing my bad opinion about the problemset, which I didn't enjoy, authors did their best anyway.

    I do not consider this contest as "good". Here's a yellow point of view:

    -A was okay, like normal A

    -B was such a standard task...

    -C yet another DP with same pattern. There was even a pretty similar problem on CF once.

    -D come on, "code a trie" problem. There are many such problems in the internet. Seriously, even "find maximum xor" typed in Google would probably result in finding the solution immediately.

    -E that was a fun one. Nah, just kidding :P If coding N treaps is a model solution, then wonderful problem 10/10. MrDindows did something awesome, check it out!

    I'm not saying this contest was bad. But IMHO this contest should have been an Educational Round.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      C yet another DP with same pattern. There was even a pretty similar problem on CF once. 
      

      Which one?

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

This problem set is so much interesting. Really I enjoyed it to much.

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

Somewhat structured and verbose code for D: http://pastebin.com/Md2EtNXF (submission)

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

Can someone tell me why my solution to C (java) timed out?

I saw some other recursive solutions also passing, so did I make some mistake in the implementation?

Here's the code : 19801924

Thanks.

Edit : I got my mistake.

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

Задача D. В варианте третьего запроса нужно найти максимум из ксоров данного числа и одного числа из множества. В тестах же возможен вариант, когда мы ни одно число из множества не берем. На мой взгляд это грубая ошибка условия.

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

    Это же эквивалентно тому, что мы берем число 0(по условию 0 всегда присутствует во множестве), а 0 xor x = x. Или я не так понял?

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

      Да, вы правы. Не заметил эту часть условия. Думал, множество пустое вначале. Прошу прощения за комментарий, содержащий неоправданную клевету.

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

Someone can help me? In problem D, I'm use basicly pointers, in my computer it is ok, but in CodeForces gives Runtime Error.

Submission

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

Why my all solution change to 'skipped' and I out of competition ?

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

Why I get different answers between custom invocation and problem test?

In 19790402 I got WA on test 79, However, I thought I got the correct answer when I used Custom Invocation.

What the problem is???

I passed this problem by replace %ld with %d, but I do want to know Why I get different answers between custom invocation and problem test?

By the way, I'm glad to know how to cause this WA, since I thought there is no different between %ld and %d in GNU G++11 5.10 :)

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

Got 141 points, wow!

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

Помогите пожалуйста. Почему на 11 тесте превышение по времени?( 706B - Интересный напиток

import java.util.*;

public class Main
{
	public static void main(String[] args)
	{	
		Scanner sc = new Scanner(System.in);
		String n1 = sc.nextLine();
		int n = Integer.parseInt(n1);
		String prices[] = new String[n];
	    prices = sc.nextLine().split(" ");
		String q1 = sc.nextLine();
		int q = Integer.parseInt(q1);
		String results[] = new String[q];
		for(int i=0;i<q;i++)
		{
			int sum = 0;
			String m1 = sc.nextLine();
			int m= Integer.parseInt(m1);
			for(String s:prices)
			{
				int k = Integer.parseInt(s);
				if(m>=k)
					sum++;
			}
			
			results[i] = String.valueOf(sum);
		}
		for(String res: results)
			System.out.println(res);
	}
}

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

Thanks for such a nice contest :)

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

where is the problem set ?