10

Codeforces Round #789 Editorial

 2 years ago
source link: http://codeforces.com/blog/entry/102631
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By tokitsukaze, 2 days ago, In English

2 days ago, # |

Thanks for the fast editorial! <3

2 days ago, # |

-- Excuse me, what is the worst problem did you solved ever? -- Cf #789 B2. -- (surprising)

  • 2 days ago, # ^ |

    Although the problem was a bit difficult, but just because you missed some observation does not mean that problem was bad.

    Remember:

  • 2 days ago, # ^ |

    Typical cyan attitude.

    • 2 days ago, # ^ |

      B2 was not a bad problem though...

2 days ago, # |

in div1D I thought that we choose k indices where we swap and (((

2 days ago, # |

Certainly not the most comfortable round for Div2, but I liked problem C. Thanks for a great editorial btw.

2 days ago, # |

Obligatory to say this, since many people are talking about it:

Div1A in (with a BIT/Fenwick Tree) fits within the time limit, even though I think was chosen to specifically cut out these solutions.

  • 2 days ago, # ^ |

    Yeah, that's straight up bad prep. Either they should have made a lower limit, or made these solutions fail.

  • 2 days ago, # ^ |

    Mine ordered set solution fails but others Fenwick tree solution passes that's a bit unfair

  • 2 days ago, # ^ |

    Editorial mentions that n^2 logn solutions can pass too, so ig they didn't intend to cut them?

    • 45 hours ago, # ^ |

      It is hard to cut them. Who use n^2 logn solutions also will lose time.

  • 2 days ago, # ^ |

    I'm a bit surprised since my n^2logn solution using only upper_bounds(which are probably faster than/ not much slower than BIT) got TLE.

    • 2 days ago, # ^ |

      ← Rev. 3 →  

      0

      Yeah, I also assumed that upper_bound should be faster

      But now that I think about it rationally, BIT has much fewer operations, particularly by half fewer conditional jumps which are damn expensive. So it is only natural that bit is much faster

  • 2 days ago, # ^ |

    "was chosen to specifically cut out these solutions."

    Well, what is the point of cutting logn solutions? It doesn't even make the general idea much different

2 days ago, # |

← Rev. 2 →  

+87

Actually problem F can be solved when , my solution has complexity .

Our goal is to compute the coefficient of some polynomial satisfying

We have

Therefore we have

we write formally, here is the differential operator, then we have

we only need to compute the multiplicative inverse of , which can be done in .

  • 2 days ago, # ^ |

    Here's an alternative phrasing of this concept, which inlines the differential operator a little bit.

    Fix a polynomial . Now, let be a formal variable, and note that for any , . In particular, this contains all powers of , so we multiply this by a polynomial to get linear combinations of powers of (i.e. polynomials). In particular,

    Where denotes taking the coefficient of . Let , so that .

    Now, consider the sum . We can use the above form to get

    (This is valid because is a linear operator.) Note that is a geometric sum! Thus, we get

    We can split this term into

    Note that this only depends on the first coefficients of , and the left hand term can be viewed as a different polynomial evaluated at . The rest of the solution is the same.

    One final note: if , then does not have a generating function inverse, as it has constant term . In this case, we can instead use

    since $(e^t-1)/t$ has nonzero constant term. The generating function is thus the key thing to compute to find sums of powers; this is in fact the EGF of the Bernoulli numbers.

2 days ago, # |

ayy fast editorial :)

  • 44 hours ago, # ^ |

    This is actually very good solution, i understood it better than the editorial itself.

2 days ago, # |

← Rev. 2 →  

0

Thanks for nice debugging template.

2 days ago, # |

I'm very sorry for question 1F in div1. This question is not only the same as the question（ https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial） (I haven't seen it before), but it's really a garbage question. I'm very sorry for affecting the experience of div1 participants. I won't have such a problem next time.

My English is a little poor and may not be smooth.

2 days ago, # |

there is another dp solution to b2 and b1 with 4 states like

i = current character of string

p0 = parity of last consecutive 0s

p1 = parity pf last consecutive 1s.

p = parity of s[i — 1] where s is given string s.

Solution[submission:156354472]

2 days ago, # |

← Rev. 2 →  

+3

dp states for problem B is wrong, please correct to

Solution link

  • 2 days ago, # ^ |

    Thank you for pointing out.

2 days ago, # |

I did Problem C in O(n^2 logn) using binary search, got TLE. But the editorial says it will pass. How is this possible? My solution link : https://codeforces.com/contest/1678/submission/156353215

  • 2 days ago, # ^ |

    My solution is also O(n^2 logn) and it passes comfortably: I did it by brute-forcing b and c here

    • 2 days ago, # ^ |

      Well theoretically it should not pass as the # of operations: O(5000*5000*13) = 3.25 * 10^8. And we can process 10^8 operations in 1 sec.

      • 2 days ago, # ^ |

        You assumed it takes exactly 1e8 operations in a second. I've seen somewhere I can't remember that its something like 4e8 or so(not sure but i'm sure 1e8 is just used as a rough estimate)... Also, stuff like compiler optimizations etc might happen.

  • 34 hours ago, # ^ |

    Function overhead + Higher constant?

2 days ago, # |

If you prefer command line, checkout CF Doctor for more flexibility and faster feedback.

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

Divison 1

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

2 days ago, # |

I think the most important observation for B1 & B2 is that we can just look at each digit-pair's index to determine whether we need to change it: specifically, if we have an "01" or "10" at an even position, we must change it, because finally every segment will be of even length so each such "01" or "10" must reside in a single segment instead of at the boundary of two segments.

  • 2 days ago, # ^ |

    ← Rev. 3 →  

    +6

    Unfortunately I missed this observation during the contest and failed to solve B2... and solved B1 using a more complicated solution.

2 days ago, # |

Thanks for the good round!!! Thanks for the editorial!!!

2 days ago, # |

Why is it written in editorial that n*n*logn should pass in Div2C?

  • 45 hours ago, # ^ |

    a problem can be solved by many methods,we should not think one problem only to one solution

    • 43 hours ago, # ^ |

      But I got TLE on n*n*logn :(

      • 43 hours ago, # ^ |

        May I have a look about your solution?

        • 43 hours ago, # ^ |

          This 156351799 solution was getting TLE.

          • 38 hours ago, # ^ |

            I read through your code and noticed that there are a lot of copy-like or sort-like parts in your code, which will greatly increase the running time of your code by a constant multiple (roughly counted as 6 times). is not an optimal solution in the first place, and will probably fail in the case of large constants. But your idea is roughly correct, you can try to maintain the steps of the array sorting section to maintain the previous and next values through the value field by O(n^2), thus avoiding the log

            • 37 hours ago, # ^ |

              Thanks for your reply. Got it!

          • 38 hours ago, # ^ |

            by the wall , you can use int instead of ll except the final answer

2 days ago, # |

For Div. 2 C, this solution can also pass. Let suffix_count[i][v] be the number of elements in p[i..n] that is smaller than v. Similarly we have prefix_count[i][v]. Those two arrays can be calculated in O(n^2): first enumerate v then enumerate i and maintain the suffix/prefix total. Then you just enumerate all 1 < b < c < n, and for each pair of b and c just add suffix_count[c + 1][p[b]] * prefix_count[b - 1][p[c]] to the answer.

  • 2 days ago, # ^ |

    I implemented exactly this (but with different two iterations)

    156328504

  • 28 hours ago, # ^ |

    Why not just write the maths? Let's note:

    We want to compute:

    which is equal to:

    using s[i][j], we obtain:

2 days ago, # |

I read the first question wrong and wasted more than one hour in it. It feels frustrating :(

  • 11 hours ago, # ^ |

    Wait till you encounter a contest where you spend one hour to finish reading what Petya is up to.

2 days ago, # |

Why does 156322948 this solution pass and 156357149 gives MLE. Both have O(n2) space complexity I think.

  • 2 days ago, # ^ |

    Used int instead of long long and it passed ;_;

    • 2 days ago, # ^ |

      For me I was using array during contest it was showing MLE. But now with same size vector it passed

2 days ago, # |

← Rev. 2 →  

+6

Today's Div2c is similar to click here

2 days ago, # |

Can anyone explain more about the tutorial of div1 E? What's the difference algorithm and the a*R+b part?

2 days ago, # |

Hi can someone tell me why this code times out on Div2.C. I am new to segment trees but I knew there was a way to use it to find the number of elements less than x within a given range, so I took the code online and tried it but it times out. Any help is appreciated. Thank you https://codeforces.com/contest/1678/submission/156367158

  • 2 days ago, # ^ |

    I might be wrong but I think it is just because of constants. Segment tree already has very big constants and your implementation uses vectors which adds more constants and is not necessary. Try to use a Fenwick tree instead which is strictly O(logN).

  • 2 days ago, # ^ |

    you need O(n^2) to pass this problem.

2 days ago, # |

Participating in div2 contest was pretty hard for me because of B2 being so strange. Anyway, I upsolved this contest and I have 1 question: How D2F (D1D) is supposed to be D2F? It seems pretty like D2D for me, and I spent much more time on D2D/D2E, than on D2F

2 days ago, # |

Can someone please help me understand what the variable y means in the greedy solution for problem B2? I've been trying to wrap my head around the greedy solution, but I'm just not getting it.

47 hours ago, # |

sjfsb

46 hours ago, # |

I cannot understand why I have to check if it is impossible to make original permutations in div1 D. In statement, you said that the unclear value sequence was originated from some value sequence that Tokitsukaze made. So I think the unclear value sequence of the problem must have at least one correct original permutation.

46 hours ago, # |

I had a doubt with this submission for Problem C : 156336500 I used PBDS of C++ to find the number of Pa < Pc and Pb > Pd where I'm iterating over b and c and finding the number of Pa and Pd and since we can select any of those a or d we multiply and add for all cases. Help

45 hours ago, # |

Why did my solution failed for B2 , any test cases where my solution is not correct ? 1678B2 - Tokitsukaze and Good 01-String (hard version) 156326219

  • 43 hours ago, # ^ |

    Your solution is failing on the following test case :

    test case

    The answer should be "1 2" but your answer is "1 3"

    • 41 hour(s) ago, # ^ |

      ← Rev. 2 →  

      0

      Got it , Thanks a lot :)

40 hours ago, # |

Can anyone please help me for Problem A with Round #789 Division 2 my logic seems to be alright as compared to the one given in the editorial I don't know why I am getting Wrong Answer....

Here is my code, 156393108

Also Here is the one which I submitted when the Contest was live....156311829

  • 39 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Your Solution is failing on following test case :

    test case

    Answer should be 3 but it is giving 4. This is because in your solution you are checking if adjacent number are eqaul or not , but actually you should check if any 2 number are eqaul. For example in this case "1 2 1" have two numbers equal (first and last) so it should return n , but in your solution because it is not adjacent it will return n+1 , which is wrong.

    • 39 hours ago, # ^ |

      thanks for pointing that out

38 hours ago, # |

It hurts a lot when your solution got wrong because of just two line mistake. :( But it also helps you motivate not to do it again :) Thanks for solutions.....

35 hours ago, # |

Can someone help me understand the fenwick tree solution for Tokitsukaze and strange equality

34 hours ago, # |

suggest me some tips on how to solve c in contest .topics difficulty range or any other resources to follow

34 hours ago, # |

Div-2 C is kind of hard to understand from the tutorial. Anyone else having problem too?

32 hours ago, # |

div-2, Problem B, this problem is an example of how valuable a good observation is!

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK