Mediocrity's blog

Codeforces Round #260
By Mediocrity, 10 years ago, translation, In English

Hi everyone!

We invite you to participate in Codeforces Round #260(Div. 1 and Div. 2), wich will take place on August 8th, 19:30MSK.

The round was prepared by me, netman and randrew. It's our first round and we hope that tasks will be intresting for you). Special thanks to Gerald, CherryTree, vlad107 and dimad for helping to prepare the round. Also MikeMirzayanov for creating such a good platform.

Good luck everyone!

UPD. In Div. 2 and Div. 1, scores for each problem will be 500-1000-1500-2000-2500.

UPD. We are sorry for the large queue in the end of round.

UPD. Congratulations to the winners.

Div. 1

  1. tourist

  2. cgy4ever

  3. LayCurse

  4. ecnerwala

  5. snuke

Div. 2

  1. allthecode

  2. gotowork

  3. SMAKH

  4. saikrishna17394

  5. PashaChemerys

Editorial.

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

Comments Comments (335)
| Write comment?
»
10 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The first time so early I am.

→ Reply
»
10 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Hope Strong Pretests :D

→ Reply
»
10 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Hope Strong Pretests :D

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

    Hahaha so much hate for you

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it
      • 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...
      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

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

          MinakoKojima is really a Chinese girl.

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

            How do you know that? Are you real Juan Mata too?

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

              I don't think so. He posted comments and participated Codeforces Rounds while FIFA World Cup 2014 was running.

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

              no, i am not.
              but how is that related to my earlier answer?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                How you can claim that she's girl if you don't know him/her in person? I just proved that one cannot judge people by their nickname/profile picture because you neither Juan Mata nor Chelsea player (but you have Chelsea FC on your profile picture).

                → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          One does not simply ask gender on the Internet!

          → Reply
»
10 years ago, # |
  Vote: I like it +72 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it -9 Vote: I do not like it

    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??!

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it +157 Vote: I do not like it

Chinese Div1 rounds chain is finally broken :D

→ Reply
»
10 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Hope for math problems :)

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Weak pretests please ;D

→ Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

Hoping to get back to yellow :D

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

the shortest contest post ever

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Hope short problem statements too.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      and short solution too !

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +65 Vote: I do not like it

        But not short editorial :P

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

          Still no editorial post... bad :(

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            maybe because nobody wished for "short time taken to publish editorial" ;)

            → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    actually there's a shorter announcement here it was only first 4 lines when the author first posted it.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Seems that the post you talked about is the only contest forecast post that doesn't mention MikeMirzayanov :p

      → Reply
»
10 years ago, # |
  Vote: I like it -25 Vote: I do not like it

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

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I start now FOR first time .

→ Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Coders like netman inspire us a lot for continuous practise.

→ Reply
»
10 years ago, # |
  Vote: I like it -74 Vote: I do not like it

The start time is confusing.

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

    mine is correct. F5?

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    I think the registrations close 5 minutes before contest :)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Look carefully! Bottom right one says Registration is running

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck :)

→ Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In queue

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Such CE, Much slow!!!

→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      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.

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

      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.

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

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

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

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

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

      My solution:

      S0[i] = max(S0[i-1], S1[i-1]);
