AlexSkidanov's blog

Codeforces Round #488 editorial
By AlexSkidanov, history, 6 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +61
  • Vote: I do not like it

Comments Comments (71)
| Write comment?
»
6 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Fastest editorial ever! Kudos!

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

3 8 8 9 8 5 9 2 8 4 8 3 2 6 4 2 4 3 3 7 3 6 1 6 how is this in problem D give a "0",can someone explain?

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

    If person A has 8 9 as pair, then he knows that the hidden number is 8, since 9 doesn't appear in person B's communication. If he has the pair 8 5 the same thing hold, because 5 doesn't appear in B's communication. And if he has the pair 9 2, then the hidden number is 2, since 9 doesn't appear. So in any case person A will know the hidden number.

    You can do a similar reasoning for person B.

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

AlexSkidanov Can you please upload the solutions(code) also. Thanks in advance :)

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

In F you are only considering gates that always return 0 in one of the configurations. Why is it impossible that all gates sometimes return 0 and sometimes 1 in both configurations but still all gates return 0 in one configuration for each input?

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

    Edit: LHiC below challenged the author solution and the proof below. I will keep my incorrect proof here for history.

    1. You can only use the 6 second-layer gate kinds described in the editorial (all other setups return 1 in both original and inverted configuration at least for one input).

    2. If you have at least one of the first four kinds, such gate would return 1 for all inputs in one of the configurations, so you must have all gates return 0 in the other configuration for all inputs.

    3. You must include at least one gate of the first four kinds, because if you only include the gates of the last two kinds, then for the input of all ones all the gates in the second layer will return 0 in both original and inverted configuration, and the output of the circuit will be different in two configurations.

    Does it make sense?

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

    my opinion(passed the problem but maybe incorrect):

    it can be proven that,no gate always returns 0 in both(original,reversed) circuits,and if at a certain input,a gate returns 1 in both circuits,than it cannot be chosen.

    divide remaining ones into two types:we can prove that,either (0,1) or (1,0)(original result,reversed result) cannot be archived,so divide them by that.Only circuits in one type may be chosen,so in one of the configurations(decided by the type we chosen),it always returns 0.

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

Another Div2C/Div1A solution: If there exists a point in squares intersection, it's also exists a point in squares intersection with integer coordinates. Then we can just bruteforce all points, because absolute values of their coordinates are small (<=100).

Solution.

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

    how can you check if a point lies in the rotated square ?

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

      point lies in the rotated square if manhattan distance from it to square's center is equal or less to the half of square's diagonal

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

        Does this apply to a rectangle or a square with rotations other than 45 degrees? Can you also provide a proof of why does manhattan distance works? I've seen this method in Errichto solution here but couldn't prove it.

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

          It applies only to square rotated by 45.
          Proof, why it works:
          If you look to its sides, you can see that the manhattan distance from any point on the side to the center of square is constant and equal to half of the diagonal. So if a point is farther than that distance, it is obviously not in the square.

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

            The Manhattan distance property should apply to any square if that square is rotated around its center using geometric transformation such that its two diagonals are aligned with the coordinates of the 2D plane.

            The proof is a simple geometry exercise.

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

      I've checked only all points of rotated square, their coordinates are follows some uncomplicated regularities. For example, you can calculate length of diagonal and then start to bruteforce points one by one (first the higher one, then line of three points below, line of five etc.).

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

In Careful Maneuvering, my solution tries all possible meaningful positions for two spaceships, and then for each such combinations does simulation, so it is O(N5).

In Compute Power, I'm using the fact that values of b[i] are small to implement a solution that sorts tasks by power and then does knapsack dp[pref][i][j][sum_of_b] — where parameters are length of prefix, number of used computers with one task of higher power, number of used computers with one task of power equal to power of current task, sum of b[i] for first tasks on used computers so far, and the value of dp is total power used, so it is something like 50*50*50*5000.

Was any of these solutions considered during round preparation? What was the intended verdict for them? I'm confused because constraints look weird in both problems: it's like they aren't high enough to make it challenging to get AC with such solutions, but at the same time they are high enough to make it clear that intended solution is most likely different. Both of the solutions which I mentioned are not so hard to transform into right ones — but, at the same time, they are not so hard to cut off as well :)

