By zeliboba, 9 years ago, translation, In English

Hi, Codeforces!

Codeforces Round 317 will take place on August, 22 at 19:30 MSK.

The round is prepared by AimFund employees: Kostroma, riadwaw, yarrr, gchebanov, ArtDitel, SirShokoladina and zeliboba.

Scoring system will be static.

Thanks to Mike Mirzayanov(MikeMirzayanov) for brilliant platforms Polygon and Codeforces, problem coordinator Max Akhmedov (Zlobober) and Maria Belova (Delinur) for English translation.

Top 200 div1 participants will be awarded t-shirts. To learn more about AimFund please refer to our previous post.

This round is prepared as part of "5 years" Codeforces program as our present to community. This round is the first Thanks-Round devoted to companies donated significant money.

We wish you good luck and high frequency rating!

P.S: scoring 1 div 750-1250-1500-2000-2750. 2 div 500-1000-1750-2250-2500

P.P.S. Top-20 div2 participants will be awarded t-shirts.

Analysis

P.P.P.S. Dear friends. We are pleased to inform you that t shirts delivery will be under way next week. We hope you will really like them. Our sincere congrats again to you all!

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

| Write comment?
»
9 years ago, # |
  Vote: I like it -263 Vote: I do not like it

If you in div2 and you want win T-shirt upvote this comment

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

    You know if they do that nothing changes...

    Cause all of div.1 programmers will join in div.2 by another account and not only you won't get any t-shirt but also you may have worse rank and rating...

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

      Would be interesting with 10 extra T-shirts. For the first to solve each question.

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

        Hmmmmm... :/

        It's a good idea at all but again nothing changes for div.2 users i guess...(at least for problem C,D,E div.2)

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

          Be careful. When someone says 10 extra T-shirts, It means first accept for each question and each division.

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

            I knew that...

            But the div.1 participants again will join div.2 and they have better chance to get t-shirts(also they can use 2 accounts and if they didn't success to get t-shirts in div.2 they will fight for top200)

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

              Maybe you are right, I was not careful, I have to accept my mistake.

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

    Really? Why do you think all the people are like you? Contests are for challenges and learning more.

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

this round is not combined. so "Top 200 participants" means?

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

    Top 200 of Div. 1 according to the email they sent.

»
9 years ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Is it rated round?!

»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I think it should be combined division round :)

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

    Sorry, but we haven't got appropriate problems for combined round.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Then, Top 200?

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

        Top 200 will awarded T-shirts

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

      Okay, but it's a bit sad. Combined rounds are great :P If you want, and if you have time for it, you can think about change it to combined round, for example taking some problems from div2, other from div1 and maybe add one additional problem? I think cf community would really enjoy it, am I right? :D

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

        "Combined rounds are great" — no, they are not. Actually I'm very happy that this round will not be combined.

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

          Why? I'm actually unsure on the matter and I think it'd be interesting to hear opinions from both sides.

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

            Basically because there are huge rating rises and problems tend to end up unbalanced with too many easy ones for a red (that's a thing with normal rounds as well, but a gap between C and D out of 5 isn't as bad as a gap between F and G out of 8).

            The authors of the round probably realised it.

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

      yes,separate round gives more learning opp. to the newbies .

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +57 Vote: I do not like it

    Am I the only one around here,

    who feels that combined division round causes worse rating inflation.

    My friend increases rating very heavily, even skips a color (blue to orange, skipping purple) on a combined division round.

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

      I think the reason is that many who have been away from competitive programming for a while comes back for the combined rounds. Their rating will be at the level when they were at their top, but now they are rusty so they will lose points on average meaning that everyone else will gain points on average.

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

        But because of rating inflation, those who comes back after a long time doesn't have very high rating.

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

          Rating inflation only effect div 1 since the flow between div 1 and div 2 is so slow. That's another thing, rating can only enter div 1, rating never leaves div 1 except for combined contests. I wonder how TC handles this, they don't have combined contests right and the rating have been pumped from div 1 to div 2 for like over 10 years right?

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

          I checked some old accounts now, most have rating curves roughly like this:

          http://codeforces.com/profile/hos.lyric

          You can't really see the rating inflation on them since most of them haven't gained anything the past 2 years even though they played continuously. If they had stopped for 2 years instead and then came back they would definitely have too much rating!

