adedalic's blog

By adedalic, 17 months ago, In English,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #421 that will be held at June 27th, 2017 at 17:35 MSK.

Yes, it's my first round, and yes, it's another round from purple.

Great thanks to KAN for help in preparation of this round, dans for help on first stages and testing, Belonogov, white2302, hloya_ygrt, Perforator for testing the problems, and MikeMirzayanov for great systems Codeforces and Polygon.

As always, participants of both divisions will be given 5 problems and 2 hours to solve them. Scoring will be announced before the round.

Good Luck and Have Fun!

UPD1: Scoring is standart for both divisions: 500-1000-1500-2000-2500

We are working on the issue with problem A in div. 1. We will announce the decision later.

Due to the issue with problem A, the round is declared unrated. More details.

Nevermind all promblems, Editorial must be, so it's here.

Tags 421
 
 
 
 
  • Vote: I like it  
  • +43
  • Vote: I do not like it  

»
17 months ago, # |
  Vote: I like it -49 Vote: I do not like it

Good luck everyone! :D

»
17 months ago, # |
Rev. 2   Vote: I like it -84 Vote: I do not like it

Lol kek cheburek

»
17 months ago, # |
  Vote: I like it -121 Vote: I do not like it

Is it rated?

»
17 months ago, # |
  Vote: I like it -51 Vote: I do not like it

We should thank KAN for his help in the last 10 rounds at least =D =D

Thank you so much :)

»
17 months ago, # |
  Vote: I like it +48 Vote: I do not like it

Hope for short statements like the blog <3

»
17 months ago, # |
Rev. 3   Vote: I like it -76 Vote: I do not like it

Hope for short statements too. <3 Good luck for all.

»
17 months ago, # |
  Vote: I like it -77 Vote: I do not like it

Hope for short statements like the blog <3 *3

»
17 months ago, # |
Rev. 3   Vote: I like it -26 Vote: I do not like it

I think White-Beard is very lucky because his feedback still positive. I hope you good luck in contest my friends <3 .

»
17 months ago, # |
  Vote: I like it -13 Vote: I do not like it

anime?

»
17 months ago, # |
  Vote: I like it -87 Vote: I do not like it

I know what to ask to get 100 downvotes but I won't ;P

  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it -43 Vote: I do not like it

    you will get downvotes anyway lol so take a screenshot to your current contribution :P

»
17 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Everyone still wonders: Is it rated?

»
17 months ago, # |
  Vote: I like it +21 Vote: I do not like it

lord saves CF servers today, just submitted a solution and it's a 2 page long queue.

»
17 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Round 420 is also "rated"...

»
17 months ago, # |
  Vote: I like it -22 Vote: I do not like it

What is the motive behind announcing the scoring distribution just before the round? Or is it just a tradition being followed since quite long?

»
17 months ago, # |
  Vote: I like it -11 Vote: I do not like it

i hope this time problems does not have any bugs good luck every one :D

»
17 months ago, # |
  Vote: I like it -36 Vote: I do not like it

The blog of down votes

»
17 months ago, # |
  Vote: I like it -28 Vote: I do not like it

**The Rain Of Downvotes :P **

»
17 months ago, # |
  Vote: I like it -35 Vote: I do not like it

Hope we can have a better exam environment and problem statement :P

»
17 months ago, # |
Rev. 2   Vote: I like it -35 Vote: I do not like it

When you come to increase your contribution but gets downvotes instead.

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

    Why would you "come to increase your contribution"? Do you write comments just for meaningless internet points? Contribution should be the result of your comments, but not the reason for it.

»
17 months ago, # |
  Vote: I like it -12 Vote: I do not like it

Hope for better performance of the server..

»
17 months ago, # |
Rev. 3   Vote: I like it -15 Vote: I do not like it

The queue is long on the status page :( . Let us hope servers perform good in the contest :)

»
17 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Good luck to everyone

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

»
17 months ago, # |
  Vote: I like it +133 Vote: I do not like it
  1. Take a lot of screenshoots just in case.
  2. Take part in the round.
  • »
    »
    17 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    How do the screenshots help exactly ?

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

      He needs screenshots for the time when he is still Nutella in case he lose Nutella this contest.

      • »
        »
        »
        »
        17 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        "Nutella" as in ? P.S. Why all the downvotes ? I asked a genuine question.

»
17 months ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

A lot of of solutions in the status page got Denial of judgement :( !

Is the issue in the site ?

BTW, its the same solution but a lot of people try it to know why it got Denial of judgement.

»
17 months ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

The comment is hidden because of too negative feedback, click here to view it

»
17 months ago, # |
  Vote: I like it -29 Vote: I do not like it

F**k CF servers just before the contests :/

»
17 months ago, # |
Rev. 2   Vote: I like it +48 Vote: I do not like it

Make a wish for Akagi with 200 rating.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Eatint and Drinking? Oh, they don't exist

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, due to the unrated, maybe I have lost more than 100 rating.

    But...

    Where is my Akagi?

    (ノ=Д=)ノ┻━┻

»
17 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Only red coders are getting upvotes... Others not even getting an answer :P

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking at servers which one has the maximum possibility? delayed contest or Unrated again.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh my god ,I missed this turn! I don't know it comes so fast.Emmmmm……Ok,i know, it aims at making up for the last turn.So sad.

»
17 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Is my English weak?i have read 20minutes still cannot understand what the problemC want to tell me。

»
17 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Пиши контест говорили они, будет весело говорили они.

»
17 months ago, # |
Rev. 2   Vote: I like it +157 Vote: I do not like it

My story since past few contests:
1. Eagerly wait for contest to begin.
2. Contest starts. Open problems.
3. All problems long af, difficult to understand.
4. Lose interest, order dinner, watch BBT, eat.
Is it only me or others too that have this feeling?

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

    +1 :p

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you're not the only one

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

    I guess BBT stands for Big Bang Theory. Anyway, this strategy proven to yield the best results during the last 2 div2 rounds...

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

*Rushes to the contest scoreboard upon reaches home

*Realizes how few people managed to solve Div1AB even though they appears to be totally solvable to me

*Feels bad about missing a chance to climb a lot of rank

*Realizes there are only 218 participants.

Whining asides, I wonder why so few people are participating the div1 round even though the time is completely fine, not to mention uni students are having a summer break.

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

    Because A, B are extremely shitty, I guess

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So this is a contest consists of only purely mathematical problems, it's fresh!

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Writed solution for Div2B. TLE 7 test. Too much math. Even don't want debug it... Just want to know: is it bruteforce with ternary search?

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

    I think brute-force + math is enough!

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

    I fixed 2 points 1 and 2 and checked all the of the angle with third point. Say n = 5, so interior angle is 108 and increment in angle is 36 so possible values are 36,72,108. I dont know if it is correct

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

    The angles are integral multiple of (180/n)*i where 1<=i<=n-2.

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

    I think when you experiment with a few n-sided polygons then you realize that the total number of angles you can form with three points is n-2. Then you just iterate through all possible angles to get your optimal answer.

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

    The idea in my mind is about: Calculate the angles of 0-1-(n-1), 0-1-(n-2) ... iterately by using sine & cosine theorem, then just binary search for the answer.

    Say you are considering angle A-0-X with fixed A and unknown X, this angle equals to (0-1-2) — minus the angles at the two sides, which you can lookup and binary search from the preprocessed values, use binary search to find the two Xs which are just below & above the desired angle.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think what you try to pair V[1], V[i] and to a binary search for the third one.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this my approach :

    each angle = 180 * (n — 2) / n

    you can divide each angle to (n-2) parts , the degree of each part = angle / # of parts

    start withe one part and loop , each time add a part and optimize your ans.

    O(N)

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I actually did the same. At first, I precompute the angles, and then I loop through the parts. But got WA :( you surely used double?

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can then set that angle to a and solve for n to get a O(1) solution.

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

    It isn't much math, really. There's no need for ternary search. You have to consider the circumference the the polygon is inside, then the only observation you have to make is that after fixing the size of the arc, any point would suffice as midpoint. (consider a, b and c as points of the polygon. For simplicity, a=1. Also, a < b < c. Then, for every c you choose the angle formed by acb (in this order) is the same).

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

    How to solve B:

    First notice that any interior angle for a regular polygon is (n — 2) * 180.

    Second note that if we take 2 1 as V1 and V2 we can see that we can iterate from 3 to n and try each one as v3 because N is small enough.

    Now we see that the difference between 2 1 x and 2 1 (x + 1) is always the same which is (((n — 2) * 180) / (n — 2)).

    So just look up all possible v3 and choose the best one.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I could not get why the difference is always same. Is there any reason or is it just an observation ?

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

        Because of symmetry if the difference is not the same then this means that there are angles and/or sides that aren't equal which is not correct because the polygon is regular.

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

        Let's assume there are three vertices, v1,v2 v4. There is another vertex v3 in between v2 and v4. Now, it is not difficult to prove that angle(v2v1v3)=angle(v3v1v4) when the edge connecting (v2,v3) and (v3,v4) are equal. Just join v2 with v4 and v1 with v3. Since the edges (v2,v3) and (v3,v4) are equal, then tiangle (v2,v3,v4) is isosceles and therefore (v1,v3) will pass through the mid-point of (v2,v4). Hence, the difference is equal.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just realize the angle with Vj-1 Vi Vj+1 formula is equal to eachother, then i just do some stuff with some conditions.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It was bad idea to solve d before solving b. Hope my rating won't fall much.

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

Is div2C/div1A just a stupid case analysis, or is there an elegant solution?

  • »
    »
    17 months ago, # ^ |
    Rev. 7   Vote: I like it +4 Vote: I do not like it

    Actually stupid case analysis is necessary as far as I understood.

    You can divide cases with b >= a and a > b, and again, r-l+1 >= period and r-l+1 < period where period = 2*(b+a)

    Consider these cases a = 4, b = 2 : abcd,dd,abef,ff repeats in optimal answer, and a = 2, b = 2 : ab,bb,ac,cc repeats in optimal answer. In the first case, if the query interval is equal to or longer than the period, then answer is clearly 2*a-b, and in the latter case, it's a+1. If the length of query is shorter than the period, then we can just loop over the string which contains only one period.

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

      If there's nothing more than if/else in the solution, i think there are just too many cases.

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

        You can exploit period for large cases, and brute-force(manually construct short — whose length is around 50 — string) for smaller cases.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it by checking the length of the interval, and if the interval is small (say R-L <= 100) then I brute-force the solution with simulation, and if the interval is bigger, I just calculate the worst case and print that.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Case analysis and modulo?

    For instance when b < a, I was thinking maybe the first 2*a+b characters can be repeated. Knowing this we can iterate from min(L%n, R%n) to max(L%n, R%n) where n=2*a+b. But I don't know if this is correct. :(

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

      I did the same thing! Just be careful though, since there might be a case for example where n = 12, l = 9 and r = 14. You would be iterating from 2 -> 9, and this might give a WA.

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I get what you mean. You are right. I hope your solution was correct. I did not submit as I got the idea late in the contest.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No need for case analysis actually. I used bruteforce to compute first 12 * (a + b) characters (random constant) and then, if r - l was long enough — print number of different characters in string, otherwise modulo l with length of the pattern and count distinct characters in substring of right size.

»
17 months ago, # |
  Vote: I like it +62 Vote: I do not like it

How to solve Div. 1 A C D E? :)

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give idea of Div2B ?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check the angle between the diagonals starting from one verticle.

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

      Yes I did the same.Plz correct me .

      code
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        At calculating the angle, you do the cast wrongly. The program calculates ((180)/(n)) first, because of the parenthesis, and after casts this to double. But calculating ((180)/(n)) already floors the result to an integer, so casting it to double doesnt matter. Hence if e.g. n = 100, then angle should be 1.8 but it will be 1.0.

        To fix you simply have to delete the parenthesis, and write "(double)(180)/(n)".

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

          Thank You Bro! lost so much for small mistake!hope that i will not repeat it again.

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

    Because of symmetry, you can fix the first vertex of the angle, and itterate the other 2 vertices. To avoid O(N^2) complexity, you can only itterate the second vertex, and find the optimal third vertex using binary-search. All you need is a function that calculates the angle of 3 given vertices in a regular n-gon.

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

      Please can you once check the code above.Thank you

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think that we can even fix two adjacent vertices, because size of the angle can be calculated using number of arcs the angle takes.

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I talk about arcs that n-gon divides the circle into, if we inscribe the ngon in a cirle

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes. I just kept the first vertex at 1 and the second vertex at N. Then I just used some geometry to calculate vertex 3.

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

      Actually you can do it in O(1) with some geometry.

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

      Actually, you didn't even need to iterate the second vertex. All you needed was the third. If this doesn't hold true then RIP my rating :D

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, i iterated only the third vertex too

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Felt awesome when I realized in the middle of the contest that I didn't need to iterate for all possible triples of vertices and just needed to iterate for the 3rd vertex. One thing that might be worth noting for those who are currently still trying to solve it however is that the measure of an interior angle of a regular polygon may not be an integer, so if they still don't pass the test cases, chances are they just need to use a float/double.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A O(n) solution also exists.You can fix the first and second (for example:1 and 2) and then iterate for the third.If we binary search on it the complexity will be O(logn) but it's not necessary here. My solution : 28086134

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 D?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can calculate dev[i] = deviation of permutation with i cyclic shifts. You can calculate it fast with prefix sums.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate little bit more?

      • »
        »
        »
        »
        17 months ago, # ^ |
        Rev. 4   Vote: I like it +10 Vote: I do not like it

        Let's say p[i] >= i
        In first p[i] — i cyclic shifts p[i] — i will be not negative.
        And if p[i] < n next n — p[i] cyclic shifts p[i] — i will be negative.
        And the remaining cyclic shifts p[i] — i not be negative again.
        You can add arithmetic sequence in range with prefix sums.
        You need to do the same think for p[i] < i. Hope it is correct.

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for this nice approach!

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Your approach is elegant :) Thanks!!

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I had similar idea when I was trying to solve it. But my problem is: how can you do range update when you do not add same number? You need to add in range [x,y] lets say. But yu need to update p[x] with p[i] — k, p[x+1] with p[i] — k — 1... So you dont update with unique number. How do u handle that?

          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think I got it. Range update with arithmetic series as said above.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I will be pleased if you explain how to use prefix sums to calculate dev[i]

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell my I was failing on pretest 6? My code — https://pastebin.com/R09b5YRN

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem is Div2B

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same Problem Bro!waiting to see the solution

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        After discussion with a friend, I guess I have done mistake in taking n as integer. Not sure about yours though.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are taking values as int probably. Make them as double or float and you will pass it.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div 2D?

  • »
    »
    17 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I tried but failed. Maybe try to use prefix sums? Here's my code:

    Solution
  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Given a[], foreach a[i] — i > 0 push (a[i] — i + t) where t is the current time into a heap, for each iteration, update the value that has been newly pushed to the front, plus one for each element which is not in the heap, minus one for each elemnet which is not in the heap, pop elements from the heap if time = a[i] — i + t, as now a[i] — i should be >= 0.

    Edit: It appears that O(nlogn) is not good enough, to achieve O(n), use prefix sum as others mention to store the updates instead of using a heap. The idea remains simular.

