GreenGrape's blog

By GreenGrape, 21 month(s) ago, translation, In English,

Hello, Codeforces! Haven't seen ya for a while :D

Codeforces Round #461 will take place on Wednesday, 20:15 MSK. Note that the round is scheduled a bit later than usual.

The round will be rated for all division 2 participants. Division 1 is heartly welcome aswell :)

My gratitude to Kolya (KAN) for round coordination, Grisha (gritukan), Oleg (x3n), AmirReza (Arpa) and Senya (senek_k) for testing and Mike (MikeMirzayanov) for awesome Codeforces and Polygon. A special thanks goes to Dima (mitterr1999) and Camille (pseuda) for sharing a problem sketch with me.

The main character of this round will be Imp the playful monster. Yet the statements are guaranteed to be short :)

There will be six problems with the following scoring:
500 — 1000 — 1250 — 1500 — 2000 — 2750

GL & HF!

Note that the round has been moved 40 minutes later to avoid clashing with CSAcademy Round.

UPD. The contest is over. Well...

UPD. System testing is over! Editorial.

Congratz to the winners!

Div. 2:

  1. sorry-haghani
  2. spec4r
  3. SashaShlyapik
  4. belic
  5. 4783992

Div. 1 (unofficial):

  1. dotorya
  2. Vercingetorix
  3. dreamoon
  4. kmjp
  5. FCB1234

UPD. The complete editorial is out (D/F).

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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

Really loved your last round but hopefully this time, there will be a better difficulty distribution in the problems!

»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

codeforces contests are always great and amazing , i always try to attend the contests , but my bad , may be i will not be able to participate in this contest due to some travelling stuffs , and it is much painful for me , competitive programming is my passion

»
21 month(s) ago, # |
  Vote: I like it +38 Vote: I do not like it

Ohh god CM problem setter again.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    How to download Test #15 of 650C Table Compression?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      In input :

      1000 1000

      1002 1002 1002 1002..... (1000 times)

      In output :

      1000 1000 1000 1000..... (1000 times)

      Coz you were asking so many times.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        the other numbers must be n*m(1000*1000). And also if there is only 1002(1000*1000 times) the answer must be 1(1000*1000 times).

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          oh but downloading the full test cases is not possible

          Moreover it is highly unlikely that you will be able to debug your code with such a large input /output file

»
21 month(s) ago, # |
  Vote: I like it -55 Vote: I do not like it

Is it rated?

»
21 month(s) ago, # |
  Vote: I like it +46 Vote: I do not like it

Obligatory comment: "Hope the problem statements are as short as the announcement"

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Have seen you being quite responsive in the last contest. Keep up the good work, and well, wish a quality and balanced contest ;)

P/s: Yup, I still can't figure out the most optimal income when using Perun's ult xD

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Oh... This contest is even later than others T_T

Too bad I can't enter it because of... time zone problem...

Wish you guys good luck and high ratings anyway ^_^

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope my rating will be more than 1900. Then this contest is unrated for me. I don't like rated contest. My rating will down if I don't do well in this contest. CONTEST, CONTEST and CONTEST ... RATING, RATING and RATING ... TRAINING, TRAINING and TRAINING ... ......

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    if you cheat in this contest, this contest is unrated for you too, and if nobody discover it, you can have a high rating:)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

Good luck to all

let's see, can i be a Candidate master at the end of this round or not ...

wish me luck... :)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good Luck!) Hope you will be a Candidate

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    why people doesnt like this post whats wrong about it

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      He didn't get cm :\

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        sorry,what is cm?

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Candidate Master

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you're right, i was far away from my ideal performance last night ...

        too upset for it... :(

      • »
        »
        »
        »
        19 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        well ...

        now i'm :)

»
21 month(s) ago, # |
  Vote: I like it -6 Vote: I do not like it

So sad that magic is over, can't troll with different colored grapes anymore :(

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I wondered what is different from participant division 2 and division1

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    -The Blue Color and all the colors below it are for Div2 contestants.
    -the purple color and all the colors above are for Div1 contestants.
    -Div1 guys can participate in Div2 Rounds unofficially.
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

really awesome, wait for some blossom

»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

A prime number contest!

»
21 month(s) ago, # |
  Vote: I like it -19 Vote: I do not like it

not u again

»
21 month(s) ago, # |
  Vote: I like it -23 Vote: I do not like it

How to download Test #15 of 650C Table Compression?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Unfortunately , the large inputs can't be previewed completely. if you stuck with the problem you can see the tutorial of the contest (here). if you still stuck , you can check out the Accepted solutions (here).

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

"Yet the statements are guaranteed to be short :)" this is the best announcement so far.

»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Yet the statements are guaranteed to be short :)

Thank you very much:)

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Unusual early scoring!

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

"Codeforces и Polygon"

Learning some russian.

Learning everywhere. :)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Learning so much that you start to understand Croatian. (Source: COCI 2016/17 Round #6 solution, p. 4, line 8)

    Let Pa < Pb i k * Pa ≤ Pb < (k + 1) * Pa.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Hope another great problem set from this amazing head. Big chance to rise up. CF is too good to stay away from. :)

»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

Can anyone help me with one problem? I have good answer on test 2 on my computer, but on codeforces I get WA no matter what I do. Obviously compiler settings or something isnt same. Just visit my problem and check last submissions, problem C from few rounds before. 34983468

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Test ur program on custom invocation and u will undrestand why got WA.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

It's quite strange no one noted that this round coincides with CSA round #68 tomorrow! Can't you just delay it 30 more mins? GreenGrape

UPD: the contest is delay 40 mins!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    More like, CSA coincides with Codeforces Round 461.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      linguistically, is there a difference?!

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I mean, CSA consistently hosts contests only in that time slot.

      I guess it went under the radar since they start 30mins earlier until recently.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    CF round moved by 40 minutes.

»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

Glad to hear this: Yet the statements are guaranteed to be short :) Looking forward to it !!!

»
21 month(s) ago, # |
  Vote: I like it -11 Vote: I do not like it

How to download Test #15 of 650C Table Compression?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Okay, this should be the last time I see this anywhere.

    You cannot do that. At all.

    (Well, except if the problem setter provide the full package publicly).

    For convenience, all test cases are compressed in case they are too big, so large input/output files are near to complete omittance.

    Usually, if you get stuck with a big tests, it can only mean a few things:

    • You ran out of memory (MLE verdict).

    • You ran out of time / your algorithm was too complex (TLE verdict).

    • You handled the undefined behaviors poorly (WA/RE verdict).

    These tests are mostly used to tests how a code works against large input streams, and not to be corner cases, so please check your own source code for places that can be optimized, not just spamming the blogs all the time.

»
21 month(s) ago, # |
  Vote: I like it +34 Vote: I do not like it

Normal guy's Imp.

Codeforces member's Imp.

»
21 month(s) ago, # |
  Vote: I like it +117 Vote: I do not like it

Is it legal?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    I registered him manually, just a prank ^^

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +54 Vote: I do not like it

      How is registering someone in a contest a prank?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        It’s just weird so a little funny. Pseudo will be like “wtf, dude” .. hence.

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Seems someone also wanted to prank you and registered you manually :P See you on leaderboard :D

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        This will be the first time someone solve all problems in 1 minute :D

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

I am gonna solve A, B and C today !

»
21 month(s) ago, # |
Rev. 7   Vote: I like it +55 Vote: I do not like it

Wow :O Rounds

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Two line summary of the announcement :
1. The statements are guaranteed to be short :)
2. There will be six problems with the following scoring: 500 — 1000 — 1250 — 1500 — 2000 — 2750

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

The time is a little late for me,but I am still glad to take part in the round.

It's really a good chance to train myself. :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I just want to say it's too late for Asian contestants . Hope I will stay alive for being such late......

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    One hour earlier, but yeah, I feel you, dude...

    12:15 AM in UTC+7 (Hanoi, Vietnam). Uh-oh...

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope I can become Expert!

»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Sanwli saloni, adaayein manmohni Tere jaisi beauty kisi ki vi ni honi Thande ki botal main tera opener Tujhe ghatt ghatt main pee lon Coca Cola tu ROUND GONNA BE AMAZING !

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    You Should Behave On website like codeforces , though fun is necessary , but people seach for good comments over here . I hope you understand it ! Good Luck for contest .

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's see How this go?

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

i think i will be green this time,thank you GreenGrape.

»
21 month(s) ago, # |
  Vote: I like it -24 Vote: I do not like it

is it rated??

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can't wait.....

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

Again a round with near 7000 participation :)

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope the long queue is fixed before the contest starts

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I hope the int vector is fixed setprecision(10) after the contest end ;!

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it
How's this possible?!
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    What's wrong? I thought you can lock the problem as long as you have the "Pretest passed" verdict, irrespective of whether you get hacked or not. Correct me if I am wrong.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Nope, you can't lock after you got hacked. But I think it happened because times are very close.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh okay, that's interesting. This probably happened because of the long hack queues today.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Contest of hacks... :D

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

very long queue in hacks

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

HackerRank will be proud of this contest

»
21 month(s) ago, # |
  Vote: I like it +27 Vote: I do not like it

I think this contest are more "Successful hacking attempt" messages than "Accepted"

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

A round full of hacks. Even one of my friends hacked me, nice contest

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hackforces in a nutshell...

Anyway, to be serious, maybe it was just me, but I think the scoring is still a little bit underrated. This should be 500-1000-1500-1750-2250-3000. C is sufficient to be called a Div2C, D is somehow quite twisted (got 4 WAs verdict on the 4th problems, all on pretest 4).

Not really sure about my opinion about E and F, coz' I have just read it for a short while.

After all, it was fun actually. And these Imps are just cute ^^

UPD: I took my words about D back. Somehow I wish I could think sharper...

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Can someone please provide explanation for third testcase of problem E.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I think you are confused just like I was — summoning a bird doesn't increase your mana, it increases you maximum mana.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Take 1 bird from the first nest (you don't have enough mana to take two birds), take 10 birds from second nest (your mana capacity is 17 and you have 15 mana so you can take them all).

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is solvable with radix sort?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I just used normal sorting with a comparing function that returns numS[a] * numH[b] > numS[b] * numH[a]

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hell man! :'( I tried to do it with normal comparison too but that condition didn't pop up to my mind! How can you prove this works ?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Given a string s, denote f(s) to be the number of subsequences 'sh'.

        Now given strings s1, s2, ... sn, it is easy to prove that if we denote xi, yi as the number of 's' and 'h' in string si, that .

        To maximize our desired value, all we need to look is the value .

        For n = 2, it's trivial that the comparing function wewark described works.

        We will induct on n — say the comparing function works for n and we prove it works for n + 1.

        Clearly, , as after deciding which sn + 1 to choose, we are left with optimizing the value with n strings. (induction hypothesis is used here)

        Now, all we need to do is prove that we need to put sn + 1 as the string with the highest value. This is simply greedy, easy to prove.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let's assume we have two strings a = sshhh and b = ssshhh.

        we can do a + b = sshhhssshhh.

        And b + a = ssshhhsshhh.

        How many sh's we got after this concatenation?

        We can note that this value is numS[a] * nums[b], because we didn't lose any sh's that were in a or in b, so what we got is .

        The same logic works for .

    • »
      »
      »
      21 month(s) ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Do you have a formal proof of such comparator?

      UPD Just came up with your idea.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got it, thank you all.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

The 1st problem made for the hack..

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Idea behind C ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For small Ks (probably <= 1000) you will find two exact values, so just implement

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    just do it with brute force :)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok. Limits are very large so how do you guarantee fast running time ?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it will find a pair soon

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          Thats what my questions is. How to prove that ?

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
            Rev. 2   Vote: I like it +7 Vote: I do not like it

            It is known that (a very important consequence/equivalence of prime number theorem) .

            For n, k to be good, (n + 1) must be a multiple of . So n must be like ek.

            This should be good enough, as running time is .

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it +13 Vote: I do not like it

              Or, say primes >10 will multiply, so it be over 10^18 fast...

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              Bruteforce works. :)

              This was my approach.
              gcd(1,2,...,k) = 1

              Therefore, lcm(1,2,...,k) = 1*2*3*..*k

              Also, since the remainders have to be distinct, one observation is that for any i between 1 to k, n%i should be equal to i-1.

              This means: n = i*C + i-1 ==> (n+1)%i = 0.

              Therefore n+1 should divide all the numbers from 1 to k. This also means that n+1 should be equal to the least common multiple of 1,2,..,k (in this case its just the product.) or any multiple of this lcm.

              Looping from 1 to k and stopping the loop whenever product crosses n+1. Product crosses n+1 easily by the time we reach i=50 in the loop. We return "No" in this case.

              If k! is equal to n+1 then we return "Yes"

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 3   Vote: I like it -7 Vote: I do not like it

        try this

        bool f;

        int top=0;

        for(int n=1;n<=100000;n++){

        for(int k=1;k<n;k++){

        f=true;

        for(int i=1;i<k&&f;i++){

        for(int j=i+1;j<=k&&f;j++){

        if(n%i==n%j)f=false;

        }}

        if(!f){

        top=max(top,k);

        break; }}}

        printf("%d\n",top);

        just look at the output and you will find out why it is possible to do it in brute force

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    People have this idea:

    Since you need to have all unique values till k. They should be obtained serially from 1,2,3,..k like this: 0,1,2,3,4,5...k-1

    so, n should be of the form: 2x+1, 3x+2, 4x+3, 5x+4, 6x+5, 7x+6,... all at the same time. But if something is of the form 5x+4 .. it cannot be of the form 2x+1 .. (coz one is odd and other is even, for even x, similarly chose a pair for odd x)

    Edit:

    The conclusion seems flawed. Maybe we can continue the logic like this:

    Number has to be of form: 2x+1, so 3,5,7,9.. 3x+2, so 5,8,11,14.. ... ....

    It kind of creating a sieve of eratosthenes, which generates a prime number.

    I don't what that gets us :)

»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

Locking after being hacked

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

how to solve D?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorting : )

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      merge or bubble

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        consider to string a and b

        let the number of 's' in a be a.S and the number of 'h' be a.H

        if you arrange a and b be ab

        the you will get a.S*b.H pairs

        so we know that if a.S*b.H>b.S*a.H then a should be in front of b

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the hack for A?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    if you donnot have a copy,you cannot get more copy

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Most common one: x 1 (while x is a positive even number).

    Expected answer: "NO" (as there are no initial copies to generate new ones)

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    0 0

    0 1

    1 0

    3 0

    2 1

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    2 1

    output

    NO

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    something!=0, y=0 and something!=0, y=1

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    4 1

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem A just burn my room

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong this this solution for E?

Let dp[i][j] be the max mana we have at tree i with j summoned in the trees before us. The max capacity is always w + j·b for a fixed j so we don't have to store that. I used long long int here and for dp table so no overflow. The answer is the largest i such that dp[n][i] is valid. I kept getting WA on pretest 5.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it's correct

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you use sliding window maximum?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    problem is that max summoned birds numbercan be ci * n = 103 * 104 = 107, so your array will have size dp[103][107].

    EDIT: I didn't read task carefully :{

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B? Seems easy cause lot of people solved it, but I only solved C and D.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    ans = 0
    for a = 1 .. n
      for b = a .. n
        c = a ^ b
        if b <= c <= n and a + b > c
          ans++
    print ans 
    
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Wow.. I'm a fool :) Thanks for your reply! (And all the others too)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    can you please tell me how to solve C?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try 1~50

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      n mod 1 , ... , n mod k has to be different. but you can easily notice that n mod 1 is always 0. So, n mod 2 must be equal to 1, because n mod 2 is 0 or 1, but it cannot be 0. ... n mod i must be equal to i-1, which means that n+1 is divisible by 1, 2, ..., k.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For a <= n, b <= n, let c = a ^ b, if all other conditions hold, then increment answer

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    a^b^c = 0 implies a^b = c. So bruteforce for a, b, and check if the 3 numbers can form sides of a triangle.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can iterate through all possible cases of a and b. c can be calculated by bitwise xor:

    As a xor b xor c = 0, we can agree that c = a xor b.

    If c is not lower than a or b, and not greater than n, and a,b,c forms a non-degenerate triangle (simply check that if all 3 inequalities of triangles are proved right), then you can add 1 to the answer.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Simply iterate over all a, b values . Check a + b > c, a + c > b and b + c > a

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I actually passed it with brute forcing which is O(N^3). It gave me 780ms even though it doesn't seem to be the intended solution.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Your condition ( c < a + b ) in the third loop in your code makes it about O(n^2) i belive

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        it is still O(n^3) with very small constant.

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Test for hack C: 1 2

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't it "yes" ?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Yes. Many people (me too) have writen: if( n < k ) cout << "No";

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Bad luck, man

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        fortunately I had written n<=k so it failed pretest and I was able to correct it. and now i'm purple.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pretty sure this is the case that got me

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F? I tried taking all N numbers initially and consecutively removing the one which will decrease f(I) the most but such that f(I) ≥ k will remain true. Just plain intuition, didn't work.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I bruteforced n<=17, implemented it for larger n, it worked well for all local inputs. Still kept getting TLE on the 7th pretest. I just wonder whether it was my complexity, I/O, special countertest designed to make this kind of solution fail...

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Explanation — Problem F

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Man, them noise and echo are simply unbearable which makes your speech unrecognizable.

»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it so interesting to post one picture several times?

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

In question D, what is the pretest 4?

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

I think there should be a limit on the number of hacks for each problem... Yeah hacks are a part of CF, but when a hacker with ABC has more points than a non-hacker with ABCD, I think there is a problem.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me some idea for 922F - Divisibility

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    for i = 1 .. n
      for j = i .. n, j += i
        d[j]++
    if sum(d) < k
      print no
    otherwise, kick out some numbers > n/2 - since they do not have multiples - so  that number of pairs will decrease to k
    
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone help me find why i was hacked in problem C? 35018691

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Short statements not means a lot of hacks.

»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

This was the biggest slaughter since I started to participate at contests

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

When will the system testing start ?

Update: System testing started :)

»
21 month(s) ago, # |
  Vote: I like it +37 Vote: I do not like it

When someone asks how life is going on?

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

While everybody is discussing today's contest, I just found my love <3

Thanks Mike :)

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +75 Vote: I do not like it

Isn't it obvious that current hacking system sucks? It's a brilliant idea, but really bad realization. Hacking should give you points (maybe even more than 100) if you find hidden not obvious bug in someone's code. But if you just take n = 0 corner case in div2A and it gives you 1500 points that's so unfair: you get that much points not because you are smart or your debugging skills are better than average, but because you have gray guys in your room who always do this mistake.

That's why I think that hacking points must be not a constant, but a function, which depends on how much hacks there are on the problem.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    if problem difficulty is 500 points so on one hack your receive 100 is 20% but if problem difficulty is 2500 points so on one hack your receive 100 is only 4%

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    til i am a grey

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Agreed. I hacked 18 solutions (Problem A) using only two test cases And guess what? My own solution missed one corner case and I got WA in system test. But 1800 points gave me an unfair advantage.

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Many among you would be disappointed because of all the hacks, but I feel that the problems were super exciting and I enjoyed all the brainstorming while getting hacked.

+1 to GreenGrape

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

 I don't know why, but my submission got stuck at test 39 for last 10 min.s. I am on page 6 of filtered list

»
21 month(s) ago, # |
  Vote: I like it +57 Vote: I do not like it

When you find one of the testcases for A  hackerman.jpg

»
21 month(s) ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I think that there is a problem with D testcases. This is my AC submission.

The problem with my solution is that the comparison is made entirely on integers, and therefore it could overflow.

I'll try to generate the testcase, I think that:

2
sssss...ssssssh
hhhhh...hhhhhhs

is enough.

EDIT: oh yes, I think it was enough. My solution gave 50000, but when reversing gave 2499950000. I don't think I'm the only one who failed for this.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's actually quite strange since tests 11 and 12 are made exactly to counter this.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I would like to remember that overflow is an undefined behaviour, so anything could happen, even getting an incorrect AC (A guess for why this happens is that the compiler may do some simplifications like x*y/x = y — avoiding the calculation that gets the overflow — maybe something in that line is what happened)

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I tested it using custom invocation, and it gives the incorrect output there (50k instead of 2499..etc).

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, I think I know what's happening here. My submissions treats different the strings consisting of only 'h' or only 's', so that's why my submission passed.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        lucky you didn't loose 100 points on tc 11.:)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    35024915 this solution gets tle on your test, if i am not mistaken. if so, D should be reevaluated

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Looks fine to me. Total characters are 200000.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah, i realized that i tested it wrong right now, sorry

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

long long contest! #define int long long accept my C and D :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A states: "Initially, Imp has only one original toy. but system test 20 tests for 0 (ZERO)!!!!!!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Print "Yes", if the desired configuration is possible, and "No" otherwise. so when input is 0 you should say no because he have 1

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have read again the problem before seeing your reply and come back here to delete my post, but now i leave it. Of course you are right.

»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Can't believe my STUPID code for C got pretests passed even and finally failed on test 76th!!! I used k instead of i in my loop.

Failed.

vs

Accepted.

»
21 month(s) ago, # |
  Vote: I like it +13 Vote: I do not like it

Couldn't proof the solution for C during the contest. But now, I think I got a proof.Correct me if I'm wrong plz.

If the answer for n is "yes", then for all i from the set [1,k] will have distinct remainders.

We can easily see that for all i [1,k]

n mod i == i — 1,

so, we can say (n + 1) mod i == i == 0 ;

That means all i [1,k] must divide (n+1) simultaneously.

Which means (n+1) must be divisible by the lcm(1,2,3,........,k).

Now the lcm(1,2,3,.........,k) would be > 1e18 when k is > 41(or something) .

That's why the brute-force solution worked.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

ohuenniy round

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

who is sorry-haghani ?!

HAGHANI ...

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain? :( 35036774 35011492

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Solving the B in O(n^3) no problem... i would say a O(n^2) solution was intended but anyway: http://codeforces.com/contest/922/submission/35039399

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

 Hello, world!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my code giving runtime error on test 5 in D : Link

»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

This was one of the best and most interesting contests on codeforces that i have given. So much of hacks and good difficulty distribution i should say ,awesome GreenGrape

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

GreenGrape has never been Green on Codeforces.

»
21 month(s) ago, # |
  Vote: I like it -29 Vote: I do not like it

contest was shit , weak pretests

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't understand A number problem. please, anyone, help me to understand this problem. problem link : http://codeforces.com/problemset/problem/922/A thanks

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you start with o. Then you do magic copy to get additional o and c.

    Now you have : o,o,c

    Next you do magic copy on c and get additional c and c , so a total of 3 c,c,c.

    Likewise.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.com/contest/922/submission/35048494 why i am facing runtime error thanx in advance

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    try swapping these statement in your comp function if (!h1) return true; if (!h2) return false;

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But what is logic behind this swap statement

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        If 2 equal objects are passed it should always return false. before it could return true.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem B, O(n^3) without pragma 35154154....using pargma only make it a little faster..35129118

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B, why (1,2,3)is not a valid set?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because it's a degenerate triangle (1+2 = 3) the

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! A triangle! thanks, I should learn to read the question carefully!