»
9 years ago, # |
  Vote: I like it +76 Vote: I do not like it

There were old legends about some company planning to run their round within the next month... :D

Looking forward for your round guys!

»
9 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Div 1 users : "It's time to register for Div.2" :((

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

    why would div1 users want to register in div2?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      cuz when its not division combined , getting Tshirts in div2 is easier in for low rated div1 users :)

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

        It's written that top200 in div1 will receive t-shirt.

»
9 years ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

Oh Yes,I think this contest is like Goodbye contest and All user Receive high rating

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hello, what do you mean by "Scoring system will be static" ? what's the difference with the last round ?

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

    "Scoring system will be static" it is mean, that scoring system won't be dinamyc (max scores for problems you will know before round)

»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Though its very obvious only Div — 1 will get t-shirt and they should get but it will more exciting for all Div — 2 coders like me if we get a chance to complete with Div — 1 coders . A collaborate Div 1 & 2 round will be more interesting for everyone and Div — 2 coders get a chance to win t-shirt also .

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

    If it's combined, ((we will fight to win a t-shirt but nothing will happen as usual)) :D

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

      I didn't perform well any of previous collaborate contest but i like these contest most because one can get the proper picture of his/her current state . So just the opportunity to participate with Div 1 coders is enough for me :D

»
9 years ago, # |
  Vote: I like it -31 Vote: I do not like it

when you want to give t-shirts. you must prepare one both division contest.(like round Codeforces Round 300)

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

thanks for preparing this codeforces round.

»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Where can we see the t-shirt's.

»
9 years ago, # |
  Vote: I like it -24 Vote: I do not like it

That's sad for div 2. Even "random x from top y" method would be great. But thanks for the contest anyway.

»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

This would be a good time to get red + T-shirt!

»
9 years ago, # |
  Vote: I like it -30 Vote: I do not like it

I guess if they had 400 t-shirts they would give 1 each to both division's 200 toppers. But they only have 200 t-shirts.

»
9 years ago, # |
  Vote: I like it -23 Vote: I do not like it

how about allowing div 2 users to submit div 1 D and E if they solve upto div 1 C ? ( no extra time )

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Yeah, surely, imagine how exactly that should look like and how big changes this will demand in whole system of Codeforces ( ͡° ͜ʖ ͡°)

»
9 years ago, # |
  Vote: I like it -37 Vote: I do not like it

if a div1 user makes a fake account for div2 contests it shows that he/she is more programmer than human!

i think being human is more important than being programmer!!!!

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

    If you believe in God,... It's good to know that "**God is also a programmer**".

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

    of course every programmer is a human :)

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

      Depends on if you consider computers that can program as programmers.

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

        We are all machines developed by nature and evolution :)

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

          That is debatable. Prepare for downvotes, my friend :(

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

        I think we are computers which run the programs written by God. So God is a programmer.

»
9 years ago, # |
  Vote: I like it -53 Vote: I do not like it

Will it be possible for you to provide T-shirts to some(your limit) top div2 rated contestants?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    i'll buy an account gg easy

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

    I don't know he got -30 by just proposing something. Seriously, what's wrong with these people? I honestly think that there can be very few people who can still perform in div1 top 200. And if you offer a very few T-shirts in div2 as he suggested, many coders in div2 can be challenged to perform well. It will be an inspiration for those who can win in div2.

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

      There will be a lot of fake accounts from div 1, because it's easy to win div 2 than being in div1 top 200.

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

        Yeah possible. But if one can win in div2 and solved same quality problems as in top 200 in Div1, Why not give a T-shirt? ( Since div1 and div2 doesn't have same problems, it is troublesome I guess).

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +43 Vote: I do not like it
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            In Codeforces Round 300, there are two div2 participants though :P. Imagine if you were one of those guys, and you don't receive T-shirt.

            But I see what you're saying. It is not gonna happen 99% sure.

            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              Rev. 2   Vote: I like it +37 Vote: I do not like it

              If you are good enough to get top 200 in div 1 then it takes just a single contest to become div 1 so they can only blame themselves for not doing the contest held a week ago.

              If it is the unlikely case that the person have only memorized solutions and thus can't reliably get into div 1 then you could argue that they aren't worth a T-shirt even if they did well in this specific contest.

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

        I mentioned that.

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

    I did not find too many points.

»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I speek Croatian and Croatian is similar to Russian, can I also apply?

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Good luck :)

»
9 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Bless All!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I will solve 2 questions today

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone! :)