»
17 months ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve Div2 C?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I greedily generated string upto 2*(a+b) length such that Mr. B always choose the last character from the generated string so far. Ex — If the string so far is "abcde" then Mr. B will form string "eeee..." and merge it to the original string i.e "abcdeeee...". After generating the string I mapped the value of 'l' to smaller string by taking mod with (a+b). http://codeforces.com/contest/820/submission/28096854

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

      I followed the same approach. But how did you assign the value to l. Why in particular mod with (a+b) and not the length of string. The optimal string have a length of 2(a+b) right?

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can observe that in any case after 2*(a+b) length, the string will get repeated i.e s=s+s. Also there is Symmetry in string from length (1 to a+b) and (a+b+1 to 2*a+2*b). You can also take mod with 2*(a+b) but then you have to increase the length of string to 4*(a+b).

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How does the string have symmetry. As I understand, the length 2*(a+b) forms the period. Eg: a=2,b=2 Then string would be abbbaccc|abbbaccc|... (so on)

          Sorry, correct me if I am wrong but can you explain in more detail, probably with an example.

          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            What I actually meant was abbb and accc are not exactly same but they are similar. This similarity can be used and that's why I used (a+b) to take mod. But you can also use 2*(a+b) to take mod.

            • »
              »
              »
              »
              »
              »
              »
              17 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks for your help, I got it. I did a very lame mistake of not considering the fact that r can be less than l after taking mod. -_-

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

  • »
    »
    17 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I didn't solve the problem at contest time, but I think that the first thing to do here is to split the problem in two cases:

    if r — l + 1 >= 2 * (a + b)

    in this case the person A is going to put a different letters for sure, since there is at least a segment of a letters in which person A is going to put his different letters. Since person B should play optimally then he's going to put the same letter and it should be one of the letters from the first A segment. but since there are 2 segments for A, then A cannot put the same letters as in the first segment since B already put one letter and A look for a suffix of at least 1.

    So, in this case the solution is a + 1

    else

    simulation, starting from l to r starting with the letters from A or B depending on l % (a+b)

