praran26's blog

By praran26, 4 months ago, In English,
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...

Thanks to radoslav11 for nice and short editorial in comments.

Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code 1
Code 2
 
 
 
 
  • Vote: I like it  
  • +102
  • Vote: I do not like it  

»
4 months ago, # |
  Vote: I like it +23 Vote: I do not like it

dynamic programming everywhere

»
4 months ago, # |
Rev. 2   Vote: I like it +61 Vote: I do not like it

Alternate solution for E.

Notice that the differentiation idea gives .

This motivates the idea to write xk as a sum of polynomials x, x(x - 1), x(x - 1)(x - 2), ... and x(x - 1)... (x - k + 1).

The coefficients for this linear combination is known to be the Stirling Numbers of the Second Kind. (you can also just calculate them) So combine that to have a O(K2) solution.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I get the differentiation part, but after that, I'm loosing on x^k as a sum of polynomials and Stirling numbers. Can you elaborate a bit!

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

      If our goal was to solve for , we would be done by our first observation.

      However, we are to solve for .

      Therefore, it makes sense that we should try to write ik as a sum of i, i(i - 1), etc.

      After that, we can use our first observation to collect the sum quickly.

      About the part about Stirling Numbers, it isn't really needed (you can just calculate them directly) but it's the first equation in https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Generating_functions.

      Here, (x)k = x(x - 1)... (x - k + 1). Hope you understand now.

»
4 months ago, # |
  Vote: I like it +71 Vote: I do not like it

If you know at least something about convex hull trick and have some prewritten code of it than you can easily solve problem F in not more than 10 minutes. IMHO this problem is very straightforward.

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In Problem C P[j] = j-1 for i < j <= i+k-1 if I'm not wrong.

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

    Fixed. Thanks. :)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it -25 Vote: I do not like it

      You are given N , A , B find such x and y that (A*x + B*y) = N .

      If such x , y does not exist print -1 , either print x and y in same line separated by space , if there are multiple x , y that satisfy the equation print any of them .

      For example: If N=9 , A=2 , B=5

      then ans is 2 1 . Because 2*2+5*1=9 . Here A=2 , x=2 and B=5 , y=1 .

      Constraint:

      1<= N , A , B <= 10^18

      INPUT

      9 2 5

      22 3 7

      439365 78717 87873

      505383 77277 99291

      1000000 3 999997

      474441 99291 77277

      911106 51038 78188

      321361 79845 81826

      1000000000000000000 8765433 54343345

      OUTPUT

      2 1

      5 1

      0 5

      -1

      1 1

      4 1

      1 11

      3 1

      25359400 18397426840

      I have solved using linear loop .

      for(long long i=0; i<=n/a; i++)
              if((n-i*a)%b==0) {
                  printf("%lld %lld\n",i,(n-i*a)/b);
                  return 0;
              }
      
          printf("-1\n");

      But constraint is so big so this would not pass . For this test case n=1000000000000000000 , a=3 , b=798877665 code is getting TLE .

      How to solve this problem efficiently ? This is a subproblem of this problem http://codeforces.com/contest/932/problem/C

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E : (1 + x)^n = sum, the sum should start from 0, not from 1.

»
4 months ago, # |
  Vote: I like it +132 Vote: I do not like it

Another alternative solution for E:

Let's give xk a combinatorial meaning. xk is the number of combinations of picking k people from the subset with x people with repetition. For each subset we count all combinations and sum those.

Why not switch sums? For each combination we count the number of subsets in which the combination appears, and sum those. This obviously computes the same result.

Assume we have a combination of size k consisting of i distinct people. From which subsets can we construct this combination? Obviously the i people have to be in the subset, but for every other person we have two choices: he is in the subset or he isn't. It doesn't matter. Therefore there are 2n - i such subsets.

Let dp[j][i] be the number of combinations of size j with i distinct people, then the result is . dp[j][i] can be computed very easily with, you guess it, dynamic programming.

My submission: 35317193

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

    Hello Jakube. Can you tell me why this way is wrong[ Written the steps in the picture provided in the link] . And why step 4 in the picture is not the general solution?

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

      The differentials are wrong. You need to use the product rule!

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

        Thanks. I got the mistake now. By the way in your explanation how you are calculating dp[i][j]. I mean the recurrence formula you are using to calculate it how it equal to dp[i][j].

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

          Look in my submission. It is pretty basic: either the last element already appeared in the combination or it is new.

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

    could you tell me why is (j * dp[i-1][j] + (n-j+1) * dp[i-1][j-1])?what is the combinatorial meaning? thank a lot!!!

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

      To generate a combination with i elements from which j are distinct we have two options.

      • We can start with a combination with i - 1 elements from which j are distinct, and append an element that already appears in it. => j options to choose the new element => j * dp[i - 1][j].
      • We can start with a combination with i - 1 elements from which j - 1 are distinct, and append a new element that doesn't appear in the combination => n - (j - 1) possibilities to choose the new element => (n - j + 1) * dp[i - 1][j - 1].
      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        this part is clear now, but I dont understand how to deal with x^k yet

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

          xk are just a bunch of combinations. And each one of those I count independently. This way I don't have to use xk in any of my computations.

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

            How to count independently ? by a combination of size k consisting of i distinct people?

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

    A so nice approach Jakube. Thanks.

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

praran26 please answer this question::

It came to my mind during the contest, corrrect me please: I thought that the answer will be always P=[1 2 3 ... n] . Suppose x = min(A,B), so in x moves this permutation will always satisfy both function f and g.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    For your permutation, g(i) = 1 for all i. (Since x may not be 1, the permutation is wrong.)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain D in a bit more detail?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, if every node in the sequence is a descendants of its predecessor,can it be solved?

»
4 months ago, # |
Rev. 5   Vote: I like it +86 Vote: I do not like it

Another solution for problem E;

The last algebraic is easy for calculating.

»
4 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

( Sorry, my English is poor )

Another solution for E:

It can be proved (by mathematical induction) that ans(n, k) = 2n * fk(n), where fk(n) is a k-degree polynomial.

So we can use fk(0), fk(1)...fk(k) to calculate fk(n) with Lagrange interpolation method. ( Since we use consecutive integer as interpolation points, the interpolation will be very fast )

fk(0), fk(1)...fk(k) can be computed by simple O(k2) dp, or other O(k2) algorithms.