»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Is scoring the same for both divisions?

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Last one isn't usualy 2750, right?

»
9 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Tough set. I guess those t-shirts are really special.

»
9 years ago, # |
  Vote: I like it +124 Vote: I do not like it

div0 contest :))

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

    I think that's a great idea. One more division for the Gods :)

    But it'd require to prepare 2 more problems for a contest...

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Did anyone else get WA on problem B test 10?

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

    So many times. And I think I figured out why: you are supposed to take the least cost sell orders, and print them descending. I think :P

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

      I coded A and B very fast but I faild at the same point, Damn my luck.

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

      From what I see in statement ,in the order book for sells they are sorted descending.Even if you want to take first s lowest agg sells. Tricky statement.

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

    Yes. Then I found that I hadn't noticed this : "A buy order is better if it has higher price and a sell order is better if it has lower price". After considering it, passed.

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

      Then I got WA for some other reason, wonder what. Any tricky cases?

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

      I noticed this with 1 minute left. I barely missed the submission window(was typing the cout statement once contest ended, last line of code -.-)

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

      Ah, that makes sense. Such a shame that there was only one example.

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

    Along with 4 failed attempts, yes (

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I am impressed. Thank you for round anyway.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So light pretests for div2 C( My solution with O(n^2) complexity passed them, but I know there will not be such luck on final test. So I interested how to solve it faster?

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

    How would be a n^2 solution for it? Couldn't even think about it!

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    Just calculate the inverse instead. The total amount of ways you can increase is (l + 1)*(l + 2)*(l + 3)/6, then you just remove all cases that don't work.

    You can't form a triangle with a set of numbers if one is larger or equal than the sum of the other two, so just iterate over all increases (O(n)) of a, b, and c and for each increase reduce the answer by the amount of ways to increase the other two such that their sum is less than the largest one.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it +29 Vote: I do not like it

      Like this:

        ll f(ll a, ll b, ll c, ll l) {
          if (a < b + c)
            return 0;
          ll d = min(l, a - b - c);
          return (d + 1) * (d + 2) / 2;
        } 
        
        int solve(ll a, ll b, ll c, ll l) {
          ll ans = (l + 1) * (l + 2) * (l + 3) / 6;
          for (int i = 0; i <= l; ++i) {
            ans -= f(a + i, b, c, l - i);
            ans -= f(b + i, a, c, l - i);
            ans -= f(c + i, b, a, l - i);
          }
          cout<<ans;
        }
      
      
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is probably a stupid question, but why ~~~~~ ll d = min(l, a — b — c); ~~~~~

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          Its the amount of increases that you can distribute between b and c. Of course you can't distribute more than l and if you distribute more than a - b - c then the triangle becomes valid.

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

        nice and simple solution thanks :)

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        How is it intuitive that there are no overlaps? When you're increasing 'a', you also increase 'b' and 'c' On a closer look, when you increase 'a', and hence increase 'b' and 'c', for those values always 'b'<'a'+'c' and 'c'<'a'+'b' But this wasn't really intuitive :|

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

      Why the total amount is (l + 1)*(l + 2)*(l + 3)/6 . I am a little bad in maths.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It's probably stupid, but could you explain how did you get formula for calculating total amount? Thanks in advance.

      UPD: Same comment as above, sorry for duplicate.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    suppose we increase a,b,c by x,y,z

    fix z then the triangle ineq conditions reduces to let v1 = x+y,v2 = x-y

    1. x+y >= max(0,(c+z)-a-b+1)

    2. x+y <= l-z

    3. x-y >= b-(c+z)-a+1

    4. x-y <= b+(c+z)-a-1

    subject to above contrainsts,we hvave to find all such pairs such that v1%2==v2%2 and v2<=|v1|

    to do the rest, you need to analyse each interval properly.

»
9 years ago, # |
  Vote: I like it +61 Vote: I do not like it

the hardest contest i have ever seen.

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Div1 — A today is so mind-blowing (harder than Div1-B IMO). Is there a simple way to solve it?

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

    I tried iterating through all ways of adding an amount to a and then binary searching for the min and max values for b, therefore fixing c but could not get it to work. Is this a valid solution?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

... And how to solve problem A (div. 1)?

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How div1 B is solved by a lot of contestants it's very hard!! maybe a lot of them are going to fail system test?

div1 C is far easier than div1 B but they both have almost the same points!! I didn't submit my solution because of this reason

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

    I can prove my solution at div1B and it's not that hard

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

    div1 B is dynamic programming + some greedy approaces. Actually if you can notice, that elements, which absolute difference is taken are located in non-intersecting sequences. Also it is obvious, that elements in such sequences are neighbours in sorted array. So you should find the optimal way of splitting the sorted array in "blocks", minimizing the target function. In fact there is no more, then 2 different length of blocks are possible, so you can do DP in k^2.

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

      Yes, this is the only observation required to solve this problem that there wont be more than 2 different lengths. Thanks for the explanation dude :)

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

    Not exactly. C demanded a lot of stupid code, while code for B was pretty easy. C was not idealogically complicated, but not fun to code and multiedges stopped me for half an hour.

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

      I have implemented it in simple way:

      handle cases for variables appearing only once and variables appearing twice but in same sign and check which nodes are satisfied.

      put all unsatisfied nodes in priority_queue such that the top is the node with least degree, each time pop a node from queue and select arbitrary edge connected with that node to make that node satisfied , then delete that edge(the other node degree is reduced by 1) , if in some moment degree of a node which is not yet satisfied is 0 then "NO" otherwise "YES"

      didn't even have to check for trees or search for cycles

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

        and you even don't have to handle cases you described separately.

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

    You wont solve 1 C if you haven't seen the problem before since it is a huge research topic.

    Also you wont improve if you care about points, better to fail and learn than to not try at all.

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

      This particular case it's not a huge research topic and I think I solved it(or at list I have a good and proved idea, maybe some bugs but I have a good idea) without meeting it before

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

        Oh, I read the problem wrong >.<.

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Aparently, me too=)))I thought that you can have just -2 and 2 ore just one of them but you can have two of -2 or two of 2 which is very easy tot treat.I don't really understant why did they do that :(

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

    Div1 — B is just DP: imagine we will build each subsequence {a(i), a(i+k), a(i+2*k), ..} seperately, and to make the result minimum, each subsequence must be sorted. We will have to build cnt1 = n%k subsequence of length n/k+1 and cnt0 = (n-cnt1*l1)/l0 subsequence of length n/k. Sort array a in ascending order. In order to minimize the result, there must be no pair of two subsequence that intersect with each other. So, this problem could be reduced to: finding a way to split array a (after sorted) into cnt0 continous subsequence of length l0 and cnt1 continous subsequnce of length l1. Notice that cnt0*cnt1 <= n, so a DP with complexity O(cnt0*cnt1) would work.

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

      You wanted to say cnt0*cnt1<=(k*k), no?

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

      Wow, that's actually a solution I was trying to code during the contest! Can you please describe your DP a bit more detaled?

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

    B was very nice and much easier than A, at least in my oppinion. I needed about 10 minutes to figure out the dp after I read it but I still have no clue about A :(

»
9 years ago, # |
  Vote: I like it +36 Vote: I do not like it

That CNF-2 (Div1-C) is easy but hard to implement (many corner cases)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    If you compute the number of degenerate triangles and substract this number from the total one is very easy but it's hard to think.I guess this was the slution without corner cases

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

      Did you mean Div1-A?

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

        Yes I saw it later when I already had -30 contributin :)) but it didn't make sense to refer at div1C.There were 3 cases in my solution and I treated each of them in one line.Any way sorry for misunderstanding

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

    It may be implemented without corner cases:)

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