»
17 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve div2C ??

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How tp solve Div2 C and D ?

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I must be the only one solving Div2 Problem B by constructing a regular n convex polygon, and using binary search to find the answer :P Totally forget things about circles

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did BS then I realized it's 10^5

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can construct the polygon in O(n) and use binary search to check every vertice, so the overall complexity is O(n + nlogn)

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, but all those angles then you do binary search are the same...

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same :D

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is Div2C just about implementation?

»
17 months ago, # |
Rev. 2   Vote: I like it +550 Vote: I do not like it

Problem A is a pile of bullshit.

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

    Why? I thought that it was interesting.

  • »
    »
    17 months ago, # ^ |
    Rev. 3   Vote: I like it +83 Vote: I do not like it

    I don't know whether it's good or not, but I am sure that people won't like that task ))

    UPD : It is also very bad lolololol

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

    *the whole contest

  • »
    »
    17 months ago, # ^ |
    Rev. 4   Vote: I like it +30 Vote: I do not like it

    Solution for A:

    1. Prove that the best strategy the human player may use is repeating the last character in the string b times.
    2. Show the string generated by this strategy is periodic with period 2·(a + b) ≤ 48 (or strongly believe it holds so hoping you are right). Generate the first 48 characters by means of brute force.
    3. If r - l + 1 > 2·(a + b) then lower r so that brute forcing [l, r] becomes manageable.
    4. Freak out and increase 2 to 6 and 48 to a + 400·(a + b) just to make sure.
    5. Profit ...

    Edit: It fails like most passing solutions, unfortunately. Details below.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why 96? I think 48 is good.

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not always, take a = 5 and small b.

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

          I used the exact same approach to solve this problem but with string period = 2*(a+b) for any value of a nd b (off course a and b within the given constraints).

          Although repeating last character of string during Mister B's turn seems to be a wrong idea (proved by LLI_E_P_JI_O_K in comments below).

          Let us assume a=5 and b=1, then

          initial s=> "abcde"

          after first turn s=> "abcdee"

          after second turn s=> "abcdeeafghi"

          after third turn s=> "abcdeeafghii"

          after 4th turn s=> "abcdeeafghii" + "abcde"(same as intial string).

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

            Your reasoning is perfectly fine, It seems I miscounted when I wrote the post (post updated).

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

      But is that true? What about the test case from below?

      3 1 4 10
      

      Your solution would give:

      "abc" + "c" + "ade" + "e" + "abc"
      unique("cadeeab") = 5
      

      But the real answer is:

      "abc" + "b" + "ade" + "d" + "abc"
      unique("badedab") = 4
      
      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Of course, it fails, like most passing solutions, unfortunately. There's an interesting psychological factor regarding this problem. A lot of yellows and reds would just find something intuitive enough to be correct and (maybe) try "false-proving" it. Then, there are also a handful of targets who could not find something provable / ruled the expected approach out by finding counterexamples. What's clear for sure is that it goes well beyond Div1 A, if it's solvable at all.

