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

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

Всем привет!

Приглашаю вас принять участие в Codeforces Round #260(div. 1 and div. 2), который начнётся 8 августа в 19:30 по московскому времени.

Задачи были подготовлены мной, netman и randrew. Это наш первый раунд и мы очень надеемся, что он вам понравится).

Большое спасибо Gerald, CherryTree, vlad107 и dimad за помощь в подготовке раунда и MikeMirzayanov за создание Codeforces и Polygon.

Удачи всем!

UPD. Распределение баллов для первого и второго дивизиона будет таким 500-1000-1500-2000-2500

UPD. Приносим извинения за большую очередь в конце соревнования.

UPD. Поздравляем победителей.

Div. 1

  1. tourist

  2. cgy4ever

  3. LayCurse

  4. ecnerwala

  5. snuke

Div. 2

  1. allthecode

  2. gotowork

  3. SMAKH

  4. saikrishna17394

  5. PashaChemerys

Разбор на русском

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

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

Здорово! Раунд новых авторов, тем более от земляков) Думаю, будут хорошие задачи.

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

    А если бы они не были земляками Вашими, то раунд не удался бы?

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

Хороших начинаний Вам!

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

It's good to see new problem setters coming up with DIV1 rounds at their first appearance :)

Thanks to Mediocrity,netman & randrew. We expect more DIV1 rounds from you :) :)

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

The first time so early I am.

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

Hope Strong Pretests :D

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

Hope Strong Pretests :D

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

    Hahaha so much hate for you

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

    Why there is so difference two people with exactly same comments but one has 65 upvotes while other -16 downvotes !

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится
      • I simply copy the statement of the above floor, it is a spam in some sense.
      • I do not add strong pretest in my round, and ask for strong pretest in other round...
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Sorry for personal question, but I was always curious are you really Chinese girl or you're a boy who just puts girl face (as well as pictures from anime, cartoons, whatever) instead of their real profile picture? I think, that's pretty big disadvantage of English that you cannot understand the sex of the person when he tells something.

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

netman,(one of the authors of today's contest) you profile is very inspiring. starting from CF 105 div2, minimum rating 1105 at 143 div2 and then a story to tell everyone the secret of reaching 2192 at round 259 div1 ! its really amazing to see rising someone from the very beginning with his passion and practice that reminds me my lack of effort to attain that level. Wish you more and more success:)

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

    he is just 8 rating away from becoming Grandmaster. let's hope that he can achieve this in the next round. :)
    seriously, downvotes for wishing a participant good luck? seriously??!

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

    Rating graph of randrew is also inspiring... :)
    minimum rating is 1306 and maximum is 1889 ... just 11 rating away from being Master...

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

Chinese Div1 rounds chain is finally broken :D

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

Hope for math problems :)

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

Thanks for taking the time to prepare the problems. Feeling excited! Good luck contestants. (◕ܫ◕)

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

My first time in a Div 1 round, I hope I can make a submission.

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

Weak pretests please ;D

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

The first ever non-Chinese Div.1 round in 40+ days(excluding tournaments)!!!

Hoping to get back to yellow :D

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

    Wish you good luck :D I'm just hoping to get a positive rating this round.

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

      Well I don't hope I can get back to yellow only by one contest, I mean, there are more chance of positive rating change in non-chinese rounds

      UPD Wow. I become master again. And you too XD

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

        WOW! That's wicked! I've never thought of being yellow in one regular round. Congratulations to you too!

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

Hope for good problem. Hope for more hack.hf & gl

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

the shortest contest post ever

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

Как принято в некоторых других странах, откомменчу: Удачи всем белорусам на контесте!

Земляки, не позволяйте меня заминусовать:)

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

Жалко, что без пони, но зато и без спойлеров.

Special translation for MinakoKojima: It's pity without pony. But it's good there are no spoilers this time.

Big thanks to vas.and.tor for help with the special translation for MinakoKojima.

Thank to sebinechita (not a user codeforces (and it is not a user)) for help with translation helpful to vas.and.tor.

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

I start now FOR first time .

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

Good luck & it's my first time to be purple to take part in Div 1 !

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

a good news for me, a Chinese coder who don' t do well in math... most of last Chinese Rounds are also nightmares for me :p(anyway, learning is always a goos idea, through perhaps you can' t adapt it well

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

Is it the first Belarusian round or any other Belarusian rounds that have happened before ?

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

Coders like netman inspire us a lot for continuous practise.

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

The start time is confusing.

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

    mine is correct. F5?

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

    I think the registrations close 5 minutes before contest :)

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

    It's simple: the time shown corresponds to what's written above it. If it's "Registration's running", then the time shown is how long the registration will be running. If it's "Before start", then the time shown is how long until the contest starts.

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

    Look carefully! Bottom right one says Registration is running

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

Good luck :)

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

А куда делась ВКшная кнопка "мне нравится" возле отстчета до начала контеста?

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

worse прекратил "бурить"(

печалька

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

    А вдруг на цфе рейтинг unsigned, и поэтому если уйти в минус можно выйти в топ?

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

    мне вот просто интересно, на сколько он поднимется если хотя бы решит 3-4 задачи за контест?

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

GooD LucK...:)

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

Div 2 задача С — просто показалось.

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

I'm ready

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

In queue

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

Such CE, Much slow!!!

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

What a pity , I submitted a code in last 5 seconds and I got " Codeforces is temporary unavailable "

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

Problem C reminds me of the first day of IOI 2013, doesn't it? It is also clear now why you didn't thank Delinur for translations.

I like problem D a lot. Seems to be a good example, where rope sucks and sqrt-heuristics rule :) I didn't solve it during the contest, so I may be completely wrong.

Thanks for the contest, I've enjoyed it!

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

    Good problems, but contest was ruined by slow testing.

    I saw 20 pretests in some problems. Which means no hacks and maybe 500 tests in final tests. This could take some time to finish.

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

      I am not sure that pretests for A are really strong. I hacked a guy with overflow and using N instead of MAXVALUE.

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

      Fun fact: you can check if there are at least x pretests in the Status tab with settings "any verdict" and "tests  = x" — based on AC solutions shown.

      This way, we get: 12 for A, 10 for B, 15 for C, 9 for D, 21 for E.

      At least A-C have nice time limits and D,E didn't have too many attempts.

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

      My solution for C has a terrible misprint, but it gets AC on the pretests. It makes me think, that they are not so strong.

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

    Thanks. We don't thank Delinur because when I write the announce we didn't know who was the translator.

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

    Seems rope doesn't suck 7400437, but how does it work?

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

How to solve Div2 Prob C? I summed effective values obtained by all odd entries first and then checked even entries that outweighed the neighbouring odd entries, and then vice-versa. WA on pretest 11.

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

    I guess it was linear DP. dp[i] = max(dp[i-2]+(freq[i]*i),dp[i-1])

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

      My solution:

      S0[i] = max(S0[i-1], S1[i-1]);
      S1[i] = S0[i-1]+freq[i]*i;
      
    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I used this dp after 4 WA. I hope it could be the correct answer.

      dp[i] = max(dp[i-2] + m[i] * i, dp[i-1])

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

      How did you come up with this recurrence? Can you explain it please. Thanks in advance.

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

        dp[i] = the maximum score you can get using numbers with values 1~i. It is obvious that if you take one number i, then it is optimal to take all numbers i. Therefore we have two choices — take all numbers i or take none. If we take all we have dp[i-2]+freq[i]*i, we use dp[i-2] since we can't use values i-1 and we get score freq[i]*i from taking all numbers i. If we don't take i then the answer is the same as dp[i-1]. So we get the formula dp[i]=max(dp[i-2]+freq[i]*i,dp[i-1])

        Hope I helped! :)

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

        lets say you have stored number of frequency in array f. (Note ai<=100000). Now for each of the number i, if you take i you can't take the next number i+1.so you have to recurse over the next's next number i+2. and if you don't take it , you can take the next number. And see if you don't take the number i , you have two possibility , either you took i-1 , or you will take i+1 , both case is considered in the previous steps. and if you take(which you only can if you didn't take i-1) you can't take i+1.

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

    I too faced the same problem. :(

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

    It should be dynamic programming, you should consider two circumstances of the number. Reserve it or throw it away. Suppose that c is the count of a precise number, we have: fi, 0 = fi - 1, 1 + c[i] * i, fi, 1 = max(fi, 0, fi, 1). Note that you should use long long in c++ or int64 in pascal.

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

    Ok, but what is the mistake with my approach? http://ideone.com/MVT6SI

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

      1 2 2 3 4 4 5 6 7 7 8 9 9 10. Best answer is taking all the doubled numbers; your approach, starting with taking the odd numbers, will not replace 1 3 5 with 2 2 4 4 because 2 2 is not strictly better than 1 3 and 4 4 is not strictly better than 3 5, but combined 2 2 4 4 is better than 1 3 5 (because 3 only appears once).

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

Как решить C Div2?

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

    Простая динамика

    dp[1] = cnt[1];
    for (int i = 2; i < MAXN; ++i)
         dp[i] = max(dp[i - 2] + i * cnt[i], dp[i - 1]);
    cout << dp[MAXN - 1] << endl;
    

    cnt[i] — кол чисел i

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

      Круто, спасибо.

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

      Я ее пытался решить, задавая в отдельном массиве "веса" действия, т.е. (mass[i] — mass[i — 1] — mass[i + 1]) Примеры:

      1 2 = -1 1

      5 4 3 4 5 = 1 -4 -5 -4 1

      4 5 7 6 2 1 8 = -1 -6 -4 -3 -5 -9 7

      И потом брать наибольший вес, удалять числа, и переопределять таблицу весов Контрпримера нет ни у кого, кто так решал? Я на 5 тесте обвалился, со своими велосипедами

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

        Мой друг тоже писал что-то похожее и дожил до 9 теста.

        А я пытался пропихнуть жадник, и прожил чуть дольше вас — 11 тест.

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

now not

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

Сделал попытку взлома за 2 с половиной минуты до конца контеста, а вердикта почему-то до сих пор (после конца контеста) нет. В чем может быть причина?

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

Спасибо за контест))
интересно было решать, только вот по С Div 2 не успел одного взломать на long long

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

    Всю жизнь пишу массивы от i64, внезапно сегодня написал от инта, контесты утром для меня плохо складываются.

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

Problems are all interesting! Thanks! What a pity that can' t correct my buggy codes at last:(

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

It is unbelievable that there are many people still use long long in Div2/B although the N is 10^(10^5)..

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

It is unbelievable that there are many people still use long long in Div2/B although the N is 10^(10^5)..

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

Nice round. A and B were the way div2 first 2 problems should be. C was a little nice DP. D was a real show-off of Trie + 2 x DP + Game Theory. Also heared that E was pretty hard for Div (1+2), because Div1 coders should implement C and also meybe D or E.

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

    The chain in the problem C could be maintained just by using a set. After merging two vertexes (a, b), the answer will be .

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

      Only note each "division by 2" should be rounded up.

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

      But firstly you have two compute the largest path for if each set representative right? DFS from any vertex then find the most deep vertex. Then dfs from that vertex. Isn't it the approach for finding longest path?

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

        Yes, we should firstly initialize this, just simply DFS and merged them up in the set.

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

    For the ones who have studied problem 1A — Dreaming in IOI 2013 the solution will be quite clear. Fortunately I have read that problem and solved it before :D

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

How to solve problem D? Maybe I'm stupid, but I tried to solve it for quite a while, and the only solution I came up with is the straight-forward square-root optimization (store one single Treap for permutation + individual Treaps for all numbers which occur often enough). This takes per query and works literally forever (30 seconds on my machine for the worst case). But looking at the amount of people who solved it, probably there is a much simpler and much faster solution. I wonder what is it?..

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

    We have solution and it's much easier then yours.

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

    One can divide an array into sqrt(n) blocks and maintain a deque for each block. Shift operation is rather simple: for fully covered blocks, it is just one push_front and one pop_back. Partially covered blocks can be handled naively.

    To answer the second type of queries, one can maintain a count array for each block(count[i] — the number of occurrences of i within a block). For fully covered blocks the answer is just count[x]. Partially covered blocks can be handled naively again. Shift operation changes the count array in at most 2 positions per block, so it is possible to update it quickly.

    The complexity is O((m + n) * sqrt(n)).

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

    From what I could read in kutengine's solution: keep linked lists containing elements each, and remember the count of each integer for each list. Then you can do the rotating query by removing from the end of one list and prepending to the start of the next.

    That's quite beautiful, actually. I'm always surprised by sqrt-decomposition brilliance :P

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

Can someone explain this compilation error to me?

7393631

it worked after I've resubmited it (no changes were made)

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

How to solve div2-D ? I tried to use suffix automaton but couldn't get an idea. Hope a nice tutorial for this problem.

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

    I guess, D is based on game theory..

    waiting for the editorial :)

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

    I think we can use bor and then for each vertex set: 1) can we Win from this position 2) can we loose from this position After it see on root vertex and print answer. http://codeforces.net/contest/455/submission/7387998

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

    trie + 2 tree traversals to check if it's always possible for first player to win and if it's always possible for first player to loose. then just check for each case:

    • first player can choose if he wins or looses a single game -> "First"

    • first player always wins a single game AND k%2 == 0 -> "Second"

    • first player always wins a single game AND k%2 == 1 -> "First"

    • first player always looses a single game-> "Second"

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

      There's a case when first player can neither win nor lose for sure. Then second player wins and 71st testcase covers it.

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

        I'll take a look, bit i think it's always possible to be sure (at least my code got AC)

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

          There are 5 different cases(but we can reduce that to 3):

          1. The first player can decide the result of the game. Then he will lose n-1 games and win the last one.

          2. The result is deterministic (first player always win or lose), in such case, if first player always wins, result depends on parity of k; otherwise first player loses.

          3. The first player can ensure a lose but cannot win, then opponent force him always lose.

          4. The first player can ensure a win but not a lose(this is more complicated and I took some time to evaluate that): assume k=1, then first player choose to win; then assume k=2, we will see that the second player can let him win, and get a first play in next game and wins; evaluating similar cases as k grows we will see that first move will always win if optimally play. So the result depends on parity of k again.

          5. The opponent can decide the result. Obviously the first player loses.

          And finally the conclusion is: If first to play can decide the result then first play wins; Then if first to play can only ensure a win, result depends on k; Otherwise first player loses.

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

After waiting for a long queue, my submission have failed on pretest after 15 minutes after the contest. I should have tested more with handwritten cases.

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

again power of #define int long long.....2 unsuccessful hacking attempts on my code because of this...:P

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

    yes ,but one of them give me 100 pionts. others even passed,very angry...

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

    How do you write int main?

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

    16. Solution code obfuscation and creation of obstacles to reading and understanding the solution is prohibited. It is forbidden to use any special techniques designed to complicate the reading of the code, to understand its workflow.

    /blog/entry/456

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

      Yes, but this is actually useful if you want to avoid overflow. It can lead to fails, but it does have use.

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

      Oh ... take it easy man...! It's just a technique to avoid integer overflow and using int safely...it also has some good side effects!

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

        It stopped being "just a technique to avoid integer overflow" when you boasted how you tricked other people with it. I agree with dalex, it is a poor practice.

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

      Yes, I guess it's time to enforce the rule. I've seen countless solutions with super-obfuscated code, "#define int long long" is one of the most innocent tricks. E.g., once I've got unsuccessful challenge attempt because someone submitted file with 2 solutions — correct one was at the top, and then incorrect one (with bug) was at the bottom, protected from compiling by some hacks (but not commented out — it would be too obvious).

      Introducing unused code rule (similar to topcoder) would also be nice. Yes it slows some people down if they have to clean up their horrible mess before submitting, but making other people read this mess is much more cruel.

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

        Which solution? Unlike TC, at CF contestants can gain from making solutions readable -- because it's possible to resubmit solution if it haven't been locked.

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

          They benefit only from a certain kind of readability; there is no reason to fix hacks like "#define int long long" (and more tricky obfuscations).

          Regarding to your first question — I'm not sure I understand, what are you referring to?

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

      so using "small L" should be prohibited because it's exactly the same as "one" in codes! I lost an attempt to learn it ...

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

    LOL, i tried to hack you once, and it returned unsuccessful for the same reason. luckily it was only a testing round. :D
    PS: due to Black Day of CF, this submission is no longer visible. :(

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

so many people even use long long to cin>>n in DIV2 B. and a lots of them passed.... what could i say

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

People used biginteger and modular exponentiation in div2bB!

Hacked a Java code but python code passed time limit! :(

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

In hacking box, font size is too small. When I was attempting to hack, I couldn't distinguish letter 1 from letter l. So I sent an hacking request and got Unsuccessful. This will be better if font (in hacking box) is not Courier New or at least not too small like this.

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

    1 and l almost look the same in hacking box, I agree. I've got same problem before.

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

why system testing is not started yet ?

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

Oh la. What a large queue. :X

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

problem div1 A, at beginning I thought we remove all element equal to Ak + 1 not Ak + 1 , who is the same?

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

Верно ли, что в при объединении двух деревьев если старые диаметры в них d1 и d2, то новый будет максимум из: d1, d2 и ?

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

    Если твои квадратные скобочки — это округление вверх, то да.

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

    1

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

    Да.

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

    Нам не помешает лишнее нытьё. Завалил С из-за того, что при слиянии не проверял, что мы уже и так в одном дереве.

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

I have a question. How did this "7385674" solution passed the pretest..?? i tried to hack this with a large input. i thought it will fail to take the input. but it still passed.. and gave correct answer, how is it possible...???

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

    Your test you hack ?

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

    Because (x^4 — 1) % 5 == 0 (according to little Fermat theorem). So there are only 4 cases:

    n == 0, n == 1,n==2,n==3 (mod 4). Easy to see, that if n==0 (mod 4) -> ans=4,else 0

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

      sorry bother if i am not clear... the problem says the input can be very large... but the solver use long long.. I tried hacking with a input consist of almost 300 digit. how did it take the input a 300 digit long number in long long and still can calculate the correct answer...?????????

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

        passed pretest but it will fail system test.

        and your hack failed because when this code reads large number it will overflow so an overflowed variable will have random number so it will still enter either "if" or "else" and in your hack it entered by luck the same as the correct answer for your test so it gave correct answer.

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

        5464456456456456456456465465456456456456456456456465

        At my computer it gives wa

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

    It looks like this solution relies on particular implementation of cin. Actually, what really matters is a residue modulo 4, so it's not so strange that solution works, because when overflow happens "divisibility by 4" is not changed.

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

    counter example : 111111111111111111111111111111132.May be you didn't huck, because for your test answer is 0.

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

    And some submissions have got accepted, even though there has been overflow

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

      If somebody uses cin for taking input, and if your input is too large , it will take maximum value of that data type(I found when I did unsuccessful hacking). If you use scanf(), in case of long long it will just move between 2^-63 to 2^63 — 1(Data type range). In Java it will throw exception, I thought same in c++. His submission accepted because he used scanf.

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

For Div2, problem c, I used the DP : dp[i] = max(freq[i]*i + dp[i-2], freq[i-1]*(i-1) + dp[i-3]), can someone please tell me why it is wrong and why dp[i] = max(freq[i]*i + dp[i-2], dp[i-1]) is correct?,

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

What are hackings on problem A div1? At first I think some people doesn't use long long but it seems that pretests include that case.

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

    Got successful hack on a guy that used int so I don't think pretests cover it.

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

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

7377218

This shouldn't have happened...

Can't compile file:
g++.exe: error: CreateProcess: No such file or directory

Could you please repair it ASAP? :P

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

Many programs which already passed pretests get "Compilation Error", I think there must be some problems with the judge system.

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

Is there any problem in system tests? I submitted 2 codes for A, 1 for B and 1 for C. Instead of skipping my 1st A code, the submission page shows my B code as skipped.

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

Can anybody explain me this: 7377299 ?

UPD. This solution passed pretests; verdict became "Compilation Error" during the testing .

After resubmission, it was "In queue" until the end of testing.

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

Кстати, в B div 1 проходило решение за O(k), надо было чуть поднять ограничения на k...

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

    wut? Как решать за O(k)?

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

      Показывая пассы Никиты Литвинкова, когда тот говорит о чае Супер-пупер математическим алгоритмом со страшным названием!

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

      Ну, всё как в обычном решении, только вместо if'a на чётность k, цикл :)

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

1H after coding phase and system test still not complete :(

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

    codingphase

    Bad influence of topcoder(

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

      Nope. When a Codeforces round ends a message box pops up and says "the coding phase of round xxx has ended"

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

In Div2 "A" — I checked if numbers in each pair are equal...

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

7383032 Seriously -_-...? Why?? Because of what? Is O(n log n) too slow for 3e5 -_-?

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

    7391661 Even worse :(

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

    Uhm, by what magic doesn't it crash? Your function "Find()" doesn't return results for non-trivial cases...

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

      LOL XD Good point :P

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

      I guess that works because assingnment returns the assigned value (eg. a=b=7; assigns 7 to both a and b).

      Anyway I commented the cerr and got AC xD 7396190

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

        Yes, I did the same few minutes ago : /. I ignored it, because it outputs The same amount of text as cout, but it was a mistake ; d. Is cerr slower than cout?

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

        I know perfectly well how assignment works. However, "int f { a = b; }" isn't the same as "int f { return a = b; }" ;) In this case it can be smth with how return value is stored on the stack and how exactly the code is compiled. However, missing return is Undefined Behavior, so compiler has full right to compile it to "while (1);" or to "exit(42);".

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

      That's magic in C. You can program a one-liner gcd or disjoint set XD

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

в этот раз тесты плохие. DIV2 задача A у меня прошло вообще не верное решение :) Заметил, как всегда, после блокировки задачи...

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

Check out room 23: Slovak domination!

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

    what do you mean?

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

      Me and Bobik are both from Slovakia and take top 2 places. It's rare to see 2 people from a small country in a room together, and taking the best places is much more rare.

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

        two coder in one room means these two coder registered nearly at the same time.

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

          According to the registrants' page for that contest: Bobik is 27., I'm 1102.

          nope.avi

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

            I have thought the room is according the order I register... Oh, it is wrong... I want to find out the algorithm for the place of room.

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

              I don't know what it is, but if I was the one coding it, I'd make sure it's randomized and sufficiently complex so that nobody could register 2 accounts in the same room to get hacks — and, of course, people just registering in the same room for the lulz.

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

    Omg, that's unbelievable! How did you manage?

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

can anyone explain div1-B . I was trying something with trie ....but coludnt get it ...

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

    Here it goes, hope I explain my solution well enough:

    Firstly we build a trie. The root of the trie is the empty string. Now the game proceeds as the first player starts in the root and then chooses a child to go to. Then the next player chooses a child to go to and so on until you are in a leaf, when the current person loses. Now to efficiently solve the problem you must compute two values for the root position.

    1) Can you win if you try to? (is it a Winning or Losing position)

    2) Can you purposefuly lose if you try to?

    Both are equally simple to compute. Simply start from the leaves and go up the tree computing each vertex through its children. The computation of both values is simple and is as follows:

    1) If you can move to any lost position, then the current position is won. Otherwise it's lost.

    2) If you can move to any position that CAN'T be purposefuly lost, then the current position can be purposefully lost. Otherwise it can't be.

    Now how do we compute our answer? Well let's look at a few cases.

    1) One simple case is if the root position is lost, that is you can't win if the second player plays optimally. Well then the answer is "Second" as he could easily win all games and the loser would always play first again and lose

    2) If the root position is won, and it CAN be purposefuly lost then the winner is "First". This is due to the fact that he can purposefuly lose until the very last game where he can win, no matter what k is.

    3) The last case is if the root position can be won, however it CAN'T be purposefuly lost. Well then it is obvious to see that if some of the two players wants, the game can be played in such way so that the first guy always wins. Therefore it is easy to see that if k is odd the first player will win, and if k is even the second player will win.

    Hope I helped you :)

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

Why no editorial still?

I dont think editorials cannot be shown during systest (when it takes 100+ minutes)

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

Все кто писали Union Find без ранговой эвристики или рандомизации обломались. Оно правда работает за квадрат?

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

My submission was judged as WA on test 20 but when I use custom invocation, everything is OK. Please check! 7377515

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

7377531 WA with no reason? I submitted the same thing in practice and got AC...

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

Thanks for minus!

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

I can't stand that Imagine my excitement when 1,5 min before the end of contest I finally debugged my D. Imagine my anger when few seconds later it turned out that Internet crashed in a place I was coding and I can't submit it. Imagine my anger when I got to know that my C got very weird TLE which resulted in 39->262 change of my place. Imagine my anger when I submitted D on practice and it got AC!!!! And now my C got accepted after deleting one cerr (without endl's, so it is really fast)!!! Words won't describe my irritation at that moment ^&*(%^%^*!!!!! I should have took ~10th place and I got 262th! ARGH!

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

    imagine my anger when I submitted a code for D in last 5 seconds and I got "codeforces is temporary unavailable"

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

      I see that your code doesn't pass 1st pretest, so it is not that bad feeling afterwards xd. Btw I once managed to load my code, but haven't managed to click "submit", I was late about ~1 sec and it passed after the contest. Moreover it was E (I never got E accepted!) and I spent 15 mins of that contest doing nothing on facebook xd.

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

        I fixed my mistakes in that submission then submitted again in last 5 seconds so why it's not a bad feeling ?

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

          Hm. sometimes I also get angry, because of some unlucky circumstances, but when I submit my code after contest and it's not passing I'm getting calm. So far, I don't see your solution among accepted, so I guess that it's the case. But when it gets accepted xd...

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

            Still you gotta admit, getting "codeforces is temporary unavailable" while trying to submit or open a problem is quite irritating.

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

              Yes, I have to. I'm really a professional in category of whining about everything and if it had occured to me I will surely get annoyed :P.

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

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

I have some problem with my div 1/B submission

this is the code I submitted during the contest, and got queued until the end of the contest. The verdict said WA on pretest 1. But it appears that there is no output in the submission above.

Then I submit this code after contest, the very same code but with assertion commented, and it got accepted (I tried to post the exactly same code but the verdict is exactly the same with my first solution; no output at all).

Does anyone knows what's happened?

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

Can we continue to solve problems?

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

Can we continue to solve problems?

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

I see the most of the solution of DIV 2 Problem LAPTOPS solved using sorting in O(nlogn) complexity. But it can be solved in O(n) . Suppose for "Happy Alex"

price[i] < price[j] ....................equation_1 quality[i] > quality[j] ====> -quality[i] < -quality[j] .................equation_2

let's add equation_1 and equation_2

price[i]-quality[i] < price[j]-quality[j]

Difference[i]<Difference[j]

so compute all the difference , get max difference and min difference if max_diff!=min_diff

then "Happy Case" else "Poor Case"

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

    There is much easier solution using piegon's hole principle.

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

    But does Difference[i]<Difference[j] imply price[i] < price[j] and quality[i] > quality[j]?

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

    Both the price and quality numbers are limited from 1 to N. Since they are unique, the only way the prices are valid if they look like this:

    (for example, if N = 3)

    1. Price = 1, Quality = 1
    2. Price = 2, Quality = 2
    3. Price = 3, Quality = 3

    So you can just parse it as you read it, and if price != quality for any pair, you just print "Happy Alex" and break. Otherwise, print "Poor Alex".

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

It’s my first time in CF and feel 2exicited. But I got TLE for cin ,which depress me.

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

Why is my submission skipped? 7380034

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

During contest I got TLE 121 on problem C: 7391661

Exactly the same code got AC in practice: 7396418

This might be caused by server load during the contest, and I request that my in-contest submission is rejudged and considered correct.

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

    Your code in practice runs 951ms. IIRC, variation of execution time on codeforces is ~40-80ms, so nothing surprising that it failed during the contest.

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

      If it was WA then yes — it should be considered wrong. But IMHO if a solution once once fails time limit due to overload, and then passes, it should be considered correct.

      I can't find how such cases are considered according to Codeforces rules though. I think it's up to problem setters and administration to decide.

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

        That's not due to overload. Try submitting your solution again to practice several times (adding whitespaces to make it re-run the submission). I've just tried, and it gets TLE ~50% of the times.

        I think usually on CF they don't change their verdicts. E.g., ~3 years ago one of my problems failed getting TLE and passed in practice with 100ms margin. Back then they probably had slightly different machines, and now it's not that bad.

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

      7396999 Here it passed again, so the fail during contest is definitely due to system load.

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

        And here it failed: http://codeforces.net/contest/455/submission/7397092

        I'm absolutely sure it's due to the natural variance of execution time; 40ms margin is very tiny.

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

          I agree that it might equally fail and pass. My question is, how are such cases handled on CF? May be some of these points:

          • Solution is incorrect, if it got TLE at least once;
          • Solution is correct, if it passed TLE at least once;
          • The contest verdict is taken into account, no matter what happens in practice;
          • This is a matter of appeal with inspection of a particular case.

          or something else. I would appreciate an official comment from problemsetters/administration.

          Anyway, this particular solution had the same chance to pass during the contest, and I might be somewhere around 50th place, not 286 :)

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

            I believe it's "submission is correct, if it got AC on the systest", with "submission is systested if it passed all pretests, is the last submission of that user on that particular problem and wasn't skipped for cheating". So it has to pass all pretests on 2 runs and all other tests on 1 run. Of course, with possible reruns.

            Maybe you noticed that usually, the authors of the round have solutions that fit in the time limit comfortably. That's because the TL is chosen so that a reasonable constant factor wouldn't pose a problem, usually 2-5 times that original solutions' runtime. And I think it's safe to say that a reserve for cases such as yours is included.

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

            The practice is that the system test results are final in this case.

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

    Check out my submissions in practice — I tried submitting your code several times (the only difference is adding a comment) and got AC 2 times out of 9. Based on this, I don't think a rejudge would make much of a difference, unless the code was rejudged until it got AC (roughly 1-5 times, I'd guess).

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