2E/1C was quite interesting I know what I was supost to do but I didn't have time to implement it, stil I liked that problem. Can't wait to see the editorial :)

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

    Yeah basically the problem is equivalent to "Given a graph can you direct it's edges so that each node has an in degree at least one".

    You can always do that as long as the graph is not a tree. And if it isn't finding a cycle and then directing all edges outward from that cycle does the trick.

    But yeah I also ran out of time to implement this.

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

      ... as long as each component of the graph is not a tree ...

»
9 years ago, # |
Rev. 3   Vote: I like it +22 Vote: I do not like it

number_of_contests_with_only_D++ :(

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

    Why would you write underscore at the end of variable? Awful.

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

      it was not the only stupid mistake anyway :P

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

      Actualy it is widely used convention if we are talking about nonpublic attributes of classes :).

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So Cool. Congratulations to the winners.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

And is this be standard from now on. New round every Saturday?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I got TL on the 6th pretest (Div. 2 C), and that in 2 minutes before closing... I... I could solve it... Arghh!

Anyway, it was a great round!

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

    Me too, but it seems that there's a O(n) aproach, so we couldn't solve it actually hahahaha

»
9 years ago, # |
  Vote: I like it +106 Vote: I do not like it

Why is system testing stuck at 75%?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to change something in code after the contest has finished if it is only 1 operator , I mean switch = and <= ?

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

    No.

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

    yep change it and also you can submit it in practice :D

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

    Why not? Every one can. But really do you think it will be judged again?

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

    You can submit in practice after the grading finishes, but it will not affect how you performed during the competition.

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

    Sure, why not? You are allowed to change up to 10 letters in your solution after the contest, so remember that your variable names should be short, because that way you will be able to do more changes.

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

      haha :P

      Some contest allow minor changes like that , that's why I asked

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

        "Some contest allow minor changes like that" — yyyy o_0. Can you give me an example of at least one :P?

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for preaparing this great round, also thanks for t-shirt :D

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

