Educational Codeforces Round 57 [Rated for Div. 2]
By awoo, history, 6 years ago, translation, In English

Hello Codeforces!

On Dec/28/2018 17:35 (Moscow time) Educational Codeforces Round 57 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Soroush Tabesh Soroush and me.

Good luck to all participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 chuochuo 7 222
2 Traxex_ 7 270
3 quailty 7 281
4 hitman623 7 285
5 E.Space 7 316

69 successful hacks and 296 unsuccessful hacks were made in total! The table doesn't look that interesting this time, so I won't include it.

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A irkstepanov 0:00
B ChiIIi 0:03
C Qing_Yang 0:06
D aleex 0:07
E chuochuo 0:57
F isaf27 0:19
G 300iq 0:06

UPD: Editorial is out

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

Comments Comments (169)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

ggguys i cant wait! !=) X) :)

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

Second last chance to reach my 2018 rating goals lol.

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

hello gays i live in a very wealthy part of the austro hungarian empire and i am wondering if the contest will be worthy of my royal time i request you inform my intelligence on whether the contest will be rated or not

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

However,I love Educational round.

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

YESSS...a div2 round for candidates ;)

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

I hope it would be a great educational

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

Hope I can become hahalmao555huehuekkkxixi after the contest.

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

Today I'll become a Christmas mandarin orange.

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

Nickname?

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

One interesting thing in this contest is that both the description and problem name of problem G greatly resembles Problem D in XVIII Open Cup, GP of Urals. But the solution differs a lot, and actually, the solution to that Open Cup problem is more similar to Problem E of this contest. That's why I think the problem difficulty of E,F and G in this contest should be rearranged, with G being extremely trivial once you know FFT, F being some simple calculation once you know the linearity of expectation, and E needs some combinatorics knowledge(like counting in a multiset and inclusion-exclusion principle). And the number of accepted solutions seems to prove me right.

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

Problem F reduces (at least I reduced) to calculating this sum in small complexity:

for given x, y, m.

Any hints to calculate this?

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

    LOL, LMAO, ROFL. No, it's not solved like that.

    Normal solution: there are three kinds of inversions:

    1. Inversions between known elements — they are calculated by your favourite method (Fenwick / mergesort)
    2. Inversions between unknown elements — if there are P unknown elements, they form P*(P-1)/4 inversions due to symmetry
    3. The last case is when one element is known, and the other is unknown. Let the known element be x, and there are some free places to the left and some free places to the right. For each of free left places, there is an inversion if you put element > x there (find count of these elements by lower_bound). For each of free right places, there is an inversion if you put element < x there (find count of these elements by lower_bound). And the rest is easy.
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      LOL, LMAO, ROFL. No, it's not answered like that.

      My question is about calculating the sum not how to solve the problem. Anyways, thanks for the solution :P

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

        This is a valid method of calculating the sum in reasonable complexity though, given that it reduces to the same thing (differing by some easy-to-calculate value). You're just counting the same thing in different ways and equating them.

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

        I think you have already figured out how to solve this problem, my reply is too late. :P I was trapped in the same calculation as you. However, after peeking others' solutions, I found it better to calculate the expectation alone, rather than calculate P and Q separately. This problem enlightened me a new angle to calculate expectations. When it is the case that P is hard to calculate, we may try to calculate the expectation directly. Good luck!

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

    First idea and very overkill is next: let and , then your sum is coefficient of zm of a convolution A × B or something like this (if you calculating with modules). Convolution FFT.

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

      If you write A and B in closed form as follows:

      A = x·z·(1 + z)x - 1

      B = (1 + z)y

      and then multiply them, then coefficient of zm in A × B = x·z·(1 + z)x + y - 1 would be simply x·C(x + y - 1, m - 1).

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

    Does anyone know why my nlogn solution is timing out?

    https://mirror.codeforces.com/contest/1096/submission/47665224

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

      It might be because my distance is linear...but I also tried with Fenwick tree, and still.timeout

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

It's guaranteed that rating of this topic will never exceed 998244353 (by absolute value).

(OK, it's not really)

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

number 998244353 everywhere

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

How to solve G? Is it some sort of bruteforce on small strings + DP? Couldn't figure out the details in time.

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

    Trivial when you know how to accelerate polynomial multiplication using Fast Fourier Transform.

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

      Can you elaborate a bit? Specifically, what are the polynomials you're building and then multiplying? Thanks!

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

        Let polynomial f(x) = a0 + a1x + ... + a9x9, where ai = 1 if i is an available digit and 0 otherwise. Then the answer is sum over the square of every term of f(x)n / 2.

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

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

How to solve B?

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

    Count length of prefix and suffix such that all characters in the prefix/suffix are equal.

    if prefix == n, answer is n * (n+1) /2

    if first char == last char, answer is (prefix+1) * (suffix+1)

    else the answer is 1 + prefix + suffix

    Edit: first case won't happen

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

      https://mirror.codeforces.com/contest/1096/submission/47648603 is it not correct then?

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

        It is wrong due to overflow of int ans. Replace itwith long long, it will be accepte.

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

      I think the first case won't be used, as its given in the question that there are at least 2 distinct characters.

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

      can u tell me how u derive the 2nd case?

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

        First char == last char means you have a string that looks something like aaabcaaa

        Any way that you split the string will work if it excludes the 'bc'. Consider this:

        |a|a|a|bc|a|a|a|

        Choose two bars, one of left of bc, one on right — that represents a substring that you remove. Note that there are p+1=4 bars on each side, p being number of a's on each side. Because you are taking one from each side, the answer is (prefix + 1) * (suffix + 1)

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

      How do you derive the last case?

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

        Say you have this:

        |a|a|a|cc|b|b|b|

        Each bar to the left of the "cc" represents a substring that you can remove (from the bar to the right). Each bar to the right is a substring from the bar to the left.

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

      [user:goloins] can you please tell the answer to "aabee" ??/according to conditions mentioned by you answer should be 5 but it is coming 7!!! I may be wrong..hopefully you can point out my mistake

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

        The answer should be 5. The resulting strings are "", "a", "aa", "e", "ee"

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

is this eduround 998244353?

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

What was wrong with C? I messed it up :(

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

    It showed me Wrong answer on test 1

    But it was correct

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

Am I the only one who stupidly thought B answer is x*(x+1)/2

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

Is D f(i,j) = min ans for prefix i such that starting j letters of hard are taken.

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

    i don't know, but my solution is this rsrs.

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

    Yeah, that dp should work.

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

      I could be missing something obvious but I don't understand why that dp works ? Could you please explain ?

      EDIT: Maybe I just dont understand what "starting j letters of hard are taken" means here. Could someone just elaborate on that ?

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

        Minimum cost we can obtain from prefix till index i such that the resultant subsequence contains first j characters from string "hard" in order. Then you can do DP : 47674309

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

I got WA on test case 4 for problem D, does anyone know what could be wrong 47654263

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

    Me too :( 47654227

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

    Test 4 catches a lot of bugs; from a quick scan of your code, it seems like you made the assumption that the solution must be removing all the occurrences of one letter. This isn't the case. Consider if the string is "harard", where the first a and the last r are very cheap to remove, but everything else is very expensive. Removing those two letters would be the solution.

    The general problem is solved using DP.

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

      Thanks! I indeed made that flawed assumption.

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

      Thank you very much for that test case. I also made that assumption but there was no way of figuring that out from test case 4.

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

the solution for C for god sake?

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

    Multiple of pi(180) which is multiple of alpha angle. Also check that internal angle obtained is greater than or equal to alpha angle.

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

    for every side length k from 3 to 360:

    smallest angle = 360/(k*2) biggest angle = 180-360/k

    every angle in between is a multiple of the smallest angle. If the angle you're being asked is between the smallest and biggest angle and it is a multiple of the smallest angle, then the answer is k.

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

      please tell the proof regarding "every angle in between is a multiple of smallest angle"

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

        Imagine the polygon as a circle with points on it.

        The inscribed angle theorem relates length of curve to the angle. https://www.mathsisfun.com/geometry/circle-theorems.html

        The smallest angle represents the arclength between two adjacent points, and every possible angle represents the arclength of some integer * the smallest possible arclength.

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

        essentially any regular n sided shape can be placed inside a circle. any angle is the sum of the different smallest triangles that divide up the shape around an arbitrary point. circle geometry states that because some of the angles subtend equal arcs/segments then the smallest angles must also be equal, and hence any angle formed must be a multiple of the smallest angle

        edit: ok you responded by the time i send this.

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

      How did u came to the conclusion that all angles in between are multiple of smallest angle?

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

    I've solved it and here is a link to my solution: https://mirror.codeforces.com/contest/1096/submission/47665926

    You may want to read below to understand it.

    EXPLANATION:

    It's a property from grade 10 (high school) maths.

    If you draw a circumscribed circle around the regular polygon, the angle subtended (by any two vertices/arc) at the centre of the polygon will always be double of angle subtended anywhere on the circle.

    Here is a youtube link if you want the proof: https://www.youtube.com/watch?v=MyzGVbCHh5M

    ============ Steps ===========

    1) The input needs us to find a suitable "n" for a given query angle "q". What we do is find suitable "n" for angle subtended at the centre of the circle. which is 2* q.

    2) But how do we find "n" ?

    Total angle subtended at the centre of a circle by any two vertices can be a max of 360 (to be precise, some decimal value < 360). Hence if you have "n" vertices, you can "distribute" this 360 between the vertices.

    What I mean by that is that if there are 10 vertices, then every 2 adjacent vertices will subtend 360/10 (=36) at the centre.

    To find "n", we need to use a loop , eg: for(n = 3; n <= 360; ++n) Start from n = 3, so that you can get minimum "n" once below condition is satisfied. On finding it, break from the loop.

    // NOTE: For this problem, "360/n" must also be an integer. Hence you must // ignore values of "n" if "360 % n != 0"

    if( (2*q) % (360/n) == 0 ) {

    // found n. 
//Break from loop if you have structured your code that way.

    }

    This condition means that if our required subtended angle (2*q) is a multiple of the minimum possible subtended angle for a given "n", then we have found "n" (there is an edge case, see Note below)

    =======

    FINAL NOTE: There is an edge case in the sample input and output given in the problem statement, the 4th input (178) has output 180, and not 90. this is hard to explain in words but much easier to understand visually. I have commented about this in my solution (linked above) as well. Please see that comment and try drawing it out if you don't follow.

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

      I can't believe I missed the central/peripheral angle thing.

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

What's test case 3 in C?

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

Did someone get AC on G with FFT (not NTT)?

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

    Not even with TNT man.

    that problem is really hard.

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

    neal did it 47640712

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

    I did it. To avoid precision error, I used the well-known technique that decomposes each integer into two parts. Calculate both on the real and imaginary part to reduce some factors. Basically, it's the template that tourist uses, very well-implemented and works with arbitrary modulos.

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

These guys are really good :D

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

    Is it that you didn't read problem F and G, or just that you're too weak to learn how to solve them?

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

      well well, look who is a Legendary grandmaster and who is a Specialist now

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

This user is hoax and the person who hacks his solution needs to be reported or taken down !! https://mirror.codeforces.com/profile/problem_destroyer420 Returns 0 for a particular n and voila hack from another id !

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

    Mind your own GOD DAMN business!!!

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

    Prove that the two accounts have something in common. Basically all you do now is accusing 2 innocent people without any proof. Go learn some programming, green boi

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

    I guess u r subscribed to T Series. Get out of my sight

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

C had a nice corner case and D was a nice problem in general. Enjoyed the problems, although it seems difficulty for tail end of problems was slightly mis-estimated.

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

awoo

https://mirror.codeforces.com/contest/1096/submission/47652681

What is wrong with this? In my compiler it shows correct!

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

    The output is just different... if your compiler is not giving the same answer you should make sure they are consistent but I feel it may just be you not looking closlely

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

      Please check in yours. Then you will see

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

        Ok, I got 18 on my compiler too. We must both be using a compiler not like codeforces. The only difference I can think of is the way division happens, with your code, a slight difference could cause floating point errors. If you don't use any doubles you may be able to get the right answer (and it is better to not use doubles anyways, it will likely break on later test cases even with your compiler)

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

          I don't care cf compiler. Make me expert MikeMirzayanov!

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

            You should take care of precision errors. int(x) is a bad way to round a double, since if you get 0.9999999 instead of 1.00000, int(x) returns 1.

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

              what is the best way to round-off whenever needed? Is (int)(floor(x)) always fine?

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

                Firstly, it's always better to work with integral datatypes if it is possible.

                And secondly, (int)(floor(x)) is bad because of the same reasons. Typically (int)(x + EPS) works well, where EPS is somewhere around 10 - 9, provided that x is non-negative.

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

            Maybe your code isn't so robust. Please avoid using doubles if possible. Actually, I think it more important for you to learn how to solve it without doubles. Good luck at Goodbye 2018! Wish you expert next time.

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

Fake hack: applese hacked __123456__'s submission to problem A. It has a special if for failing on purpose:

https://mirror.codeforces.com/contest/1096/submission/47640777

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

I got WA on test 4 for problem B, does anyone know what could be wrong 47654945

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

    Integer overflow in line 36.

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

      thanks,but i am a little confuse that why it would be overflow,i think the fr and en should be lower than 2*10^5.

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

        But fr*en will be 10^10 which will overflow

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

How to solve D?

I assumed that it is optimal to delete only one type of character. Is this assumption incorrect?

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

    DP[i][j] = minimum cost to delete the first 'j' characters of "hard" from prefix i.

    That assumption is incorrect.

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

On problem G. I used Divide and Conquer + polynomial multiplication ,but get TLE However, if someone had used dft & fastpow & idft , he would have AC

My IQ is not enough to figure out the second way(it's 23:30 in China), but these two ways have the same time complexity O(nlogn)

Although I think it is ok not to let me pass, but I'm very sad. With this problem I would become Orange(my current rating is 2097)

TAT

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

    It's just the issue with constant. Well-implemented FFT can pass,too.

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

    D&C + polynomail multiplication is .

    Or did you use some special version of D&C?

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

      No. With the equation , you can see that . Same complexity with polynomial inverse/exponentiation/logarithm and some other operations.

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

        In D&C it's , if it's implemented just like ''divide the segment into two, solve recursively and then combine answers with polynomial multiplication''.

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

          Yes. But here we are exponentiating a polynomial, and we only need to calculate one half, and the other half is the same, and thus the 2 factor is gone. You can implement it use fast exponentiation just like exponentiating integers. Time complexity is .

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

            Yes. It's one of model solutions. But Ez3qwq's solution lacks this optimization, so it's TL.

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

              Okay.

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

                I think I know why I TLE

                My brain is completely offline Ahhhhhhhh

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

Problem F is similar to SRM 470 Division 1 — Level Two

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

I want to check if my code is wrong, so I hack myself.
I write a program in python3 to hack problem C: 

print("180")  
for i in range(1, 180):  
    print(i)

but system said "Validator 'val.exe' returns exit code 3 [FAIL Unexpected end of file — token expected (stdin, line 181)]", can somebody help me to solve this problem?

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

For problem G, could someone provide an explanation of how to deal with MOD in fft?

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

How can someone hack problem C if they have included all possible values of angle in pretest #3?

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

To problemsetters, G is definitely a cool problem. However, do you really think it is suitable for contests rated for Div2? This problem could be easily solved by just copying FFT templates. I think this not fair to the newcomers who has problem solving skills but didn't know much algorithm yet. I think putting these kind of problems in the problemset will cause the rating to be less accurate.

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

    Even though ERs sound like regular Div2 and behave like regular Div2, we (authors) still believe that it's not a regular Div2. That's why we allow ourselves more freedom in using "well-known" ideas (but still trying hard to find a balance).

    Of course, it will lead to some disturbance of ratings, but it's a thing we should deal with.

    On the other hand, if newcomers wouldn't confront new for themselves but famous in community tasks, they will not learn them. And I think, ER is a perfect place to meet with such tasks.

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

      I agree. If it wasn't for educational rounds, this task would not fit anywhere on Codeforces. It's too easy for Div 1 D/E, and putting it in a regular div2 round seems strictly worse than putting it in a educational round.

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

In problem A, in the output format it is clearly stated that the answer in the i-th line should correspond to the i-th query but I just saw a submission who has printed l and 2*l in seperate lines but the verdict is ok. Is it actually fine to print it on seperate lines?

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

It be like that sometimes. F

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

please stop making contests

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

How to solve F ? Or atleast is there a way to find total number of inversions among all the n! permutations

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

    It's just . Use the linearity of expectations.

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

      Ok. I now googled and Got it for no of inversions for n!. Any how thanks for replying. But how is that n! * n * (n-1) / 4 ? Can you plz show me the proof or method of deriving it ?

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

        For a single random permutation, 0 inversions is the best case, n*(n-1)/2 is the worst case. Due to symmetry (you can remap i -> n-i+1), the expected value is n*(n-1)/4

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

        For every permutation, you can take it along with its reverse permutation. Every possible inversion happens in either the permutation or its reverse. This implies that the average number of inversions is n * (n — 1) / 4.

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

how to do C?

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

    Handle ang = 179 separately, n= 360;
    (This is because for every angle less than 179, we can attain it using a polygon with no. of sides n <=180)

    For other values of ang:
    Start with no. of sides s = min(3, ceil(360/(180-ang)))[This checks if the minimum angle possible in the polygon is greater than or equal to ang ] This was derived from, angle of a regular n-gon = (n-2)*180/n;

    Now we need to satisfy,
    i*ang == j*180; (for some s<=i<=180, and j<i)
    (Idea behind this is: ang/180 == j/i; ie "ratio of ang to the total angle of a triangle" should be equal to the "ratio of no of sides opposite of ang to the total no. of sides of the polygon") This can be done by brute-forcing on i and j;
    Thus complexity is O(n^3).
    Here's my submission.

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

    Let t = gcd(180, ang). Result will be  - 1 if ang = 180, if , otherwise

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

When you have no idea for C, so you decide to build regular polygons and check all angles between them until you've precomputed the answer for all angles...

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

Peace on You All :D

I Have a question in "D" Problem .. Why my Greedy Solution is Wrong ?Here

The Idea Is ,

If i delete all character ( 'h' , 'a' , 'r', or 'd' ) it will be impossible to get subsequence = "hard" is that right ? but this is not the all answer the rest is coming

this is how i choose characters to delete character "d" i delete if there is a subsequence = "har" before .

character "r" i delete if there is a subsequence = "ha" before and i will walk to last "d" i choose to delete .

character "a" i delete if there is a character = "h" before and i will walk to last "r" i choose to delete .

character "h" i delete and i will walk to last "a" i choose to delete .

and i will print the Minimum of all that . Why This is Wrong !

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

    I think my solution is similar to yours, however, I find the greedy solution will not work for the following case: "harard", [100, 1, 100, 100, 1, 100]. The minimum cost is 2 when you remove 'a' at 2 and 'r' at 5, and the result string is 'hrad'. It takes me a long time to figure out this, I'm still working on understanding the DP solution after checking the accepted code from others...

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

In problem C, that line print −1 if there is no such n made me question myself a several times.

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

I have no idea how to solve C , can anyone help how to solve ?

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

so much math ._.

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

I think ideally, an accepted problem C cannot be hacked nor fail main tests. As the pre-test 3 checks all possible 1<=ang<=179.

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

In what complexity should E be solved? My O(N*S*2) solution doesn't pass.

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

can someone explain intuition behind D? i tried some people's solutions and coded them but i still don't fully understand them.

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

i don't know why the answer of task 178 is 180, but not 90 on problem C!!!

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

    It is true that you can form angles in increments of 2 with a polygon of size 90. However, the max angle you can form is 176 ((n-2)*180/n).

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

    Build a regular 90-gon and try to find out yourself lmao.

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

what meme around number 998244353?

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

    Needed for NTT, one of the solutions for problem G. Specifically, NTT needs that your prime modulo be off the form n*2^k +1. That mod fits. Presumably, they used it through the whole contest to not give too much away.

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

Can anyone explain the logic of D?

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

    dp[i][j] is minimum ambiguity when we are at prefix j of string "hard". So,we are at state (i,j) and in next index (prefix j+1) comes, we have two choice, either to remove that letter or continue without removing(increasing prefix) and in next index any other letter arrives,we will be in same state. hence transition will be if(next index is next character after j) dp(i,j)=min(dp(i+1,j+1),dp(i+1,j)+a[i+1]) else dp(i,j)=(dp(i+1,j)).

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

when will be the editorial released?

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

How to take random result in problem A ???

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

    just print(ans, ans*2)..that's enough since it is the best case and the problemsetter said that it is guaranteed that the answer exist

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

Can you explain the algorithm of C??

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Reply