Or is it about JavaBlitz thing, and they indeed don't pass in Java? :)

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

    How did you simulate in O(n)? I had to write a binary search resulting in O(n^5log(n)) which gave tle. for each spaceship I found if the resulting spaceship it hits is present or not and its range of indices so that I mark them hit. (I guess it is more than n^5logn, maybe n^6)

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

      Coordinates are small, so we can keep an array of flags to answer query "do we have a ship at position P?" in O(1) instead of doing binary search.

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

O(1) solution to Div2C without having to check for any intersections or handling many cases: Fix the center square, and see what locations the center of the diagonal square can be at. An octagon with 45 degree sides emerges. See below picture. The square in the middle is what is given to us, it has side length 2s. The diagonal square has a diagonal of length 2d. I drew 2 diagonal squares so you can see, if it is inside the octagon, then it intersects, otherwise it does not. We can represent this octagon as the union of two squares centered at the center of the first square, one parallel to the coordinate axes with side length s+d, and one at 45 degrees with side length 2s+d. Resulting code is short and clean: http://codeforces.me/contest/994/submission/39320205

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

can someone explain how this solution works: http://codeforces.me/contest/994/submission/39313692

thank you!

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

My approach for solving problem 994C - Two Squares was:

  1. Intersect the bounding box of the diagonal square [the smallest square whose sides are parallel to the X and Y axes and contains the diagonal square] with the first square whose sides are already parallel to the X and Y axes.
  2. Search inside the resulting intersection rectangle if it is non-empty for a point that the diagonal square contains. If such point exists, then the answer is "YES". Otherwise, the answer is "NO".

Since all the given integer numbers are between -100 and 100, the intersection rectangle can contain at most 40,000 points.

39333649

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

Don't last two kinds return 1 on all ones? nand(nand(1, 1), or(1, 1)) = 1. That makes author's solution incorrect on test:

3 6 6
nor xx. nor x.x nor .xx and xx. and x.x and .xx
and x...x. and x....x and .x.x.. and .x...x and ..xx.. and ..x.x.