S1[i] = S0[i-1]+freq[i]*i;
      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

        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.

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

    I too faced the same problem. :(

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

    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.

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

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

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

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

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

now not

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

    invalid input after 10 minutes :(

    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

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.

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

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

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

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

      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?

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

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

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

    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

    → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Beautiful, thanks for the explanation!

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain this compilation error to me?

7393631

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I guess, D is based on game theory..

    waiting for the editorial :)

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.com/contest/455/submission/7387998

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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"

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

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

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

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

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

          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.

          → Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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

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

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    How do you write int main?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      GNU C++ still accepts "main()" which means "int main()" but with a warning.

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it 
      #undef int
int main() {
#define int long long
      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You can write void main() in Visual Studio

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        But GCC gives compilation error if you write void main(), and that's not supported in standard.

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

          Codeforces supports MS compiler

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      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.

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

        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.

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

          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?

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

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

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

    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. :(

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Or they used int :) 7389513. And my attempt to hack was unsuccessfull.

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

      I couldn't watch your hack attempt. What were you input?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        string: "1" x 100000 + "\n"

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          In this case, maybe what he got is "1111111111".(The ouput as well as answer is 0) The better way to hack is input "1" x 999999 + "2". (The answer is 4 while the output is 0) :)

          → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

People used biginteger and modular exponentiation in div2bB!

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +63 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
  Vote: I like it +24 Vote: I do not like it

why system testing is not started yet ?

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

    hope all accepted solutions!

    slowest ever system test :(((

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

    Because "Pretest testing" hadn't been done.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh la. What a large queue. :X

→ Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Your test you hack ?

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

    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

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

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

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

        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.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        5464456456456456456456465465456456456456456456456465

        At my computer it gives wa

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

    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.

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

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

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?,

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

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

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

    → Reply
»
10 years ago, # |
  Vote: I like it +142 Vote: I do not like it

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    Mine: image

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

    And System testing starts finally

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

      around 50 minuets after the contest.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Started finally! 45 mins later.

    I remember I had even read the full editorial by this time in previous round.

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

      ... And system testing is completed!! nearly an hour only for systest!

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it -12 Vote: I do not like it

    Registered: 83 minute(s) ago have Contribution: +13 !!!. Link

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

      It's frequent phenomenon happens in codeforces when someone wants to post a joke but he/she is afraid from negative votes so he/she makes a new account and post the joke with that account

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

        You are right ! Maybe he is not excited about that

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        And when you see that the comment got lots of positive votes, you regret not using your real account

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

    umm, u didn't even take part in the contest! o.O

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    codingphase

    Bad influence of topcoder(

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

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

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

        nope. if i'm not mistaken, the box says

        Contest has been finished

        → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    7391661 Even worse :(

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      LOL XD Good point :P

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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?

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

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

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

      → Reply
»
10 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Check out room 23: Slovak domination!

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

    what do you mean?

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

      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.

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

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

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

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

          nope.avi

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

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +6 Vote: I do not like it

              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.

              → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

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

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

      It's magic :D

      I have no other idea how to explain it.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.com/contest/455/submission/7392292 TLE just because I used vector ?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +34 Vote: I do not like it

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

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

      Nice ans .. thanks!!!!

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

      thanks..well explained

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

      if possible please provide the code as well...

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

        You could easily retrieve it from my submissions : 7384830

        Array W is true if the position is won and array LI is true if the position can be Lost Intentionally.

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

          Thanks a lot ....it really helped

          → Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why no editorial still?

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

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

    Oh please show the editorials now.

    (Its 2 hours since end of the 2-hr contest)

    → Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Same to my situation, I have just resubmitted my in-contest code.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Same problem with mine 7395010

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it -28 Vote: I do not like it

Thanks for minus!

→ Reply
»
10 years ago, # |
  Vote: I like it +64 Vote: I do not like it

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!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

      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.

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

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

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

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

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

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

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

              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.

              → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

      Bredor has never participated in div 1 at all. Hey bro are you going to compete?

      → Reply
»
10 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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?

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Can we continue to solve problems?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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"

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

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

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

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

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

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

    → Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my submission skipped? 7380034

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

    prost))0)

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

      Sorry, but I don't understand what you mean.

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

        simpli))0)

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          what is up with adding ))0) to the end of every comment of yours?

          also, what happened to 7394707? 7395446 is almost the same code (one constant changed, just to make it different from previous code) and it got AC?

          do i lose points for 7394707? it says 

          Can't compile file:
g++.exe: error: CreateProcess: No such file or directory
          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it -14 Vote: I do not like it

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

    Only the last submitted solution will be judged. All previous ones will be skipped.

    → Reply
»
10 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
        ← Rev. 2   Vote: I like it +18 Vote: I do not like it

        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.

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

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

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

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

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

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

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

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

            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.

            → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
              Vote: I like it +10 Vote: I do not like it

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

            → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

where is the rating result ?? ?? ?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

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

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

    v karagande

    → Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Country Wise standings is updated.

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Problem E has 21 pretests Wrong answer on test 23

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

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

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

      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.

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

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

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

      OH! I totally missed this, thanks a lot!

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

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

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

      Thank you for the clarification.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The for statement should go till 100000 instead of n and you should cout max(ans[100000], ans[99999]).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      oh..Thanks.. I was hoping to become Expert for the first time but became Pupil! :(

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Edit: Did not notice that there is already a post that has answered

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      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.

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

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

    → Reply
»
10 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

Look for 107221

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

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

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally! Ratings have been updated, just now.

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

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

    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)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Cause you cheated 7394898

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Mediocrity netman randrew

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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,..})

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

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

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
10 years ago, # |
← Rev. 8   Vote: I like it +44 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Problem B Div2 :

What is the difference between these 2 codes ?

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

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

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

    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.

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

    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.

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it 
    cin>> n   !=   scanf("%d",&n)

    => 

    Hacked  and  Accepted

    He is really lucky

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

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

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

        Some competitions end up with no editorials, but they usually publish.

        → Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 !!!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

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

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

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

    never, ever use pointers explicitly in programming contests!

    → Reply
»
10 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Round Stats

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Why are people downvoting this!

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 3   Vote: I like it +4 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

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

      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.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is the editorial actually coming out in English at all?

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply