Radewoosh's blog

Hello 2019 Editorial
By Radewoosh, 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...
Tutorial of Hello 2019
  • Vote: I like it
  • +127
  • Vote: I do not like it

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

thanks for the tutorial!

How to split sequence into |LIS| decreasing sequence in E?

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

    We'll use the "standard" LIS algorithm with binary searching: sweep through the array, and maintain an array of dp[l] = min(A[i] s.t. there's an increasing sequence of length l ending at A[i]).

    When we see a new value A[k], we binary search and find the maximum length l such that dp[l] < A[k]; then we know there's an increasing sequence of length l+1 ending at A[k]. Also, l is maximal, so dp[l+1] > A[k], so we should update dp[l+1] = A[k].

    Now, note that the sequence over time of values of dp[l] is decreasing. Thus, these are precisely a partition of the permutation into |LIS| decreasing subsequences, so we can store a vector for each dp[l], and get the subsequences.

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

      But why is its running time

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

        The running time of the LIS algorithm is only , but we have to run it times because we're slowly removing one LIS at a time.

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

      Why does removing the maximum of LIS or LDS each time give the wrong answer?

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

where does the Youtube tutorial go? :/

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

For 1097D why is the result multiplicative?

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

    If you calculate the expected value for a given n with k = 1 (one step), you see that the answer is simply σ1(n) / σ0(n), where σ1(n) denotes the sum of divisors of n and σ0(n) the number of divisors.

    It's well known that σ1 and σ0 are multiplicative functions (and easy to prove indeed). So, it's easy to see from there using induction that the function is multiplicative.

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

    I wasn't sure when I was in the contest, so I used DFS to search all the divisors of n, the complexity is correct.

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

    E[f(X)g(Y)] = E[f(X)]×E[g(Y)], if X and Y are independent. Here exponents of each prime divisor of N are independent of each other, and E(.) denotes the expectation value.

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

can anyone help me with problem B

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

    Since the constrains are small, u can apply brute force, a simple approach is that for every given angle u can consider rotating it either clockwise(+) or anti-clockwise(-). Do it for all the angles in the array and keep summing them, if in one of the ways u get a final sum(after one complete traversal of array) which is divisible by 360, then output 'yes' other wise if non of the ways satisfy the condition sum%360==0 then output 'no'. There are total 2^15 ways(maximum) of obtaining the final sum. Refer to my solution for more clarity. https://mirror.codeforces.com/contest/1097/submission/47914337

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

      Yes, we can approach all the possible combinations using bit masking

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

How to calculate dp(k,j) in problem D.

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

In my opinion, posting fast such editorials without tutorials of some task is muuuch better

It gives time for problemsetter to write missing ones clearly and others an oportunity to read available parts and try to understand them

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

in problem c " The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence". Can someone explain me the solution of c in context of the bold statement above.if we want each bracket sequence occur in at most one pair then how is the editorial solution is correct. for ex if sequences given are : "((,)),)())" then solution according to the editorial will be 1 but there will be one sequence left with no pair which violates the condition in the bold statement.Can someone clarify my doubt

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

    At most one means zero or one.

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

For 1097B, how to solve it if N is bigger?

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

    like this:47957456

    it is O(nk) and can be O(nk / 32) if you use bitset

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

      I will be glad if you make me understand these according to editorial: shanxizeng Aman_98 blitzitout

      i) why should I chose 2^n-1 instead of 2^n

      ii) If i-th bit is 0 so we should do it clockwise rotation for i-th, why?

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

        1. In general, this is a technique for brute forcing and looking at all possible outcomes. Since, every angle has 2 options (either CW or ACW), we have at most $$$2^N$$$ possibilities. We can represent all possible outcomes in terms of binary representation of all numbers from $$$0$$$(all 0s) to $$$2^N-1$$$(all 1s). So, we can check a total of $$$2^N$$$ possibilities and see if we get the desired result.

        2. Basically bit 0 represents one choice and bit 1 represents the leftover choice. There is no hard and fast rule, you can assign any direction to any bit. Either way it's fine.

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

      shanxizeng Can you explain This Solution — 47957456 of yours for the problem 1097B - Petr and a Combination Lock.

      I Have dried run it thoroughly but i am not able to understand the idea behind it.

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

        Firstly,you can define h[i][j] as something that if you can get a j after rotate i time.If it's true,the value is 1,or it's 0.And you can simply get that h[i][j]=h[i-1][(j-a[i])%360] or h[i-1][(j+a[i])%360].This is a simple DP.

        And then,you can define g[j]=h[i][j],f[j]=h[i-1][j].The method of calculating is similar as below.When all of the g[j] were done,you can copy g to f,and use f to calculate h[i+1].At last,you can get h[n][0].

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

    47954506

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

How to solve G?

I came up with an idea that we can calculate the number of ways to choose k edge(s) from n-1 total edges, and for each way we calculate the number of the set of vertices which satisfies the condition(for every edge we chosen, there is at least one vertex(in the set) in both sides of the edge).

And that is the answer. Maybe can use DP on tree to solve it.

Because f(S)^k <--> choose k edge(s), that's equivalent.

Am I right?

sry for my poor English, wish you can understand me...

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

    My idea is similar but not same with yours.

    First we can use Stirling number to split power into several falling factorial，e.g

    f(S)^k=sum{i=1...k}S(k,i)f(S)_(i)，where x_(i)=x(x-1)...(x-i+1)=C(x,i)i!

    then we should compute sum C(f(S),i), for every 1<=i<=k.

    this is equivalent to choose i egdes and sum the number of sets valid(that means f(X) includes these edges).

    then we can DP with dp(i,j) means choose j edges in i's subtree, and each egde chosen has at least one node of its subtree in the vertex set. and then the answer is dp(1,i) minus unvalid ways, the latter is only possible when (j-1) edges are all in the other's subtree(and no vertex outside this subtree is in the set). you can enumerate the "highest" edge, and the ways of this can be easily gotten use dp values.

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

I think problem C somehow matches to 990C - Bracket Sequences Concatenation Problem of previous codeforces contest ....

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

Could someone mind explaining to me why this solution for problem E doesn't work?

My approach is the same as described in editorial, except that I remove from list the maximum between LIS and LDS.

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

    Unfortunately, that's just not efficient enough. That solution gives you sequences, but you need around .

    The key to the solution is that, if the LIS isn't long enough, we take the entire set of decreasing subsequences, not just the longest decreasing subsequence. Note that in general, repeatedly removing the longest/last decreasing subsequence doesn't give you the minimum cover: consider 3 0 4 2 1: you might want to take 3 2 1, but the only minimal cover is 3 0 and 4 2 1.

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

      Hmmm I'm still not fully sure I understand since at every single step I take the max between LIS and LDS, then shouldn't that mean that at least one of LDS or LIS should have size bigger K, for the case mentioned my code would work since if it takes 321 as LDS, then it would find 04 as LIS on the next step.

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

        I don't have a case on hand which breaks it. Unfortunately, it's not true that either the LDS or the LIS has size at least K: see the sequence 3 6 9 2 5 8 1 4 7: both the LIS and LDS have size 3, but K = 4.

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

          But in that case 3 is fine, because its length is 9, not 10 and 6 is doable in 3

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

            For N = 9, you need to solve it using 3 sequences. N = 6 only guarantees 3 additional sequences, so 9 — 3 = 6 isn't good enough.

            If you want a larger case, the corresponding sequence for N = 25 has a similar issue: you can only remove 5 vertices from 5 10 15 20 25 4 9 14 19 24 3 8 13 18 23 2 7 12 17 22 1 6 11 16 21

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

          So I get what you mean which is that in the worst case you will find that LIS and LDS are both sqrt(N), so its possible that there is some sequence where by taking sqrt(N) every time instead of sqrt(2*N) it will require more iterations :S

          It just seems very hard to find such case...

          I tried to find a test which breaks my solution so I ran a program which tested all 9! permutations for N=9 in my code and all of them passed with K<=3, so if there is a case that breaks it it's at least N=13...

          Also, do you have any idea on how you would demonstrate that the complexity of my proposed solution is 2*sqrt(N)? I did a this very simple code, and it plots approx 2*sqrt(N), but I don't know how to demonstrate it formally:

          function f(N) { // 10=> 4, 100=>16, 10000=>193, 1000000=>1990
  var ret=0;
  while(N) {
    N-=Math.ceil(Math.sqrt(N));
    ret++;
  }
  return ret;
}

          After adding the condition if len<K grab the decreasing sequences LCS generated my code passes.

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

            My submission failed on test 9, which had permutations of size ~25. Maybe try permutations like that?

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