All gates are of kind 5 (both participants' solutions return 0).

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

    Yep, this is a major mess up. I both misinterpreted the output of my script that was searching for the gate configurations, and evidently when I was stressing the solution against the naive, didn't get all the way up to 6 gates in both layers...

    Would be interesting then to hear how Um_nik and Errichto solved it.

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

      And damn, should have listened to those guys and thanked MikeMirzayanov in the announcement...

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

        So what happens afterwards? Is it rated at all?

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

          Yes, because there is a solution and the tests are not affected.

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

      My solution:

      There are two types of bad situations: on some input first circuit returns 1, but second returns 0 and vice versa.

      First type means that there is an input on which some gate in second layer of first circuit returns 1 and some (maybe other) gate in second layer of first circuit returns 1. Let's iterate over all ordered pairs of gates and check if there is such input. A pair of gates depends only on 8 variables, so we can check all possible values. If there is such input, we will draw an edge between these two gates. To satisfy first condition the set of remaining gates in our circuit must be an independent set in this graph.

      Second type means that there is an input on which all gates in second layer of both circuits return 0. Let's suppose (for now) that we only want to check if this condition is satisfied for the whole circuit. Let's say that outputs of two gates in the first layer which are inputs for some gate in second layer are X1, X2. So we want OP(X1, X2) = NOT(OP(NOT(X1), NOT(X2))) = 0. It is easy to see that if OP is OR/AND then we want X1 = X2 = 0, and if OP is NOR/NAND then we want X1 = X2 = 1. So, our condition is "some gates in first layer should be equal to given values". Since gates are only OR/AND/NOR/NAND it is some instance of 2-SAT problem.

      Now let's notice that that for second type some subset of a set is always worse than the whole set (we have less restrictions). So if we have some set on which there are no bad situations of first type than there is no need to check its subsets.

      So, the whole solution is: find all maximal independent sets (using Bron-Kerbosch algorithm), then for each of them check if 2-SAT has a solution.

      Yeah, it probably should be TL :)
      Initially I thought that we only need 2-SAT once in the beginning, wrote the solution, it doesn't work on second sample. I have like 20 minutes left, so have to come up with some tweaks.

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

        What if all maximal independent sets do not satisfy the 2-SAT? Do you need to check smaller independent sets?

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

          Maybe I used incorrect word. By 'maximal' I mean maximal by inclusion (I know that there are 'maximal' and 'maximum' but I don't know which is which :) ). If all of them do not satisfy then the answer is -1.

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

          If I understand Um_nik's solution right, 2-sat is used to find an input that would result in all the gates in some maximal set return zero in both configurations. If 2-sat finds such input, then such maximal set doesn't satisfy the condition from the problem statement, and naturally all its subsets do not satisfy it either (so no need to check them).

          Otherwise such a maximal subset is an answer candidate.

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

        I think that the number of maximum sets will be at most two. My reasoning:

        Let's split all the setups of gates in the second layer into four categories:

        1. ['nand(nand(a, b), and(a, b))', 'nand(or(a, b), nor(a, b))', 'or(nand(a, b), and(a, b))', 'or(or(a, b), nor(a, b))']

        All these setups return 1 for all inputs in the original configuration, and 0 for all inputs in the inverted.

        1. ['and(nand(a, b), and(a, b))', 'and(or(a, b), nor(a, b))', 'nor(nand(a, b), and(a, b))', 'nor(or(a, b), nor(a, b))']

        All these setups return 0 for all inputs in the original configuration, and 1 for all inputs in the inverted.

        1. ['and(and(a, b), nor(a, b))', 'nor(nand(a, b), or(a, b))', 'and(and(a, b), nor(a, c))', 'nor(nand(a, b), or(a, c))']

        All these setups return 0 for all inputs in the inverted configuration, and something that depends on the input in the original

        1. ['and(and(a, b), nor(a, b))', 'nor(nand(a, b), or(a, b))', 'and(and(a, b), nor(a, c))', 'nor(nand(a, b), or(a, c))']

        All these setups return 0 for all inputs in the original configuration, and something that depends on the input in the inverted

        All other setups return 1 in both original and inverted configuration for at least one input, and as such can't be in the resulting set.

        Now the maximal set might be one of the two forms:

        1. All the gates from the first category and all the gates from the third category. If there's at least one gate from the first category, such set satisfies the condition from the problem statement (since such gate return 1 for all the inputs in the original config). If there's no gate from the first category, then we need to run 2-sat to see if for every input there's at least one gate from the third configuration that returns 1 (this step was missing in my original incorrect solution)

        2. All the gates from the second category and all the gates from the fourth. Similar reasoning -- if at least one gate of second category exists, it's a good set, otherwise run 2-sat to check it.

        Now we need to show that no other maximal set exists.

        Gates from the first category can't possibly be with gates from the fourth, because gates from the first category always return 1 in the original configuration, and gates from the fourth return 1 for some inputs in the inverted, thus there's at least one input for which one of them returns 1 in one configuration, and one in another.

        Similarly gates from the second category can't be with gates from third.

        Finally, to show that the gates from the third can't be with the gates from the fourth, it is enough to show that if the input is all ones, the gates from the third category return 1 in the original configuration and the gates from the fourth category return 1 in the inverted configuration.

        If I haven't messed up anything above, your solution fits into TL since it will consider at most two maximal sets.

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

      Is it possible to add that test to the main tests for upsolving? if I hadn't read this comment I would have probably thought that my wrong solution is correct and never went back to it.

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

Please take this constructively — all the problem statements other than C could have been written in a much clearer way.

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

can someone please explain me the last sample test of Div2 D.

what i have understand : second person is sharing (1, 2) and (1, 3) so, it must have either (x,1) or (2, 3) and third time he is sharing (2, 3) and as this pair doesn't contain the both the numbers of second player. so, he must have (x, 1) but for (2, 3) to contain a number from his own pair (i.e(1,x)) he must have either (1, 2) or (1, 3) which will contradicts the first two pairs. so, how the given pairs are valid?

PS: sorry if someone finds this silly. but i'm really confused.

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

    I can't understand you explanation . In this test , first player showed(1,2),(4,5) , which means one of them is real and the other one is a "made-up" pair . The same for the second player . if (1,2) in first and (1,3) in second is true , the common one is 1 . If (1,2) in first is true and (2,3) in second is true , the common number is 2 . So the observer could not determine the common number . For players , the second player could determine the number because he know which of the (2,3) and (1,3) is true . But for first player , he only knows his (1,2) is true , but he could not determine the second player's pair . So the answer is "-1" . Note pair(4,5) couldn't be the true one because there's no common number in the second player's pairs . The same for the second player's (1,2) because there's either two common numbers(if the first player's pair is (1,2) ) or no common numbers(the first player's pair is (4,5) ).

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

      thanks a lot for this explanation.

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

I solved E by using divide and conquer and FFT that is O(nlog^2). FFT solution : http://codeforces.me/contest/993/submission/39324259 And I get TLE by using NTT instead of FFT. NTT solution(TLE) : http://codeforces.me/contest/993/submission/39317762 Can only body explain why there are so much difference between these two solutions?

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

div1B can be solved in O(n*m) Why n,m<=12? During the contest,I thought I misunderstood the problem at first because n,m was so small.

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

    Maybe it's just for confusing you. :)

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

RTE CODE my code shows RTE for some reason. can someone please tell why. When I replaced b[i] with variable t. It passed all test cases. this is so weird AC CODE

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

    You accessed from b[0] to b[m — 1], but the size of b is set to n, and m can be larger than n.

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

My approach for Div2B was using dynamic programming.

First, sort the knights by the power in ascending order.

Then, let them
dp[n][k] : the maximum number of coins the n-th knight has after he kills k other knights.
coin[n] : the number of coins the n-th knight initially has.

Finally,
dp[n][0] = coin[n]
dp[n][k] = MAX(dp[n - 1][k] - coin[n - 1], dp[n - 1][k - 1]) + coin[n]

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

In Div1 D , I saw the word"rounded up" . The google translation told me it means"1.4 -> 1 , 1.6->2" . Then I got wronganswer on test 8 and it turns out that we need to find the smallest integer which is bigger or equal than the answer .

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

    I actually believe it's a translation mistakes, cause author is (I guess) russian. "Round up" is a literall translation from russian, which in russian means "to round UP", so there is no ambiguity. Author just didn't notice it's a phrasal verb in English.

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

      May be this problem. The first time I saw this word , I thought it means "to Round UP" . Then I checked on google and discovered that it's a phrase . Anyway I'm not able to solve this problem during the contest and it doesn't matter too much for me . :)

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

Thanks for this fast editorial, ItsNear Senpai!!

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

There is solution for div1D without binary search and it have no mess with precision at all.

First of all lets gather vectors of bi for each unique ai and sort it from bigger to smaller.

dpi, j, k = minsuma where i step (we are iterating for unique ai) ;

j is how many computers can take second task(with this sorting it is valid) ;

k is how many processors is used;

minsuma is how minimum sum of A;

so shortly we calculate minimum sum of A for each valid possible sum of B. To do this on each step we try to update go from every state and we try to use some tasks as second and as first on computer. How to choose what tasks with equal ai will be second or first we need to conseder that tasks with bigger bi must go to first. Thus we only iterate size of tasks that will go as first.

Complecity see submission for deatils : 39313087

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

My solution for div1C: compute bitmasks of destroyed spaceships (1 bitmask for each side) for each position of a small spaceship. Precompute popcounts of numbers up to 220. Then try all pairs of these positions, compute ANDs of corresponding bitmask pairs, get the number of destroyed spaceships as the sum of 6 popcounts and take the maximum. Complexity O(N2M2(N + M) / 60).

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

    I solved with bitmask too, basicly generate all possible intersections points while updating its leftmask and rightmask with OR operation. iterate over all the possible pair of points, the answer is the maximum of popcount(leftmask[p1] | leftmask[p2]) + popcount(rightmask[p1] | rightmask[p2]).

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

how test case 37 results -1 for div 2 D problem??

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

elegant Python solution for Div2/B, sub: 39338337

R = lambda: map(int, input().split())
n, k = R()
v = []
t = [0]*n
for p, c, i in sorted(zip(R(), R(), range(n))):
    t[i] = sum(v)+c
    v += [c]
    v = sorted(v)[::-1]
    if len(v) > k:
        v.pop()
print(' '.join(map(str, t)))
→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

994C — Two Squares can be accepted with randomized algorithm with some special judge. My Code (If you are a lucky dog, you may pass with very short code. But for me, I think it's impossible xD

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

Giving testcase 8 WA in Div2 C and following the editorial only... Can anyone help?

http://codeforces.me/contest/994/submission/39349217

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

    Draw the two squares, then it should be obvious why your code doesn't work.

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

    I think you forget to check centers that mentioned in the editorial in first sentence.

    Input seems like this.

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

Why in the "Two squares" test: 3 6 3 7 4 7 4 6 5 0 0 5 5 10 10 5 breaks many people, and the testing system produces a "Full Solution"?

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

In the editorial of Div 2 D, there is actually no need to check for the point 2. Its because candidateship is commutative. If we found "a" as a candidate while iterating over the first array, we must be having some pair (a, b) in the first array and a pair (a, c) in the other one (where b != c) . But while iterating over the 2nd array, when we would have come across the pair (a, c) , we would have found the corresponding pair (a, b) in the other array. This means that a candidate found for the first array while iterating over it will also be found as a candidate for the second array while iterating over it, and vice versa. Therefore, the first and the second array have the same candidates.

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

In Div2 B, I keep getting WA on test 10, can someone tell me what am I doing wrong? Here's my code. http://codeforces.me/contest/994/submission/39424745

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

    Overflow. "#define vi vector <int>". You save the result which has got the type "long long" into the "vector <int> res(n)".

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

What's the complexity of Problem F?

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

Oh my god,n^2*m^2*(m+n) can pass div.1 C. See my code 39886117

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

Can someone help why the following solution for Div 2 B gets a Runtime Error on test 62 —

http://codeforces.me/contest/994/submission/41742929

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

I solved div1E for practice, and got WA in test 43 for float-precision. I changed it to long double and got AC. Then I read the editorial and found that simple doubles should not pass. However, after looking at the top 3 contestants from the round, Um_nik, Errichto, and scott_wu, the three of them used simple doubles and got AC! Here are the submissions, respectively: 39303954, 39298654, 39301524. I know the contest was ages ago, but I'm really curious to how they handled precision, since long doubles are unbearably slow! Can someone help me understand this please?

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

    The reason you have bad precision is the way you compute the roots of one:

    for(int i = 2; i < (1 << LG); i++) ur[i] = ur[i - 1] * ur[1];

    The precision errors stacks up when you compute every next uri. Instead, compute them independently:

    for(int i = 2; i < (1 << LG); i++) ur[i] = polar(1.0, i * M_PI * 2 / (1 << LG));

    You get AC with this change: http://codeforces.me/contest/993/submission/44679848. The disadvantage is that this preprocessing is much slower, but it's only done once so it's ok. Also, you can even start from i = 0 in this loop and not initialize ur0 and ur1 in a special way.

    I will soon create a tutorial about precision errors, maybe with some examples about FFT.

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

      That's very helpful, thank you very much. I will anxiously await you post, it sounds interesting. You could also consider writing a post on efficient FFT's, your solution is intriguingly fast.

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

      Also looking forward to your post about precision errors :)

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

For C coordinates when we rotate the origin by 45 degrees can be found using the formula.

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

i solved div2E for practise. seems like there exists another solution using bitmasks and stuff. can anyone explain what the other solution is? what do i need to read for that?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Alternate solution to Div-1D without binary search:

The main observation is that if we are using k tasks with some particular value of ai = x, then its always beneficial to choose the k tasks which have the greatest bi among all tasks with ai = x. (Since the contribution to the numerator of the average will be same for any k tasks with ai = x, so we can just maximise the contribution to the denominator and it will be optimal).

After that, you can just observe that the constraints of ai and bi will allow O(N^3 * MAX(B) * log(N)) solution to pass and code a simple DP.

https://codeforces.me/contest/993/submission/195044033

→ Reply