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

Автор adedalic, 7 лет назад, перевод, По-русски

Привет, Codeforces!

Рад пригласить вас на Codeforces Round #421, который состоится 27 Июня, 2017 в 17:35 MSK.

Да, это мой первый раунд, и да, очередной раунд от фиолетового.

Хочу поблагодарить KAN за огромную помощь в подготовке, danilka.pro за помощь на начальных стадиях и тестирование, Belonogov, WHITE2302, hloya_ygrt, Perforator за тестирование задач, а также MikeMirzayanov за Codeforces и Polygon.

Как обычно, участникам обоих дивизионов предлагается 5 задач и 2 часа на их решение. Разбалловка будет объявлена ближе к раунду.

Good Luck and Have Fun!

UPD1: Разбалловка стандартная для обоих дивизионов: 500-1000-1500-2000-2500

Мы работаем над проблемой в задаче A первого дивизиона. Мы опубликуем решение позже.

Из-за проблемы с задачей A, к сожалению, раунд нерейтинговый. Подробнее.

Несмотря на все проблемы Рабор должен быть, поэтому он здесь.

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

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

offtop

Когда результаты отбора на Сазанку?

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

Is it rated?

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

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

Thank you so much :)

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

Hope for short statements like the blog <3

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

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

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

Hope for short statements like the blog <3 *3

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

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

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

anime?

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

Everyone still wonders: Is it rated?

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

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

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

Round 420 is also "rated"...

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

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

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

**The Rain Of Downvotes :P **

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

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

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

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

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

    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.

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

Hope for better performance of the server..

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

»
7 лет назад, # |
  Проголосовать: нравится +133 Проголосовать: не нравится
  1. Take a lot of screenshoots just in case.
  2. Take part in the round.
»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +9 Проголосовать: не нравится

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.

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

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

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

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

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

Make a wish for Akagi with 200 rating.

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

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

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

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

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

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?

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

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

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

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

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

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?

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

    I think brute-force + math is enough!

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

    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

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

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

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

    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.

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

    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.

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

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

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

    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)

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

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

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

    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.

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

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

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

        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.

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

        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.

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

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

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

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

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

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

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

    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.

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

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

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

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

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

    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.

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

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

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

      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.

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

    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.

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

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

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

Can someone give idea of Div2B ?

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

    Check the angle between the diagonals starting from one verticle.

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

      Yes I did the same.Plz correct me .

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

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

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

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

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

    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.

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

      Please can you once check the code above.Thank you

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

      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.

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

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

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

        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.

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

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

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

      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

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

How to solve Div2 D?

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

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

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

      Can you elaborate little bit more?

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

        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.

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

          Thanks for this nice approach!

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

          Your approach is elegant :) Thanks!!

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

          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?

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

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

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

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

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

How to solve Div 2D?

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

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

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

    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.

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

How to solve Div2 C?

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

    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.net/contest/820/submission/28096854

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

      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?

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

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

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

          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.

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

            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.

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

      Thanks!

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

    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)

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

How to solve div2C ??

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

How tp solve Div2 C and D ?

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

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

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

is Div2C just about implementation?

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

Problem A is a pile of bullshit.

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

    Why? I thought that it was interesting.

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

    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

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

    *the whole contest

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

    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.

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

      why 96? I think 48 is good.

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

        Not always, take a = 5 and small b.

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

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

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

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

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

      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
      
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        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.

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

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

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

    Could you explain your solution a little more.

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

      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.

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

        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"

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

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

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

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

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

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

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

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

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

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

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

      What .. So how to solve B

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

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

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

Нормально ли, что решение в Div1 B за NlogN получает TL? даже рукописный декарт не помог.

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

    Кажется, оно предполагалось за O(N), судя по ограничениям)

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

      Так и есть. И там довольно просто, без каких-либо алгоритмов.

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

      NlogN = 1e6 * 20 = 2e7 должно заходить учитывая что TL 2 секунды

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

    Вы знаете слишком много алгоритмов, это вам вредит

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

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

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

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

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

    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.

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

      Seems that you also failed system test...

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

        Yes I did :(

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

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

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

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

    I agree. E is the easiest, I think.

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

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.

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

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?

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

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

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

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.

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

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

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

    you are just being really toxic...

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

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

Thanks, C++.

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

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

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

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

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

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

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

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

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

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

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

 1:59:59 stupid long double :3

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

The worst problem for C div.2 :|

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

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

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

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

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

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

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

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

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

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.

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

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.

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

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

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

    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.

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

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

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

        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.

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

      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!

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

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

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

    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.

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

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

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

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

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

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

    So....

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

    Ops, my rating stays same :D

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

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

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

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

    We're looking into the issue.

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

    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!

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

      Yes, of course, I suppose Div2C too :)

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

        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.

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

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

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

            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.

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

            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.

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

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

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

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

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

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

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

                  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.

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

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

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

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

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

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

                  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?

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

                  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.

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

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

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

                  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.

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

              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.

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

                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.

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

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

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

                  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.

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

                  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!

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

                  Thanks man,best luck to you too!

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

              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

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

                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.

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

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

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

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

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

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

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

    Wow, the test is made by me...

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

I think problems were fine ! Just estimation of level is very bad + bad pretests for A div 1 :)

Anyway I am stupid guy and I should stop with competitions.

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

Hi guys! Something bad happens to cf-predictor, it's falling over and over again. It's not clear what is the reason. You could download prediction here. Mirror will be available soon.

UPD

I can see rating prediction on standings page, hope you too:) Website currently deployed on AWS

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

Why do people put geometry in their problems, i mean it's clear math, informatics it's about implimentation and other informatics' topics. Already 2 contests in a row there is geometry, that's shit.

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

I think the contest problem that it had depended overly on Maths and Geometry

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

adedalic Does the dataset of C has some kind of problem? My AC code performs the following: input: 4 2 11 21 output: 6

but it can be 5. The string could be like this: abcdddabefeeabcdddabef........

from 11 to 21 we can have only 5 distinct letters.

Please see to this if I have misunderstood something......

(I skipped my first code because I found this test case and submitted a new one... now I see my skipped code gets AC. This is the greatest irony)

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

    Something is wrong with Div2C = Div1A systests.

    In this comment there is information about a wrong test in the testset.

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

      could you please see the testcase I have given? I had a hectic day and I may be wrong :v please let me know :v I need to know i haven't lost my mind totally

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

        Seems correct:

        Input: 4 2 11 21

        s = "abcd" + "dd" + "abef" + "ee" + "abcd" + "dd" + "abef"
        s[10:21] = "eeabcdddabe"
        

        And s[10:21] has only 5 distinct letters: a, b, c, d and e.

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

      See here, my solution has better ans than judge. Getting WA on this case. :(

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

        Is it a wrong answer in the pretests? If so, the round must be unrated. Do you have a string which can be generated by the players and the answer for which is 12?

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

          It should be rated if pretests were ok.

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

            It should be unrated if there is no correct solution to that problem.

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

              But I think someone have got the correct solution of this problem.

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

                Not necessarily. We know that some solutions can generate a better answer. It's not known if these solutions are correct. There might be other test cases where the answer is even better than the one produced by these solutions.

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

            Why this should be rated if pretests were ok ?? Someone may pass pretest and get stuck because judge data is wrong. @gabrielsimoes

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

              Well, because even though system tests are wrong, system tests are not available until after the contest and shouldn't be taken into account.

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

              You can use wrong solution to pass some of the codeforces probem's pretests, but it can be hacked or FST.

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

              If pretests were ok and there is a correct solution to the problem, the can remake the data and rejudge the problem.

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

                Ok, maybe, but I don't think it will be normal, if problem Div 1 A will be solved by 10 people, as all passed solutions are incorrect.

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

          Here is the string for test 12.

          12 1 100000011 100000024
          12
          abcdefghijkllabcdefghijkmmabcdefghijkllabcdefghijkmmabcdefghijkllabcdefghijkmm
          
          
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Seems like this string is incorrect: on the computer's first turn it will look at last a = 12 symbols ("bcdefghijkll") and append the string "amnopqrstuvw".

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

        You solution produces an invalid answer. The piece of string [l - len, l + len * 3) looks like this: "ghijkmmabcdefghijkllabcdefghijkmm". That's not a valid string. b can't be there as it's exactly the twelve-th character to the left from its second occurrence.

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

Rating Predictor ....?

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

in Div2 B test 6 the input was 100000 1 my answer was 1 2 181 the jury's answer was 2 1 558 can anyone explain to me why the jury's answer was better ?

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

It's not rated???

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

.

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

for div2E or div1C am I correct to say that the the following block will give answer:

for(int i = 1;i<=m;i++) if((2*s) % (gcd(i, n)) == 0) res++;
for(int i = 1;i<=n;i++) if((2*s) % i == 0) res++;

Not saying it will be fast enough just want to know if this is equivalent to the problem

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

For Div2B,I see solutions that fix the first 2 vertices and iterate for the third vertex assuming the angles thus formed are a multiple of (180/n). Can anyone provide with the proof for this? I tried working out the values but I found that they were not always equal(I may be wrong :P).

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

Downvote a contest first time. Now i feel sorry to my friend, who i invited to participate the contest. Obviously,the awful problems wasted his time. Not only div1a.

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

Do it unrated. :c

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

It seems the organization is still causing troubles in this time line.

There can't be two consecutive cf rounds unrated. send_nodes, lets send another D-mail.

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

That moment when you and send_nodes are in the same room. xD

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

    I was there too. I tried to hack him, for the previous round where I didn't get +116 rating. :D

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

When you try so hard to improve your rating, but the round ends up unrated.

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

Somebody clarify rated or not?Its been 3 hours!!!

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

    We are working on the issue with problem A in div. 1. We will announce the decision later. - ( The update in the blog )

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

They should give that hacker kudos for hacking the entire contest xD instant 1st place or something lul

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

Can anyone help me find out what I'm doing wrong for Div2D? I don't know how to get past pretest 9. Code

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

just push it!

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

Interestingly, Div2 B is educational and enjoyable. There are 2 solutions that come to my mind (assuming one of the outer points of the angle is fixed as vertex 1):

  1. Iterate the middle vertex of the angle. Then, either binary search or use a two pointer approach to find the third vertex.

  2. Remember your geometry theorems: The locus of middle points for the angle given the outer points are fixed is a circle (the circumcircle of the polygon). This way, there are only O(N) candidates for the last point of the angle and there is even a way to solve the whole problem in constant time by some formulas.

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

    In this particular problem, I have a doubt- Why solutions are always such that two vertices are adjacent ? I mean in a 20-gon polygon why cant there be an answer like 4 7 15 for a specific value of angle a.

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

      There are multiple solutions, but you can print any of them. Finding x so that the answer is "2 1 x" is the most practical approach.

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

      it is not necessary as for a n=6 and angle=150 one of the possible answers is 1 3 5

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

        Okay..But how is it possible that everytime this two adjacent vertex approach is validated ? Any proofs for that ?

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

          This is how this work. Suppose your solution is angle 10,20,30. But, angle 11,20,31 is also a solution (because angle 10,20,30 is same as 11,20,31 -> you just "shifted" angle. Why? You can draw a circle around polygon. Then, every peripheral angle over same chord is equal). By same logic, angle 12,20,32 is same. If you go on like that, angle 19,20,39 is same as 10,20,30. So, whatever angle is your solution, you can shift it to angle that has two adjacent vertices. Also, its logical because everything is simmetric.

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

    I'm not strong in math, so I coded a stupid solution with problems about precision, but it passed! http://ideone.com/LxRrwC

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

Two unrated rounds in a row.

I feel sad for those who got hundreds of down-votes because they asked if the round was rated or not :v

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

This contest was definitely unlike any other. The questions involved much more math than normal. In Division 2, the best way to solve Problem B was by drawing out a diagram. It could be realized that since a circle could be inscribed around the regular polygon, and due to the inscribed angle theorem we could just pick two points right next to each other for one side and test out the remaining possible points for the third point. That allows for an O(n) complexity and much easier implementation. Also, Problem D in Division 2 (also Problem B in Division 1) was surprisingly easy! If you haven't already, you should definitely check it out! Just watch out for time complexities!

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

Can you atleast give a rough idea of when the decision will be announced? I've been checking this page for around 3-4 hours now. :(

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

    I believe that once a solution to div1 A/div2 C is verified, they will just rejudge submissions and provide new standings based on which, the rating will change.

    You can speed it up by creating a formal proof of the solution to the above problem.

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

      I think that would be best for now to rejudge in case of such an ambiguity....two consecutive unrated contest is not fine for legendary Codeforces

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

Upvotes for contest came down from around 250 to 50. If they don't announce their decision for some more time, it can come down to 0.

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

This thread has more than 300 upvotes couple hours ago.. Now it's only 50-ish and falling..

Edit: it's negative now. Feel sorry for him. Hope this problem is solved soon before it gets worse

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

Div2C/Div1A

I am getting wa for below test case. My answer is 4 and jury's answer is 5. However I am able to get a string which gives 4 as answer. What am I missing?

Test Case: 3 1 4 10

sample string with answer 4: a b c b a d e e a b

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

Now this blog has negative votes...

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

Is it rated?

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

I'm sorry to say that the round is unrated now. Here are some details.

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

If the rating of this competition was a stock, then we would all be broke.

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

I would like to change my vote for this topic, however cf does not let me do this. Is that option blocked on purpose? I think that I should be able to remove my vote or change it any time.

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

I can't understand why all those downvotes there is always a possiblity for such a situation and the testers & the problem setter described that they did their best. I think we can understand the situation more wisely ..

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

    I gave upvote and will always do so,people need to consider how much time authors putted on testing and making problems,mistakes can happen.On the other hand you must consider amount of unlucky people who performed for over +150 rating in previos two rounds and ended up at same rating.it's so frustrating,I can't go over 1480 and with these 2 contests I would be over 1600.Anyway after all this happened suddenly I don't care a bit about rating and won't participate in CF rounds for some time.

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

I'm really disappointed about the blog post rating is negative.
Several hour ago, the post rating was 300-400, but now it is -50.

I think some people was disappointed about unrated. Me too. But the contest writer worked very much for codeforces and people, and you may enjoyed the other problems.

So I think this post should be positive, at least 0 because you may enjoyed at least a little, and the writer worked very much. Don't blame the writer too much.

UPD: I see the blog again after 9 hours writing the comment, and the post rating was -18. Thank you for the incident didn't got worse, but the post rating is still negative. I say again: don't blame the writer too much.

UPD2: the post rating became to positive! I'm very happy. (The writer and most people may be happy too.) Thank you!!!

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

    Man, it is just a rating, it is not like we are beating him up or something.

    I belive this is a sign to stop the poor proof contest and the over confidence that the algorithm is correct because the problem looks simple.

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

      I saw many comment of feedback of Codeforces Round #421, and I posted my opinion:

      I think this post should be positive, at least 0 because you may enjoyed at least a little, and the writer worked very much. Don't blame the writer too much. I say again: don't blame the writer too much. (written by E869120)

      Yes I agree, writer prepared very much. And I think the other problems except Div2C/Div1A is good. Though I have came across similar issue in Codeforces Round #382, that is, there was an issue in Div1A/Div2C, and this is the similar pattern.
      I belive this is a sign to stop the poor proof contest and the over confidence that the algorithm is correct because the problem looks simple. (written by rick_sanchez_c-137)

      I agree that I think writer/tester should make a correct solution with correct proof, but I think Codeforces has too much rounds like 2-3 days per a contest. It is very very short period compared to Topcoder or Atcoder. I want to ask whether Mike or Kalinin can do really good testing and checking proof and checking the editorials. Though, we will be very happy if there's a contest per 2-3 days and also no issue with very high probability.

      UPD: The contest announcement blog is now positive like +20. I also read E869120's comment below. I think many people don't have experiences of problem writing in a large-scale or international competition, and some of them may thinking that it is not very difficult. (Arpa's blog describes how Codeforces problemsetting is doing like.)
  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -7 Проголосовать: не нравится

    Thanks very much for upvoting the announcement blog.
    Finally, the topic rating became to positive (Now it's +18!). I'm very happy.

    I think any real announcement of CF should be positive, whether the contest was rated (or unrated), whether the contest delayed, whether the contest has some issues, whether your score or rank in the contest, and whether there is some notorious coincidences in the contest.

    Please consider about the work of writer. It may took so long time, and writers/testers have many difficult tasks. I already hosted 4 contest which is unofficial, and 1 contest which is official, all of these in AtCoder, but in one contest example, it spent all of 2 weeks to prepare contest.

    I hope there is no real announcement post of CF contest which has negative rating.

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

The test (Div1 A Test 64) is made by me.

Because of my test the contest is unrated, today is so cool for me XDDDDDDDD

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

Last two contests,

Rated contest

Solve and hack

Sorry, it is unrated

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

First time I get rank < 50, contest is unrated :(

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

Lol, this guy didn't even bother to hide his second account. What an outstanding perfomance from the one who solved the most problems on codeforces ever!

Submissions are obviously the same. Ali.Pi's B, Ali.P's B.

Please no notorious coincidence meme

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

В конце написано Рабор должен быть

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

edit:I know now why it will not work :-( adding -1 will not solve the problem :-D

I have a solution for div2/C div1/A , I want to know if it will work , because it seems simple to me and I checked it many times and it worked

I considered segment [1..inf] (from 1 to infinity) that describes the "game turns" as repeated segments of length 2(a+b) (see the figure for the different situations)

I replaced the choice of Mister B by -1

The solution will be as following :

- create a array in range 1..4*(a+b)  that represents the game in first 4(a+b) turns (see the figure)

if [l..r] in [1..4(a+b)] then
    count unique numbers in array[l..r]:
    If count>1 and you considered [-1] while counting then
	solution=count-1
    else
	solution=count

else if r-l>2(a+b) then
    solution=max solution (you can find it on range [1..2(a+b)]

else:
     reduce range to 1..4(a+b) and find solution as described in first branch of if condition
     reducing as following
     nl=l%(a+b)
     nr=r-(l-nl)

adedalic can you take a look

my solution code

sol
photo hosting service

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

problem writes are just pieces of shit.