from 25 to 1300, such is life in codeforces.

»
9 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

The contest was great !
Really hope that Round 318 will also give 200 T-shirts.

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

typically how long does it take before the rating changes? it was a great (hard) contest! :P

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

could any body please say me what is the calculating way for first contesters?

»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I think the problem statement for Div 1 C is unclear. In the problem statement it is written

We know that each variable occurs in at most two clauses (with negation and without negation in total)

Therefore, I thought that when a variable appears twice, the variable and its negation will both appear. Fortunately, there is test case 3 that shows that this is not true, but I did not have enough time to update my solution when I realized that.

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

    two in total means 0+2 and 1+1 and 2+0 , no ambiguity in that

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

    I don't see how that can be understood like this. Moreover you have "at most" which suggests that sometimes it can be one (or maybe even zero?), so there will be no place for variable and its negation at one time.

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

      Yes I know that there can be zero or one of the variable. What I meant is that the addition (with negation and without negation in total) sounded to me like we can get any subset of the set

      {negation, without negation}

      and thus in this case {negation, negation} is not possible.

»
9 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Just a wrong character on code of A, and using 109 as inf on code of B but answer can be 2 * 109. Why I can't learn anything? :(

»
9 years ago, # |
  Vote: I like it +89 Vote: I do not like it

Late for the contest for 30 minutes, still got the T-shirt

image host

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

what about editorial??

»
9 years ago, # |
  Vote: I like it +90 Vote: I do not like it

Screencast