»
17 months ago, # |
  Vote: I like it -15 Vote: I do not like it

pretty good problems Dying to see the editorial for Mister B and PR Shifts :'(

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

IMO, problem D (div 2) was pretty cool. Shifting the sequence is equivalent to subtracting/adding one from each element in the answer. There's actually an easy way to do this.

Code

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain your solution a little more.

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

      Assume we are shifting to the left instead of the right (that's how I did it in my code, you can easily switch between the two).

      An important observation is that, when moving from one cyclic shift to the next, you have to consider for each i from 1 to n, if p[i] < i. If p[i] < i, then it will contribute -1 to the answer for next cyclic shift. Otherwise, it will contribute 1. This is because every i will decrease.

      Now, we just need to find where p[i] becomes >= i using multiset/priority_queue, and handle the case where the frontmost element gets shifted to the back.

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

        Instead of multiset/priority_queue, you can use an array and add +1 at index k (=when), resulting in O(n) instead of O(n log n). (Apart from that my solution is more messy than yours.)

        Code: 28096290, variable "change"

»
17 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Div2C Maybe I didnt understand statements, but why in samples computer moves first?

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

    Third paragraph:

    "Initially the players have a string s consisting of the first a English letters in alphabetical order (for example, if a = 5, then s equals to "abcde")."

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

That moment when you know your solution won't pass system test.

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

Too mach math problem and I don't like it. I only solve the div2 A D. I even forget The Law of Cosines to solve problem B

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need Law of Cosines to solve B.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What .. So how to solve B

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

        You need to know, that the angle between diagonals starting from one verticle is equal. E. g. in a hexagon the angle is 120°, and 3 diagonals go out from one verticle, breaking the angle to 4*30°.

»
17 months ago, # |
  Vote: I like it +341 Vote: I do not like it

I know solutions to BCDE but not A. I kinda think swapping A and E makes a better round.

  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it -75 Vote: I do not like it

    The constraints are small enough that you can just simulate reading every page. No need for some fancy solution :)

    EDIT: I forgot that div1 exists, my mistake... :)

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

      He is div1 not div2. He talks about your C problem.

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

      I think he meant for div 1

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

      I highly doubt he has bothered to even read Div2-A. He is talking about Div1-A, or Div2-C.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You just have to check cases. If the gap between l and r is too big, then the answer can be calculated just from a and b, if the gap is small enough, then you can generate the string, and simply check.

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

      Seems that you also failed system test...

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes I did :(

        But the approach is correct, just there is a bug in my code. (I guess, I haven't found it)

        • »
          »
          »
          »
          »
          17 months ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it

          Yes, the approach is correct.

          I've just got accepted now, and I can't believe that the only bug that made me FST on A (on test 71) is that, I used 1~26 to represent a~z, but I checked if 0~26 appear in the suffix when adding letters by Mister B's opponent...

          UPD: it turned out that the author's solution was wrong... so we can only say that the approach is correct if the author's solution was correct...

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

    I agree. E is the easiest, I think.

»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I couldn't make it till the end of contest but here's my implementation of E, finds solution for all possible cases and I checked the answers so I think it works.

http://ideone.com/zzLnUp

You can understand the solution from the code.

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

What's the intended complexity for Div 1 C? Is something like per test supposed to pass where ω(n) is the number of distinct prime factors of n and is the number of divisors of n?

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

    By OEIS (see Highly Composite Numbers) we have σ(n) ≈ 105 in worst case so with T ≤ 1000 this should work. (I also have this complexity)

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thought div1 B can be solved in , wrote a bug, fixed and submitted at 01:59:33, and found Time limit exceeded on pretest 10 :(

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

    People that write difficult algorithms in easy problems and don`t get OK have always surprised me.

»
17 months ago, # |
  Vote: I like it -37 Vote: I do not like it

thank you adedalic for your efforts to make this round. but let's face it : your problems sucks ... it's even worse than robinyu problems in round 419.

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

    Codeforces 101: Always use a smurf account when you feel like picking up a fight .... Whoops I am not doing this correctly, gotta run.

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

    you are just being really toxic...

»
17 months ago, # |
  Vote: I like it +14 Vote: I do not like it

This is why you never forget int/int doesn't magically turn into double.

Thanks, C++.

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

That moment that div1 E solution looks simpler than div1 A lol.

»
17 months ago, # |
  Vote: I like it +10 Vote: I do not like it

That moment when you get popups for announcements 35 minutes after contest end xD

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

that moment when you spend the whole contest on problem B div1 then you realize that O(n log (n)) won't pass system testing !!

»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I think this contest was more math contest, than programming contest.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    and it was the bad kind of math contests

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Stupid question, Can Div.2 D be solved with ternary search???

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also thought about this one but it would not work anyway

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

    determine in which id p[i] > i

    this makes 3 segments at most for each i

    then add the abs(p[i] — i) using above and some array 28099494

»
17 months ago, # |
  Vote: I like it +15 Vote: I do not like it

wrote O(NlogN) solution with std::multiset for Div2D 28098060
time limit exceeded on pretest 7
started coding discretization + Fenwick tree
contest was over
waitted for system testing
submitted and accepted 28098915

»
17 months ago, # |
  Vote: I like it +93 Vote: I do not like it

 1:59:59 stupid long double :3

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it is unrated :(

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also did the same ......just changed the variables to double and then got AC -_-

»
17 months ago, # |
  Vote: I like it -13 Vote: I do not like it

The worst problem for C div.2 :|

»
17 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain the answer of testcase #24 of Div2 C? Input: 6 1 654321100 654321115 Answer Given: 11

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

    It should be 7. String can be abcdefgabcdefgabcdefgabdefg...

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this is wrong. initial string => "abcdef" Now let us assume Mister B appends character 'g' to it (although it is not optimal case)

      after first turn string => "abcdefg"

      now computer(other player) cannot append any of the last 6(according to your test) characters of the current string.

      So after second turn string => "abcdefgahijkl"

      and so on

      Your answer is wrong :(

»
17 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Sorry, adedalic, but problems were awful (IMHO).

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for this contest adedalic, i enjoyed solving problem B even that i do not like geometry problem but this one was worth thinking on it and really good problem.

Also i enjoyed trying problem D even that i had overflow that i didn't pay attention to and still stuck in pretest 7.

thank you again and waiting for editorials.

»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Misread Div1A statements. Passed pretests.

This is strange. Of course, I should've read the statements more carefully, but there were at least 15 pretests, so I've expected them to be strong enough. But all of them can be thrown in the trash bin.

»
17 months ago, # |
Rev. 2   Vote: I like it +352 Vote: I do not like it

Hello!

Can anybody tell me, why for Div2 C problem for test 64 answer is 5? I suppose I have better answer — 4.

Test 64: 3 1 4 10

My string for answer 4: (divided by players moves) abc b ade d ab

Segment [4,10] contains only 4 different letters — a,b,e,d. Am I wrong?

Thanks a lot for possible explanation of this issue :)

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

    If the first four letters are

    abc b

    Then the next set will be

    acd

    So the string will then be

    abc b acd

    which invalidates your idea.

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

      It can't be "abc b acd" — because "acd" contains letter "c" which is in suffix "bcb" already

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

        You're right, I read the computer as taking suffix of length b, not of length a.

        Then it looks correct to me. I'm not sure what's wrong here.

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

          Are you going to retest the problem? :) And what about rating questions then?

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

            Maybe you should write a private message to adedalic and tell him about this case.

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

              Yes, I've already done it, but he, Kan and Mike haven't answered yet

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

      The computer will look at the string "bcb" of length a = 3, so he will append the string "ade". LLI_E_P_JI_O_K's answer is OK!

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

    So, as you can understand I got WA test 64 on this problem :(

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      abc b acd d abc ?

      [4;10] there are 4 different letters

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

        Yes, and answer should be 4 instead of "5" — jury answer.

        Please, correct test 64, run total retest on this task.

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

          same here! my program got answer 4 with abc b ade d ab ... too and i think my answer is correct!

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

        As I mentioned above, the computer will append "ade" on its first turn.

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

        well wrong testcase answer.. but still nice problems..:)

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

    This round had not 1 or 2, but 4(FOUR) testers. And none of them implemented bruteforce solution for A? I've always thought this is exactly testers' purpose.

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

      I have implemented brute force during the contest, where the number of segments A or B is less than 3, for other cases got an answer by formula, as you can see, there are some bugs in tests :))

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

      As I thought, it's setters task on codeforces to code naive solutions, and I'm always doing it when setting an own round. As I've understood, testers should just solve the tasks and estimate the difficulty of the tasks...

      By the way I hadnt solved this task myself...

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

    dotorya : Now I don't know how to solve A

    So....

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ops, my rating stays same :D

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

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

    I got 1st place in Div2 and CF-predictor tells me that i'll have +310..

    but I think this round should be unrated :P

    ( I just implemented C without any formal proof, and I knew some cases like this will happen...)

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

    We're looking into the issue.

    • »
      »
      »
      17 months ago, # ^ |
      Rev. 3   Vote: I like it +27 Vote: I do not like it

      Beware, if you look too long into the issue, the issue will start to look into the you.

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

        I have to use this sometimes.

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

    There are fewer than 10 people in div1 having WA on test 64 (and they're mostly purple). If pretests hold, and there isn't any hack using such test case (why would there be, when the answer is wrong?), this might be the least solved div1A ever!

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, of course, I suppose Div2C too :)

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

        Which kind of makes me understand why the testers did not spot the flaw. Because almost everyone fell for the same trap in the real contest.

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

          Yes, but they should do some kind of slow but correct solutions to test small testcases and finding bugs in really fast and intended solutions:) But they didn't do that for this problem, I guess :)

          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I can imagine that it seemed like an obvious solution (it didn't to me though), and they might even have some proof with a tiny flaw somewhere.

            It happens. I wish the author(s) to shake it off. They are way more invested in this round than we are. And it's not like someone tried to pull a notorious coincidence on us.

          • »
            »
            »
            »
            »
            »
            17 months ago, # ^ |
            Rev. 2   Vote: I like it +71 Vote: I do not like it

            Well, we do have bruteforce solution, it produces correct answer on your testcase. We also run a stress test with it several times, it didn't find any tests against the author's solution :( And this test was a hack.

            Right now we're looking if there is a solution to the problem or not.

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

              Ok, thanks. If it is needed I can explain my solution of how to solve div2C/div1A

              • »
                »
                »
                »
                »
                »
                »
                »
                17 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Ok, please explain if you think it's correct.

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

                  Ok, I'm going to explain. It will take some time, about 10-15 minutes.

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

                  I write from mobile, sorry, if something looks badly. Let's call string of second player move — "B-string", string of first player move — "A-string". First of all I have found how many times A-strings and B-strings appeared in the given segment L...R, with some simple math tricks and partial sum principle like F(R)-F(L-1). Then if B >= A, then every time on A player move total suffix will be inside B string, it's obvious that here we should make B-string with one repeated letter and if the test is quite big (I.e. we have >= 3 full A-strings) the answer will be always (1+a). When B < A, and count of full A-strings is >= 3, every such full string will give |A — B| new letters comparing with last A-string, but such A-strings can be repeated in chess-order, like. A1, B, A2, B, A1, B,... and B should consist of one letter from A1, then one letter from A2, then from A1,... Like in 64th test, but here we have less full A-strings, than 3. In such big cases (>=3 A-strings) answer will be minimal and equal to 2*A-B. Small cases I solved with bruteforce, small — when count of full A-strings is 2 or less, here the total length of segment is short and we can use bruteforce for B-string letters.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Tests with small count of covered A and B segments are quite tricky to implement through formulas, that's why I have preferred to write brueforce instead :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  =========================================

                  For big lengths seems correct to me (for b >  = a the answer is at least a + 1, and the construction provides such a strategy. for b < a the answer is at least 2a - b, and again the construction seems correct).

                  However, for small lengths, it's not obvious that we should use only one letter, and that the answer depends only on the moves we make close the the segment [l, r].

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, but all letters from A are still different, that's why if we take such small segment, but L and R is too big, it doesn't matter what previous A strings were if we take B string consisted of one repeate letter, the same count of different used letters for pair ("previous A ans", "previous B ans") still be provided before the next A string. So, if we use strategy with all B answers consisting of repeating letters (possibly different) — nothing changes for us, we can look only on our segment. Isn't it?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                  Rev. 3   Vote: I like it 0 Vote: I do not like it

                  And is that any idea of using B answers of different mixed letters? It seems not to be better or useful just because they will prohibit more letters from the next A string. Seems to be a proof somehow.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it -28 Vote: I do not like it

                  Quality of the problems is not good enough, one problem still without a correct solution, it has been about four hours since the contest is over, do we need more reasons to make the round unrated???

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

                  Problems were fine,I liked Div2 D and Div2 B,both of them could be solved in couple lines of code,very nice problems.If problem div1 A hasn't got solution it will definitely be unrated.Main problem is that 2 consecutive unrated rounds will make joke out of codeforces.

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

              And what about the round's 421 destiny, this decision will be rather difficult, in every case, I suppose, some contestants will be slightly frustrated.

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

                I would be furios.I made a bet with my friend from school that I will be div 1 on 1.st September and I really practised a lot.Last 2 contests I got over +170 in sum and if both of them end unrated,I will just give him 20 euros and stick with atcoder rounds.

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

                  Ummmmm, but you didn't even submit Problem C...

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I tried to solve it and had something but couldn't prove it.The point is that I would have over 1600 rating if last 2 round were rated.I won't leave codeforces ,will do problemset because it helps to improve but I won't do rounds anymore.

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

                  That is unfortunate, but you have the right mindset in your last sentence. The goal is to improve. Your rating will follow. I would've just made div1 if last contest were rated, but it doesn't bother me that much. What I do care about is whether or not I'm improving and it looks like we both are. Keep practicing and you'll make it. You have plenty of time. Best of luck to you!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  17 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks man,best luck to you too!

            • »
              »
              »
              »
              »
              »
              »
              17 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              After all that's happened, I'm curious:

              How many hack cases are added to the main tests? How is it decided which ones will be added?

              I'm guessing there must be an upper limit and an algorithm which picks random hack cases, but I couldn't find any blog which mentioned so

              • »
                »
                »
                »
                »
                »
                »
                »
                17 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Usually the number of hacks is not so big, so we add all of them. Even if there are 100 hacks on some problem, probably most of them are equal, and only distinct tests are added.

            • »
              »
              »
              »
              »
              »
              »
              17 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Here is my submission, can you check it? http://codeforces.com/contest/819/submission/28109245

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

    I think it's so simple it's like how I solved the problem: abc d abc d abc d abc ans = 4

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And you are not right,because the second string ABC can't contain letters B and C, they are in suffix Bcd

  • »
    »
    17 months ago, # ^