Hey I need some explanation for problem D, how to calculate the DP states, otherwise the solution is understandable.

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

Can anyone explain in problem F Inclusion-exclusion. I don't understand the moment, that (i / x) is square-free.

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

Er

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

can anyone explain how to calculate dp[k][j]? I find it hard because dont we have to calculate gcd between dp[k][j] and p^j??

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

    ,because any t can be 0 ~ t with equal probability after an operation. You can notice that , so you can calculate it in O(α k).

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

May be this is my personal problem, but the value of k was misleading for me, if it was 106 imo it will be better. For this value of k I wrote dp solution without knowledge of multiplicative function and it was very close to tl (about 3s on maxtest). When I wasted a lot of time I finally wrote correct solution, but this is D on div1+div2, so such trap is not good.

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

    Actually I was a little afraid of having TLE even with correct solution. It was O(k log^2 n) with multiplications and modules. When I checked how long it takes on maxtest (2^something) it turned out it is quick, but it's not like k could have been increased significantly ... unless you would like to require binary exponentiation of matrices ;)

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

      Hm, actually complexity equals , not

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

        Ah yes, you're right. I mean, my code has log^2, but it is trivial to improve that, but I didn't realize since it was sufficient.

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

          I think if you calculate with it's , if you calculate with it's , isn't it?

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

In problem D, can someone please explain the recurrence of the DP.

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

Anyone knows of any other problem similar to problem D?

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

In problem F, I dont understand why operation 3 is bitiwse AND ?

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

    If you have A[i] and B[i] multiples of i, there will be A[i] * B[i] multiples of i after taking gcd of all pairs. Also, multiplication mod 2 is &.

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

Please link this editorial to contest.

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

Hint for G?

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

I wrote a tutorial of problem G. https://mirror.codeforces.com/blog/entry/64367

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

The first editorial is formatted so much better than the second. Thank you for both, though! :D

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

For problem E, how to guarantee this partition which calculates the smallest k

(Ah...I make a mistake, just forget the problem above

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

Perhaps irrelevant, but is there a sequence on OEIS for the term f(n) in problem E?

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

why in problem C, about brackets, answer is 2, but not 3?

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

    How would you pair up the strings? I can guarantee that you only find 2 pairs, therefore the answer is 2.

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

      like this one

      3 ((  )()) 1
5 ( ) 2
4 (( ) ) 6 7
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        "The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence."

        You are not allowed to combine 3 strings. So 4 6 7 is not valid.

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

      sorry, I think I got it,

      there it says pairs, then 3rd option is not valid

      Thanks for reply.

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

soon™

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

Why are the editorials not linked with questions nowadays?

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

Seriously, what is the record for the latest tutorial for some problem? We're close to three weeks now.

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

    Let me guess, Radewoosh is still enjoying the New Year, so he hasn't uploaded the editorial yet

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

In F,"instead of storing the parity of numbers equal to x, store the parity of numbers divisible by x." Is it divisible by X or divisors of X??

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

How can we solve this problem using Dynamic Programing, there is dp tag given to this problem. I am a beginner so could someone help me with this ....

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

I am 5 years late but in B you can bitmask from 0 to (2^n)/2-1 instead of 0 to 2^n-1. all combinations from (2^n)/2-1 to (2^n)-1 are the same as the combinations from 0 to (2^n)/2-1 just different signs

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

can anyone explain me how are we calculating how many brackets need to be added to left of right of a bracket sequence in problem C

→ Reply