If you wouldn't shed tear when I type long[] allCumulUpds = new long[n + 1]; instead of m + 1 you have no soul

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

    Authors have soul, I am sure. I remember Bambi’s Mother Dies, Mufasa Dies, and so on when we watched this bug realtime in your submission.

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

      What does it mean to watch a submission realtime if you are author of a contest?

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

        Authors can open any solution during the contest. Also avaliable results at final testset.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    I noted that in this problem n denotes number of edges and m number of vertices, what will lead to inevitable errors, so I declared them as "cl" and "var" what makes it much harder to misuse them. Second technique I use is to always declare arrays of sizes of sufficient constants, here 3e5+5. Any of those two things will prevent you from making this bug :).

    EDIT: Heh, it seems that I messed up problems ^^. First remark is no longer relevant, however I guess second still stays.

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

      But 2nd technique may lead to other bugs, like Petr described in one of his recent weekly reports

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

        Hmmm, yeah, I guess you're sufficiently experienced to be acknowledged with both technique of making array of a 'just right size' and technique of making it big beforehand : D. Hence, my comment was probably anything new to you :P. However I use it like this for almost all my coding life and I don't remember any case when it caused a bug. Orrr maybe, concluding from what Petr has written it may prevent us from noting some bugs rather than cause them — I guess there is some tradeoff (pretty much like always). However I am a guy really prone to mistakes you did this time, so I will stick to my method.

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

    What tool do you use to parse contest problems ? Is there any github repo ?

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Aha ..T-shirt! It's my first time to receive gift from Codeforces.. Here is my question. When will the T-shirt be sent? I can't wait to wear the lovely T-shirt!

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone provide an editorial? Thanks

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

    As always you may ask specific questions in comments. Now part of tutorial is published

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

    With respect to C I would be very interested in a discussion of how to implement the problem well specifically the part of finding the cycle in the component of the graph and then directing all the edges.

    If one attempts to find the cycle with a DFS one processes nodes until an edge is found between the node we are currently processing and a node we visited earlier.

    It is very unclear to me how to write the recursive function so that once we find such a cycle we can exit the recursion and along the way store the cycle in some sensible way.

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

      What I do for this is maintain a DSU while adding edges, and then when an edge is found connecting two vertices in the same set, we know there exists a cycle from one vertex on this edge.

      Then, we can run findcyc() from such a vertex, keeping the current dfs stack, until it reaches the starting vertex again — which it must due to the earlier argument. Thus, our cycle is isolated. Another nice thing here is that we can direct the edges along the cycle in findcyc() itself.

      Next we dfs() from every node on the cycle to direct the edges. 12656691

      Any other approaches?

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

        Come to think of it with the approach you describe (which I think is the nicest one) you don't need to find the cycle and then separately perform DFSs at all.

        If you start the DFS from the node on the cycle you can simply direct all the edges (that haven't been directed yet) away from the current vertex. This way every vertex has an edge pointing to it (the one that caused them to be thrown on the "stack") and eventually some node also has an edge to the starting node.

        So you only need one DFS per component assuming you can start with a node on the cycle.

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

      Not really proud of that code, but maybe you can get an idea how to do that by dfs: http://codeforces.com/contest/571/submission/12659401

      Condition on finding cycle is

      if (vis2[nei] && e != wh_var) {
      

      that means, I have visited that neighbour earlier and I'm not looking at the edge I used to be in current vertex.

      My dfs returns int. "If dfs returns nonzero value than cycle exists and returned vertex lies on a cycle and I have already assigned logical value to it". Whenever recursive call returns nonzero I stop executing and pass that value higher.

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

      You may also appreciate version with exceptions http://codeforces.com/contest/571/submission/12667656 :P. Finding a cycle can hardly be called 'exception', but exceptions can help you unwind stack of function calls without passing intermediate values.

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

      This is my solution: (I use outgoing edge instead of incoming edge) 1.Keep removing vertices with degree 1, and assign its only edge to it.

      2.Now there are only vertices with degree>=2. Find a vertex which has no outgoing edge. Starting from this vertex, find an unused edge and pass through this edge. Now we find an outgoing edge for this vertex. Keep doing this to the vertex on the other side of previous edge until a vertex which already has an outgoing edge is reached. It is guarenteed that we can always "go out" from a vertex with no outgoing edge because there are at least two edges connected to it.

      3.If there are still vertices which has no outgoing edge, do step2 again. Otherwise, orient all unused edges arbitrarily.

»
9 years ago, # |
  Vote: I like it +93 Vote: I do not like it

P.P.S. Top-20 div2 participants will be awarded t-shirts.

So genius that say this after contest :D

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

    Guys looked at the results and understood that participants from div2 earned T-shirts too, cause solved many problems. Why not?

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

    And now in next contest we'll see div1 guys playing with fakes in div2, hoping for such P.P.S. once again :)

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

      Add simple rule that he/she participated minimum 10 contest

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

        O_o

        So new users can't join the contests???

        Bad idea at all...

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

          Usually who win div2 — are div1 users. New user can't win contest or get top-20 in one contest.

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

            They can if they have done competitive programming in other places like icpc or tc.

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

            Ermm, having reached 3rd place in div 2 on my first contest, I beg to differ. And if you look at the standings, there are 4 more unrated people in the top 20.

»
9 years ago, # |
  Vote: I like it +24 Vote: I do not like it

First codeforces Tshirt :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

always getting wrong answer on 10th test case.iam unable to figure out .can anyone please help me :) .the link for the submission (http://codeforces.com/contest/572/submission/12670760)

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

    10th test was about wrong S and B priorities. You should write out B with bigger price and C with lower price.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

That P.P.S made my day... :3 :D !!! Thanks all... !!!!

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

Just asking out of curiosity, did you consider using the new dynamic scoring system with 250 points gaps?

If you did, what was the reason behind choosing the standard scoring system instead?

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    In short, all of us do not like the dynamic system, so we have not even considered it =)

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

      Why? So far, according to my contest experience, there were situations that dynamic scoring would have given more appropriate scores rather than standard but have not seen the same thing for the opposite. The only problem that dynamic scoring might cause was certain formulas that can lead to different points just because of 1 submission, but now it's only 250 points which is fairly good I think. For instance, it could have fixed the point distribution in this contest too, esspecialy for A-B and C-D.

      I've no doubt that all scoring systems common feature is fairness as far as it's same for all the contestants. But it would not hurt to make things better, right?

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

        Contests are supposed to be fun and dynamic scoring makes them less fun for me since its stressful not knowing how much the problems are worth.

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

          Well for me, it's more stressful when you do not know if the problem you are working on worth it's points.

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Then why do you gamble by skipping problem A, B and C? Usually A gives the most score per effort, then B, then C, then D and lastly E, so doing them in any other order is a risky gamble.

            Edit: While on the other hand with dynamic scoring the effort per problem ratio can be all over the place, usually A gives the least score per effort in those contests meaning that you must try to game the system instead of just focusing on solving problems.

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

              Because solving just A and B is boring and I want to give more time to harder and more interesting ones. If I would have started from A and B, there would be no time for D at all. The question is if you have the power to lead all of the contestants(by setting scores) would you encourage harder problems or not?

              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Since they can set the scores however they want they obviously want the easier problems to be worth it, if they wanted the harder problems to be worth more they wouldn't set A and B to be 750 and 1250.

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

    Oh, you're the first person I see which doesn't hate dynamic score :P. I like to know what is the value of a problem beforehand. Dynamic scoring often can lead to weird strategies like skipping A and B, because they will be worth 250 and 500 pts or sth like that. What matters is also strategy, not only problem solving skill and you have to admit that choosing D as only problem to solve was not best choice =). I guess that probably it was twice that hard to solve D than ABC combined, so what you did was probably harder than what I did, but my place was significantly better :P.

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

      I like dynamic scoring too, and I believe it would be more fair if it was applied for this contest , because how can a problem which is solved the most(problem B) have almost the same points as the problem solved by few people(problem C)!!

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

        Haha, that said just after stating that C was far easier than B http://codeforces.com/blog/entry/19863?#comment-247365 XDDD

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

          first problem I tried during the contest was B , but I couldn't solve it ,I thought it's harder than usual div1 B problems, so I moved to C , the idea came to me very quickly but it took me some time to code it, after finishing I saw that B was solved by a lot of contestants even more than A , and C is solved by low number of contestants so I decided to give up.

          I posted that comment immediately after the contest finished I was trying to express my surprise of number of people who solved B , I didn't know that I'm only missing an observation to solve B , it wasn't that hard as I thought.

          in the end, a lot people solved B and that's what matters so it should not have that much of points

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 4   Vote: I like it 0 Vote: I do not like it

            Just 329 people solved B, it was way harder than your average B problem. Also I really dislike contests where the easiest problem is too hard since then lots of people chickens out and it gets hard to gain rating.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

just a friendly reminder, it's analysis not analisys (last link of the blog)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it normal that I got no message, e-mail or anything regarding the T-shirt? (I got 3rd in div 2.) I added my address details to my profile the day after the contest. This was my first time competing so I'm not really sure how things work around here..

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

    Only for Top 200 Div.1 users.

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

      At the end of the post, added after the contest ended: "P.P.S. Top-20 div2 participants will be awarded t-shirts."

»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

When will the T-shirts be sent?

»
9 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Will the t-shirts be sent to other countries like China?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I still haven't received my T-shirt. Is there any information on when they will arrive (in the Netherlands)?

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

I still haven't received my T-shirt. Will it still be send?

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

    Hi, all T-shirts have been sent as I know.

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

      Was that long ago? I think my address is (and was) up-to-date.

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

      Hi , even I haven't received my T-shirt please look into it

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

    I too haven't received it yet.Is there any mistake?

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Finally, just received my T-shirt today! Thank you Aim Fund, Thank you MikeMirzayanov :D