Когда будет разбор задач?

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

where is the rating result ?? ?? ?

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

    I'd personally wait until all the matters with weird compilation errors and wrong answers are resolved before updating ratings (there were, and still are, a few). In my opinion, it's way more important to carry out the competition correctly rather than immediately update ratings...

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

    v karagande

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

Я правильно понимаю, что Дэшка и за на запрос решается? 7394913

И ещё, это(7397416) случайно не квадратное решение Ешки? Точнее говоря, . Это было так задумано, ограничивать Amax ≤ 10000, чтоб наивное решение заходило быстрее чем любое другое, пусть даже с правильной асимптотикой? =)

UPD. Всё-таки это тесты слабые. На тесте с массивом вида 1 10000 2 10000 3 10000 4 ... этот код работает больше 2х секунд в запуске.

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

    Как я понимаю, это решение по D все-таки за на запрос.

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

Problem E has 21 pretests Wrong answer on test 23

And it was a pretty easy bug to catch, too... :(

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

I used grundy numbers for problem B Div-1. I have no idea where it is failing. Can anyone please help me find the error?

Link: My submission

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

    I'm not 100% sure here, but I think that Grundy numbers work only when both players want to win. In this game, it's sometimes optimal to lose until the final game comes around.

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

      I am using grundy numbers only to evaluate one game. For each possible starting move, I find the grundy number for that move.

      Now if I find all starting moves to have grundy number > 0, then if k is odd, output "First" else "Second".

      If all starting moves have grundy number == 0, then answer is "Second".

      Else, answer is "First" as he can keep losing until the final round and win the last one.

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

    Test:

    3 100
    aaaaa
    aab
    aaca
    

    Your answer is "Second", but right is "First". You should check whether first can lose if he wants it, not if second wants it. In test first loses 99 games by a-a-c-a and wins last by a-a-b.

    UPD. BTW, you store "edges" in strange way. Are you sure, that you can't make move from valid string by edge into non-valid string (for example, edge was "generated" by other input string, then string to which current position is prefix)?

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

      OH! I totally missed this, thanks a lot!

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

      I think the edges part is fine. For example, in the test case you have given above, ['a'][1] has edges to ['a'][2], ['b'][2] and ['c'][2].

      UPD: I've realized why it is wrong. :-|

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

    consider this test :

    aab

    bac

    according to your code edges[a][1] = {b, c} but this is not correct. for "aa" the next letter is just 'b' and for "ba" is 'c'.

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

      It seems I have gone wrong on multiple levels here then. :-(

      Thank you for the clarification.

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

    Quote from your code: "//I'll shit bricks if this happens"

    You'll definitely do this because of test 71. I did the same mistake.

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

Why the output is unexpectedly 0 in 43rd test case ? Submission id: 7389527

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

Is it just me or was Div1-B really confusing? I thought during the contest that the players will play optimally in each game, and not considering all k games....

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

    No, the result is determined by the following sentence:

    "Guys decided that the winner of all games is the player who wins the last (k-th) game."

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

      Actually you're right. But for example after contest before system test, I asked my friend who tried to solve Div1B, "Play for win, for each game" is optimal?, he said "I didn't think it". Problem doesn't say "You don't need to play for win, for first k - 1 game.", it says "You have to play win, for last game." So you have to make a little observation.

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

    I don't know if confusing is the right word. It's just a matter of analyzing the problem fully, paying attention to every detail.

    I did consider K games, but I forgot about the fact that people can intentionally lose. (I thought of using K mod 2 to determine the output once I analyze a single game).

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

Обновите рейтинг, я спать хочу

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

Five hours have passed after the contest and the rates have not been updated yet! What is the problem?

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

Why is not updpate rating ? I hope very more about this

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

Why there is a Hack with status "Waiting" after contest?

Look for 107221

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

    LOL, it's still "Waiting" more than 7 hours after you wrote this comment.
    but ratings have already been updated. :D

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

Finally! Ratings have been updated, just now.

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

I want to ask a question ,why my div 2 C problem's final test statue is Skipped?I am so puzzled.

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

    Yea that is really weird. I submitted your solution and it got AC. link

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

      In contest,I got pretest passed,but after final test,it became skipped.I want to know if it is possible to rejudge it.

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

    It is so unfortunate that they updated the ratings before they resolve problems like this. It is not just you, there are other submissions which have weird verdict (like this, WA with no reason)

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

    Cause you cheated 7394898

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

Would you please post the editorial for this contest :D ?

Mediocrity netman randrew

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

would anyone like to suggest how to solve problem E- DIV2 Efficiently ?

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

    Firstly , you are given a graph which is a forest(note every connected component is a tree, as there is only one unique path between any pair of vertices).

    Now , to find the longest path in a tree , you first start dfs from the any vertex u. Let, v be the vertex we find which is the most deep node from u. Now from v you do a dfs, and find the most deep node. This height is the longest path.

    When you have found the longest path of a tree L, you insert the edges into a disjoint set data structure(actually you do it during taking the input). You find the representative of that tree and then let representative be r. So you mark longest[r] = L. Here is a thing , the longest path in a tree is called the diameter of the tree.

    So , we have found the longest path of each tree. Now, answering query 1 is pretty straightforward. You find the set-representative r and print longest[r]

    for the 2nd type , note that , for a component , if longest path is divisible by 2 you can take the middle vertex(the center) otherwise you can take any of the middle two vertex. So if you choose this way , in both component where x and y lies, the path length will be (Let r1 ,r2 be representative of x,y) ceil(longest[r1]/2)+ceil(longest[r2]/2) + 1. Now when you connect the component , the new longest path will be maximum between previous two components and this recently emerged path through x and y.

    note , if you connect to any other vertices you dont get shortest long path, why ? let you have choosen u and v that is not center. then the longest path is (larger radius end1 -> center1 -> u -> v-> center2->larger radius end2) which is defineitely larger then previous.

    Hope it helps.

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

What is the intended solution of task E?

My submission(7390143) is just an O(nm) brute force with few pruning:

  1. If x[i] < x[i+1] < .. < x[i+k] then start with x[i] is not worse than x[i+1], x[i+2], .., x[i+k].

  2. If x[i] >= x[i+1] >= .. >= x[i+k] then start with x[i+k] is not worse than x[i+1], x[i+2], .., x[i+k].

Since the range of number is 10^4, the number of computation will be under 10^5 * 10^4 / 2. (worst case is x[] = {1,2,1,2,1,2,..})

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

    {1,2,1,2,1,2,..} isn't worst case. With test x[]={1, 10000, 2, 10000, 3, 10000, 4, 10000, ...} your code works 4 seconds.

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

    Suppose you have partial sums at S[]. I used the fact that if you calculate f (i, j) starting at x[k], then you have

    f(i, j, k) = (S[j] - S[k]) + (i + k - j) * x[k]

    Which is a line, so you can use something similar to convex hull trick to get best k in log n: 7397318

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

In problem D solution can pass: 7401453. Is it ok?

UPD. 2808 ms with some shenanigans: 7401820

UPD 2. Looks like tests are weak and there is no test, where all query operations make more than 2e9 operations... 7401924

UPD 3. By the way, in lots of tests you do not need to output anything and there (if I am not mistaken) are no tests, where q = 105 and you need output several (but less than 100) lines. Of course, such testset is vulnerable to obvious pruning: if you have nothing to output don't do anything.

UPD 4. Anti-bruteforce tests were added. Thanks to authors.

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

I love this contest, even I could't go to orange in this round :( The problem C in div 1 is interesting. Love it. I expect more Div 1 rounds from guys.

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

In Div2 E/Div1 B, is the case of n=1 and the length of string = 100000 in the test? Some people use recursive, but how do you decide whether you can use recursive or not?

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

Problem B Div2 :

What is the difference between these 2 codes ?

Hacked : http://codeforces.net/contest/456/submission/7385428

Accepted : http://codeforces.net/contest/456/submission/7399213

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

    I don't know how scanf read overflow integer, but i think the accepted solution using int got super lucky accepted, since both solution is wrong because N can far exceed the limit of int or even unsigned long long, and should't always produce the correct answer.

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

    As it was mentioned in the previous comments, cin will just overflow the integer while scanf will input the integer mod 2^64 (not completely sure on this). Since 2^64 is divisible by 4 (which is what you're checking), it apparently doesn't have any effects on the result.

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
    cin>> n   !=   scanf("%d",&n)
    

    =>

    Hacked  and  Accepted
    

    He is really lucky

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

Problem Civilization is very similar to IOI 2013 problem Dreaming. During the competition itself I simply took my old code for Dreaming and modified it. I had some bugs and it took me more time to fix it than it would to code a new solution, however in the end this problem is just a simplified version of the IOI problem.

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

I am new to Codforce. plz tell me where to find the solution of codeforce round #260. thanks

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

    The official editorial hasn't been published yet, hopefully Mediocrity, netman or randrew publish it soon. On the other hand, you could just open the standings, double click on the points of some solution and check his code, trying to understand his approach.

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

      Thanks. I saw some editorial in Recent action column. In every round does author publish editorial?

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

For problem Div 1 D, I am getting accepted using vector cnt in the struct block, but when I change it to int * cnt, I get wrong answer on test case 5. Actually it is giving garbage value on a specific index.

Accepted Code
Wrong Code

Please help, thanks in advance !!!

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

    It's because of your memset. sizeof cnt is 8 and so you don't fill the whole array with 0. I replaced sizeof (cnt) with sizeof(int)*N and got accepted.

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

      Yes, I got that, Actually it has become kind of habit to use memset in that way, It wont work for pointers correctly. Learnt a new point, Thank you so much :)

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

    never, ever use pointers explicitly in programming contests!

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

    Why are people downvoting this!

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

      don't try to understand logic of voting on CF.
      EDIT: now the comment has +6. :)

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

      these people argue that his contribution is increasing. in their opinion, he's cheater

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

      I can explain it. Several people asked this guy to post his stats in separate blog and post the comment like that after each round. Instead of that he keeps posting his round stats every time in blog posts and it pops up in Recent Actions. I consider these blogposts as spam. I don't downvote them but they annoy me and I would downvote them with pleasure if I don't have other things to do.

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

Я очень удивлён, что таска С такая лёгкая ( жаль на самом контесте я этого не увидел).

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

Problem A Div.2 I don't sort and accept O(N) , but have many people sort, even Editorial use sort O(N log N). My submission

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

Is the editorial actually coming out in English at all?

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

in problem C div 1 when we calculate the diameter of the new tree why do we mazimize between the 2 small trees ??

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

    Because when you merge two trees its diameter will be the length of its longest path. It is not about maximizing, it is about diameter definition.

    More precisely, in this problem we are merging in a way that the diameter of the resulting tree is minimized. Merge means adding an edge that connects two separate trees. The optimal way to do this is by connecting its centers.

    Trees can have one or two centers. If a tree has only one center its eccentricity will be exactly , if a tree has two centers, they will be adjacent and they will have as eccentricity. Both cases can be summarized as the ceiling of .

    Finally, when you merge two trees, you must take into account that the resulting diameter can be the diameter of one of the original trees, or the new longest path created by connecting its two centers. That's why you see this max formula on this problem.

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

Ignore this; it seems that the English editorial is up.