By PikMike, history, 3 weeks 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 Ajosteen Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Soroush Tabesh Soroush.T 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  

»
3 weeks ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

what is this and is it contributed??

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Second last chance to reach my 2018 rating goals lol.

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

However,I love Educational round.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

YESSS...a div2 round for candidates ;)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The last educational rounds in this year.... :')

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope it would be a great educational

»
3 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Hope I can become hahalmao555huehuekkkxixi after the contest.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Today I'll become a Christmas mandarin orange.

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

When can we change Nickname?

»
3 weeks 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.

»
3 weeks 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?

  • »
    »
    3 weeks 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.
    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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!

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Does anyone know why my nlogn solution is timing out?

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

    • »
      »
      »
      3 weeks 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

»
3 weeks 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)

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

number 998244353 everywhere

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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!

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

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

    +1, I got that wrong too. Help please.

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      3 weeks 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.

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

      Can u please explain this

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks 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)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you derive the last case?

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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"

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what if we take out substring "abe" and "b" from the middle??? we can do that..can we??

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

is this eduround 998244353?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It showed me Wrong answer on test 1

    But it was correct

»
3 weeks 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

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, that dp should work.

    • »
      »
      »
      3 weeks 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 ?

      • »
        »
        »
        »
        3 weeks 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

»
3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 16   Vote: I like it +1 Vote: I do not like it

    Me too :( 47654227

  • »
    »
    3 weeks 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.

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

      Thanks! I indeed made that flawed assumption.

    • »
      »
      »
      3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

the solution for C for god sake?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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"

      • »
        »
        »
        »
        3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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.

    • »
      »
      »
      3 weeks 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?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do we iterate only till 360?

  • »
    »
    3 weeks 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://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.

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

      can u please elaborate more for 4th input 178?

      If the required subtended angle > 180, then you have to ensure that if you find a "n", there must be a gap of at least 1 vertex between two vertices that subtend the required angle. why so???

      and how is that implemented by this way:-

      An equivalent way to form this is checking if the minimum subtended angle is not == complement angle.

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

        Hi padamprakash,

        First see this diagram: https://ibb.co/TTG787k and then read below. I will answer both your questions in the order you have asked them:

        1) Let's say the angle in the query is "q". Hence we need to find two vertices that subtend this angle at a 3rd vertex.

        A reminder of some math theory: Any two points on a circle form 2 arcs: Major and minor arc.

        If angle subtended at centre (2*q) is obtuse, then we are dealing with the major arc for the two vertices. If there is no vertex between them (means they are adjacent/consecutive vertices), then the major arc cannot subtend the angle "q" at a vertex between them !

        2) Let's take an example case, same as input 4 in problem set.

        q = 178.

        2*q = 356

        356 is > 180.

        Complement of 356 is 4 (360-4)

        If the minimum subtended angle = 4, then this means that any two adjacent/consecutive vertices subtend an angle of 4 at the centre of the circle. This means there is no gap between them !

        ^^^ Hope that is clear.

    • »
      »
      »
      3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

What's test case 3 in C?

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

    Not even with TNT man.

    that problem is really hard.

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

    neal did it 47640712

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

These guys are really good :D

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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

»
3 weeks 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://codeforces.com/profile/problem_destroyer420 Returns 0 for a particular n and voila hack from another id !

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    Mind your own GOD DAMN business!!!

  • »
    »
    3 weeks 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

  • »
    »
    3 weeks 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

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

PikMike

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

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

  • »
    »
    3 weeks 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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please check in yours. Then you will see

      • »
        »
        »
        »
        3 weeks 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)

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

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

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks 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?

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks 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.

          • »
            »
            »
            »
            »
            »
            3 weeks 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.

»
3 weeks 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://codeforces.com/contest/1096/submission/47640777

»
3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Integer overflow in line 36.

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
3 weeks 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?

  • »
    »
    3 weeks 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.

»
3 weeks 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

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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?

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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''.

        • »
          »
          »
          »
          »
          3 weeks 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 .

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

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks 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?

»
3 weeks 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?

»
3 weeks 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?

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

    For example when someone has an "if (time(0) > x) exit(0);" and time(0) is now greater than x while it was smaller during contest, the solution will fail when a hack is performed now. Example given: https://codeforces.com/contest/1088/submission/46594591 . Although it's totally useless to have this in your code, it's a possible way to hack C now.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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?

»
3 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

It be like that sometimes. F

»
3 weeks ago, # |
  Vote: I like it -54 Vote: I do not like it

please stop making contests

»
3 weeks 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's just . Use the linearity of expectations.

    • »
      »
      »
      3 weeks 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 ?

      • »
        »
        »
        »
        3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do C?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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

»
3 weeks 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...

»
3 weeks 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 !

  • »
    »
    3 weeks 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...

»
3 weeks 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.

»
3 weeks 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 ?

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

so much math ._.

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks 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!!!

  • »
    »
    3 weeks 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).

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

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what meme around number 998244353?

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, why is answer always for sides between 3 and 360 ? Can't answer exceed 360 ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    angle is 1<=ang<180. minimum angle is 1 so for n=360 min angle is 0.5 and the maximum angle is 359.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understood it. But for n=360 minimum is 0.5 and maximum is 179. For deg=180 answer would be -1.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the logic of D?

  • »
    »
    3 weeks 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)).

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

when will be the editorial released?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to take random result in problem A ???

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain the algorithm of C??

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

After reading problem D, i think that maybe easy. After thinking for a long time, i realize that too hard. :((

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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