( But I got a WA on test 22, :( ) ( UPD: I forgot %mod somewhere :( )

»
4 months ago, # |
Rev. 2   Vote: I like it +37 Vote: I do not like it

Another (one more XD) solution for E:

The expression is

But you can also look at it as

Which is kinda alike the original expression but taking k-1 instead of k and "shifting" the coefficients.

Let dp(k, j) be , so k means the current power and j means "how much have we shifted", and since we cannot shift more than k times then there are O(k2) different states. Note that our answer is n*dp(k,1). We have the following recurrence:

And then we have dp(k, j) = (n - j).dp(k - 1, j + 1) + j.dp(k - 1, j). Our base case is k=0, since that .

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

    Very nice solution! I found the shifting idea first but couldn't make my DP work fast enough. I only had a O(k3) solution with O(k2) states. After that, I got the Stirling solution. It's nice to see that my failed approach could lead to such a wonderful solution :D

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain Convex Hull on Tree in Task F in more details? How do we add new lines to the ancestors? Also, is it possible not to sort lines in CVH? Because recently I saw a task where lines were not sorted, but in editorial it was written that we have to use Convex Hull trick. Thanks!

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

    You can use a set or linked list.When adding new lines,for set just insert,for linked list you need binary search.
    After inserted lines,check the precursors and succeeds to maintain the CVH.

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

      Sure, but how do we erase useless lines in the set when we add new lines?

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

F is solvable without the Merge Small to Large trick. We linearise the tree by Euler tour and then each subtree will represent a range in the tour. Then build a segment tree on it where each node will contain a CHT for the lines in its range. Initially the tree is empty, we can add lines on the go. Time complexity should be same.

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

Can someone tell what I am doing wrong in this approach in problem E. Please specify the step. Here is the link

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe I can't read english straight right now, but I'm really confused on D condition 2:

Every node in the sequence is an ancestor of its predecessor.

So... it's an ancestor of it's ancestor??? It's an ancestor of itself???

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

    I think they mean "Every next node in the sequence".

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

    If the sequence of nodes is denoted by {ai}, then ai + 1 is ancestor of ai.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice B, C, D — simple ideas for solutions was hidden under deterrent (a bit) statement.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sry for my noobness ;)

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

The tutorial of E is AWESOME!!!

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

Can someone elaborate more on problem D?

I am quite new to the concept of binary lifting and I believe more people are in my situation.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    Let's imagine you already have computed nxt[].

    Now for the binary lifting, you keep an array jump[u][i] which shows the vertex in which you will be if you do nxt[nxt[nxt[...nxt[u]...]]] exactly 2i times.

    Obviously jump[u][0] = nxt[u]. Well you can find that jump[u][i] = jump[jump[u][i - 1]][i - 1]. This way we can compute the jump values of a vertex in .

    In a similar way, we will store sum[u][i], which is the sum of weights of the vertices, on the nxt[] path of length 2i (without jump[u][i]).

    Now to answer the queries Let's find the highest ancestor in the jump array of vertex R, such that the sum on the path is less than or equal to X. This is obviously — we simply go through the array jump[R]. Lets call the cell which we found jump[R][j]. Now we add 2j to the answer, and remove sum[R][j]. We also move R to jump[R][j]. Well now we simply need to perform a query on these new R and X.

    Obviously the length of the query chain is at most , so the complexity for each query will become . You can notice that after each query the j decreases and achieve .

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it -13 Vote: I do not like it

You are given N , A , B find such x and y that (A*x + B*y) = N .

If such x , y does not exist print -1 , either print x and y in same line separated by space , if there are multiple x , y that satisfy the equation print any of them .

For example: If N=9 , A=2 , B=5

then ans is 2 1 . Because 2*2+5*1=9 . Here A=2 , x=2 and B=5 , y=1 .

Constraint:

1<= N , A , B <= 10^18

INPUT

9 2 5

22 3 7

439365 78717 87873

505383 77277 99291

1000000 3 999997

474441 99291 77277

911106 51038 78188

321361 79845 81826

1000000000000000000 8765433 54343345

OUTPUT

2 1

5 1

0 5

-1

1 1

4 1

1 11

3 1

25359400 18397426840

I have solved using linear loop .

for(long long i=0; i<=n/a; i++)
        if((n-i*a)%b==0) {
            printf("%lld %lld\n",i,(n-i*a)/b);
            return 0;
        }

    printf("-1\n");

But constraint is so big so this would not pass . For this test case n=1000000000000000000 , a=3 , b=798877665 code is getting TLE .

How to solve this problem efficiently ? This is a subproblem of this problem http://codeforces.com/contest/932/problem/C

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the following lines of problem C :

So, if there exists a solution (x, y) where x ≥ 0 and y ≥ 0, for Ax + By = N, we can in turn generate a permutation P satisfying our needs. Otherwise, no such permutation is possible.

So, now for any one of the solution (x, y), generate x cycles of length A, beginning from indices 1, A + 1, A * 2 + 1 ... A * (x - 1) + 1 and then beginning from indices A * x + 1, A * x + 1 + B, ... A * x + 1 + B * (y - 1), generate y cycles of length B.

Thanks!

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

    Anyways, I got it... We here are trying to break N into x parts of size A and y parts of size B.. IF this equals N then only solution is possible.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the code of problem B in more detail or suggest any related tutorial ?

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

    Let di = a1 + a2 + ... + ai (in other words, di = di - 1 + ai). Then, al + al + 1 + ... + ar = dr - dl - 1.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

RECURSIVE QUERIES And as 1 ≤ g(n) ≤ 9, using partial sum arrays for each possible value of g(n), we can answer the queries in O(1) explain this thing plzz how to use partial sum arrays and where did the author use this technique in its programme

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

    x[i][j] is the count of numbers between 1 and j such that the value of g is i. So, each query can be answered as x[k][r] - x[k][l - 1].

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

      did u actually use dp technique in your programme i am not able to see it

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

        No, it's not DP. Try running the code using pen/paper on some small test cases. That might help. You can learn more about partial sums here.

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

          then we can use bottom up dp for calculating g(n) for all the integers 1 ≤ n ≤ 10^6 in O(n).

          :/

          howz the time for calulating the g(n) is O(n).

          Let us consider

          n=200140
          
          then 1-> is n>10 true so,f(n)=8 (time taken to do this is O(width of no) that traversing the no form right to left)
          
          then 2-> 8>10 false return 8
          

          If i analyse this for running time complexity then it should be till the number not reduces to single digit every time (loop for non zero digit product calculation runs from right to left that is over whole width of the no)..

          Generally for any large number it no more then takes 4 to 5 compressions

          then my time taken (4 or 5)*(width of the newly arrived no every time till the ans returned by the f(n) is not a single digit)..

          How the time taken to find g(n) is O(n) here .. and n is the no So ur code want to say time is O(200140) if consider my case then plzz clear it !!

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

            It is time complexity to calculate g(i) for i ≤ n using DP.

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

          Is using the concept of partial sum with modification query better than using Segment Trees ?

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

For my submission http://codeforces.com/contest/932/submission/35328280 getting a wrong answer verdict, I have checked with the solution provided and not able to find any mistakes.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How would you go about solving A if you had to find the string of minimum length (which satisfies the given properties)?

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

    try to iterate over possible centers of the palindrome. In basic version it takes O(n) to verify and find answer for a center. But using hashing we can verify and find ans for center in O(logn). So we can solve it for 1e5 length also.
    Though there might be ways to get around hashing.

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

Can someone elaborate more on problem F?

The tutorial says that "Thus, convex hull trick of dp optimization can be used to find the minimum value. Once the value is calculated for a node, a line with slope b[i] and y-intercept dp[i] is added to the hull."

Does it mean that we treat every line as a point (b[i], dp[i]) and maintain the dynamic convex hull when we insert the point? If so, why?

THX.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how next[] array is calculated in problem D? I am not able to understand from editorial.

»
4 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I’m so sorry that I missed this post and the abundance of solutions to problem E, (possibly one of the greatest realizations of mathematics and computer science combined this year), so here I am with yet ANOTHER solution to problem E:

  1. Make the “educated guess” that the solution is of form ansn = 2n * P(n), where P(n) is a polynomial of degree at most k + 5 over ZMOD (the  + 5 part might be optimized out in future iterations, but let’s be honest to ourselves; we don’t care that much, do we?)

  2. Gather some small answers (i.e. by the brute-force technique) and interpolate to find P

Bonus: can you find how I managed to make the educated guess about the form of the solution?

Seriously now, since when did I start to get the notion that combinatorics and formula calculations are not what competitive programming’s all about?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it
    1. ans0 = 2n,  ans1 = n·2n - 1 — seems like a proof
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F. Weak tests. Solutions that take into account only 30 vertices deeper than current get AC. http://codeforces.com/contest/932/submission/35515087

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E didn't understand the part where b+c is a constant and that reduces the state space for implementation.Can anyone explain?.Thanks in advance.

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

another approach to E:

we can see that after each step of differentiation and multiplying it by 'x' we have the polynomial like xi * (1 + x)^(n - i). So, we can use normal differentiation rule for differentiating such polynomial and add it to the next step and after we have done we just put x = 1 and our answer is the sum of (2i * dp[k][i]) as xi = 1 for x = 1. here dp[k][j] denotes the co-efficient of the expression xi * (1 + x)^(n - i) after differentiating it k times.