ajit's blog

By ajit, history, 8 months ago, In English

We hope that you have enjoyed this round! Here is the sketch of solutions for the problems.

A. Array and Peaks

  • Problem Setter: ajit
  • Editorialist: ajit
Tutorial
Implementation in C++

B. AND Sequences

  • Problem Setter: ajit
  • Editorialist: ajit
Tutorial
Implementation in C++

C. Add One

Tutorial
Implementation in C++

D. GCD and MST

  • Problem Setter: ajit
  • Editorialist: ajit
Tutorial
Implementation in C++

E. Cost Equilibrium

Tutorial
Implementation in C++

F. Swapping Problem

Tutorial
Implementation1 in C++
Implementation2 in C++
 
 
 
 
  • Vote: I like it
  • +153
  • Vote: I do not like it

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

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

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

Thank you for the contest, I really enjoyed it.

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

In problem C, I faced lot of issues when I did not use fast input "ios_base::sync_with_stdio(false); cin.tie(NULL);"

112714905 — here I took input number as a string (to iterate over it's digits) and even when I used integers only (112715192) even then also, It got TLE verdict.

Has it become mandatory to use FAST I/O to pass the verdict now?

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

    I think it has already been a standard that you should always use fast IO.

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

Solved C by direct simulation with pre-processing

Basically just brute-force the numbers gotten when you add 1 to every digit starting from 0. The numbers can't be stored because they get large very quickly. To fix this, store the count of each digit in the current number in an array instead and update the array to the next number after applying the operation accordingly. The sum of digits of the current number(we only care about the sum) are stored in a vector for pre-processing. Then for each digit of n, apply the operation m times, which is done in O(1) because of pre-processing.

Total time Complexity: O(t*number of digits in n)

https://codeforces.com/contest/1513/submission/112728116

Lol, the updating can be done with only one array by updating backwards. Was too braindead to realize...

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

    Hi, I tried a similar solution, and as far I understand, I shouldn't be getting a TLE, but I still get one on test case 3, could you kindly tell me what is missing in this? https://codeforces.com/contest/1513/submission/112745133

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

      As I can see, you are are simulating the whole procedure in each test case. This would take at max (no. of test case)*(m) i.e., 4e10 (worst case) operations which would obviously give TLE. Instead store answer for each digit from 0....9 and for each value of m using simple DP, before the test cases and then access them in O(1) in each test case.

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

        Yeah, usually I consider each test case as an isolated environment. Thanks for the reply, I shall try it out.

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

          Think, If you have digit D and you want to increment it let's say X times then how much length it will increase. You can store it in table[D][X](Try to Precompute this table). If you don't get the solution, then you can see mine.

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

            Yeah, I tried it out, it worked, thanks for the input. But for some reason it still gives TLE without "ios_base::sync_with_stdio(false); cin.tie(NULL);"

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

      Because, you didn't pre-calculate the vector. Here, the vector stores number of digits for current number. Each particular digit of n expands till m steps. So, if I pre-calculate for m+(each digit of(n)), I can get access for each digit after m steps in O(1). Here maximum value of m is 200000 and maximum value of a digit can be 9. So, you pre-calculate vector for the number 0 to 200009.

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

F can be solved using an $$$O(n^2)$$$: 112699481.

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

    Could you explain your approach ?

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

      Well, do like the editorial solution, but in the last step just do a brute force loop and rely on auto-vectorization to cut your time down to just under TL.

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

    How did this pass the time limit?

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

In the explanation of Problem B, Why do bi needs to be super mask of b1?

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

    I'll explain my thought process maybe it will help you.

    When $$$i=1$$$ only $$$B_1$$$ will be on the left side. And when $$$i=n-1$$$ only $$$B_n$$$ will be on the right side. Therefore it's clear that $$$B_1=B_n$$$ condition must hold.

    For $$$2 \leqslant i \leqslant n-2$$$ there will be some mid elements on the left and some will be on the right. But in every case their bit-wise AND should be equal to $$$B_1$$$ (or $$$B_n$$$ as they are equal). TO keep the bit-wise AND constant,

    • $$$B_i$$$ needs to have all the set bits of $$$B_1$$$. If not the new AND will have some bits set to zero where it wasn't before.

    • What they have on other bits doesn't matter because in $$$B_i$$$ and $$$B_n$$$ those bits are set to zero and $$$B_1$$$ is always on left and $$$B_n$$$ is always on right. Thus their AND will be zero anyway

    This means that $$$B_i$$$ has to be a super mask of $$$B_1$$$

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

      Sorry I still don't get it.

      I understand why $$$B_i$$$ has to be a super mask of $$$B_1$$$.

      But why choosing two of the minimum of the array $$$a$$$, and the rest of the array will automatically meet the "super mask" requirements?

      For example, a = [2,4,2]. min(a) = 2(and count(2) >=2), but 4 & 2 != 2

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

        Oh, $$$B_1$$$ is not only the minimum one, but also should have $$$B_1 = B_1 and B_2...and B_n$$$. Got it. [2,4,2] simply can't find a proper $$$B_1$$$ in the first place.

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

          Could you explain , what does it mean that b1 must be super mask from all i =2 to n-1 . Oh , I got it from previous comments .

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

            Can you please explain what is a super mask I know about bitmask but first time I heard super mask

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

              I think super mask means that all the other b from i=2 to n-1 must have the bits sets which are set in b1.

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

              According to this editorial, I think "a is a SuperMask of b" means binary(a) should at least(counld be more) have the same 1s in the same digit of binary(b).

              Therefore, b & a will result in b.

              For example, 3(0011) is a supermask of 2(0010)

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

                Instead we can & every number with INT_MAX too.As it will have all the binary digits as one.

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

      Yes it really helped me. Thanks a lot!

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

    So that then only prefix and operation and suffix and operation for all i from 1 to n-1 will hold good , as long as those minimums are present at 1 and nth position

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

for question F:

i guess this is correct: first : let vc[i] = {b[i] — a[i], i}; second: sort vc; ans = sum = segma(llabs(vc[i].first)); third: enumerate vc[0].second whith i from 1 to n, let ans = min(ans, sum — diff); last : enumerate vc[n — 1].second whith i from 1 to n, let ans = min(ans, sum — diff);

it can pass all test, but i cannot prove it, who can give a prove?

submit code: https://codeforces.com/contest/1513/submission/112733065

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

Can someone tell me what is wrong in this submission for question B 112733641

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

Great contest.

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

In Editorial of D — why is checking if the new_element has edges enough to determine if a cycle will be formed?

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

    Hi, I have updated the solution slightly. Please have a look at it. We are spanning to left and right. Suppose we are currently spanning right and currently encountered a new_element which has an edge. First observation is that this edge is between new_element and an element with another index greater than it. Now what I meant is that, we will connect the edge between g and new_element and stop spanning in this direction (here right). This is because we just connected our current span group (current connected component) with some previous span group (another connected component) right? Any further entry we consider in this direction will form a cycle. You can have a look at the code for further understanding.

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

For problem C

I use A[i] to represent the occurrences times of number i. So we can construct anonther matrix B to represent the operation and we can multiply B m times to get the answer.

My problem is that can I improve the complexity which is O(t * 10^3)[10 is the size of B] because B is a sparse matrix.

The test code is https://codeforces.com/contest/1513/submission/112741598

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

    Probably a little late response — I did the same approach.

    Submission 115852637 is my Time Limit Exceeded on test 2.

    The simple fix was to first sort all the queries by $$$m$$$ increasingly, and update only by the power of difference (ie. keep the previous matrix power used in a variable and multiply by difference in $$$m$$$ between queries; in other words, if previous matrix was $$$P = M^{m_1}$$$ you just multiply it by $$$Q = P \cdot M^{m_2 - m_1}$$$). Lastly, just sort queries back to their original order and output the answer.

    Submission 115853823 is where I applied this optimization and it worked :D

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

Great contest with awesome problemsets.

Problem C just refreshed my memory of dynamic programming.

I solved problem C using two dimensional dp table using memoization approach.

My submission 112676785

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

    can you explain the recurrence relation?

    Isn't dp[i][5]=dp[i-1][4] true? Why is it dp[i-1][6]? pls explain

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

      dp[i][j] is defined as if we has number i and we apply exactly j moves than what is the total number of digits in the lastly generated digit.

      if i-1 is not 9 :

      than you can see that number of digits in(i-1)=number of digits in (i)

      so we can say that if i-1 is not 9 than applying one operation does not increase number of digits

      this implies dp[i-1][j]=dp[i][j-1]

      applying above thing dp[i-1][6]=dp[i][5] if i-1 is not 9

      and dp[i][5]=dp[i+1][6] if i is not 9

      so this clearly answers your query that dp[i][5] isn't dp[i-1][4] and dp[i][5]=dp[i-1][6] with constraints on values of i.

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

My understanding for F:
1. Plot all A_i and B_i on a number line.
2. If A_i < B_i, write a right arrow A_i -> B_i.
3. If A_i > B_i, write a left arrow B_i <- A_i.
4. The answer is original_answer — 2*(the maximum length of overlapping two opposite direction arrows).
(Continue to the editorial)

By the way, thanks for the great contest!

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

    Thanks for the visualization. Can you suggest me where I can read the algorithm to find the maximum overlap length given left_arrows vector and right_arrows vector of pairs.

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

...

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

In problem E, how to prove that array will be balanced when this condition holds true:

All the source vertices are before the sink vertices in the permutation

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

    I would also like to see prove that there aren't any other conditions.

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    I accidently found the proof when I was trying to prove it wrong. So here it is:
    Lets denote $$$U_i$$$ as some value needed at some sink and $$$V_j$$$ as some extra value we can take from some source. Lets say positions of sinks are $$$x_1, x_2, ..., x_m$$$ and positions of sources are $$$y_1, y_2, ..., y_n$$$. Lets say $$$y_j > x_i$$$ for $$$1<=i<=m$$$ and $$$1<=j<=n$$$. Lets denote $$$w_{ij}$$$ as some value we take from some source $$$i$$$ and give it to some sink $$$j$$$. So,
    $$$cost = y_1*(w_{11}+w_{12}+...+w_{1m}) - x_1*w_{11} - x_2*w_{12} - ... - x_m*w_{1m} + $$$
    $$$ y_2*(w_{21}+w_{22}+...+w_{2m}) - x_1*w_{21} - x_2*w_{22} - ... - x_m*w_{2m} + $$$
    $$$.$$$
    $$$.$$$
    $$$.$$$
    $$$y_n*(w_{n1}+w_{n2}+...+w_{nm}) - x_1*w_{n1} - x_2*w_{n2} - ... - x_m*w_{nm}$$$

    Now $$$V_a = w_{a1}+w_{a2}+...+w_{am}$$$,

    So
    $$$cost = y_1*V_1 - x_1*w_{11} - x_2*w_{12} - ... - x_m*w_{1m} + $$$
    $$$ y_2*V_2 - x_1*w_{21} - x_2*w_{22} - ... - x_m*w_{2m} + $$$
    $$$.$$$
    $$$.$$$
    $$$.$$$
    $$$y_n*V_n - x_1*w_{n1} - x_2*w_{n2} - ... - x_m*w_{nm}$$$

    And $$$U_b = w_{1b}+w_{2b}+...+w_{nb}$$$,

    So finally,
    $$$cost = y_1*V_1 + y_2*V_2 + ... + y_n*V_n - x_1*U_1 - x_2*U_2 - ... - x_m*U_m$$$

    Now, we can see that cost doesn't depend on $$$w_{ij}$$$ for any $$$i$$$ and $$$j$$$. So cost is constant no matter how we transfer values from sources to sinks. Hence proved.

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

      Thanks for the detailed proof! However, I think this covers only one part of the problem, i.e. proving that sinks-after-sources or sources-after-sinks will always have a unique cost. Can you formally prove that permutations other than sinks-after-sources/sources-after-sinks will never have a unique cost? I could only come up with a very informal, rather intuitive proof.

      I feel this should have been covered in the editorial itself, instead of plainly writing down the formulae. On another note, shout-out to liouzhou_101's amazing, detailed af editorial of Round #700's Problem D/B1.

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

        First we come up with a conjecture, then we try different examples so the conjecture is not wrong and then we move to the proof. So if you can think of an example to prove it wrong then you don't need to prove.

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

      Very Nice Mathematical proof!!

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

PermutationForces

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

WIERD CONTEST !

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

Would someone mind to explain to me why my submission for C got TLE? Its time complexity is O(10 * m), so I thought it would pass under 1 second. My submission 112747375

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

    Indeed complexity is $$$O(10 * m)$$$. But there are $$$2 * 10^5$$$ test cases as well. So, final complexity is

    $$$O(10 * m) * 2 * 10 ^ 5$$$

    which will surely TLE

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

      My bad, I thought the sum of m over all test cases does not exceed 2e5. This time there is no this line, thank you for pointing it out xD

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

length would be the sum of i−9 operations and i−10 operations, why? Problem C

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

    If you look carefully every single digit from "1 to 8" produce one new digit after 10 moves, expect "9" which produce two new digits. Thus, number of digits doubles up after 10 moves, if they don't have "9" in it... we need to add the digits contributed by "9", this is easy, number of 9 in number $$$x$$$ $$$=$$$ total no of digits in $$$x + 1$$$ — total no of digits in $$$x$$$

    $$$dp[i] = 2 * dp[i - 10] + dp[i - 9] - dp[i - 10]$$$

    which is equals to

    $$$dp[i] = dp[i - 10] + dp[i - 9]$$$

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

      also can you please explain why dp[i] is taken as the length to the operation applied to number '10'?why are we considering only 10?

      I got it.Thanks :)

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

        Can you explain what you got? I still find it a bit hard to understand.

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

Problem C can be solved Using a Simple 2D DP

where DP[digit][times] indicate the length of digit after times number of operations and digit E (0, 9)

and the answer for a query like 1057 16 would be dp[1][16] + dp[0][16] + dp[5][16] + dp[7][16] and take MODULO'S AS NEEDED

heres the code https://codeforces.com/contest/1513/submission/112697582

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

    That is one of the cleanest dp approach one can think of. Definitely beats the editorial.

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

    Way better than the editorial which has no explanation.

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

    your dp approach is easy to visualize as compared to the editorial's thanks for sharing :)

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

    can you explain the recurrence relation?

    Isn't dp[i][5]=dp[i-1][4] true? Why is it dp[i-1][6]? pls explain

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

      Please provide some information as to where you got that dp.

      Its not in my code

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

    Can be converted to 1D dp as each digit can be brought up to 10. So, just calculate for dp[10][times]

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

      Can you explain how the dp relation i-9 and i-10 for dp[i] as in editorial.

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

    Hey, your solution is great. Can you elaborate more on the last else statement when we are dividing $$$N$$$ in $$$0$$$ and $$$1$$$ .
    Is it due to the fact that we are calculating dp from small digits to the large, As at that time we would have already calculated dp for smaller no. ?
    Like if we say we take $$$N = 11$$$ or more.. then its not gonna divide in 1 and 0. I think, got the intiution. But can you confirm the above logic ?

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

      thats because of this if n==8 then in next step it only becomes 9 hence dp[n][times] = dp[n+1][times-1]

      but for n==9 it becomes 10 (1 and 0) hence dp[1][times-1] + dp[0][times-1]

      observe how after 9 dfs now solves for dfs(1, times-1) and dfs(0, times-1) so dfs(n, times) n would only be from 0 to 9 and would never exceed 9 and hence no need to solve for n==10 and n==11 as these are non existent.

      cheers

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

    absolute beauty , same approach just missed % mod to add , thanks dude!!!

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

    broooo that was neat!!!

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

length would be the sum of i−9 operations and i−10 operations, why? Problem C

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

Problem b : Please could someone explain this ? Now AND_pref2≤AND_pref1=AND_suf2≤AND_suf3.

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

    eg 5 3 . . . . . then AND_pref2 = 1 and AND_pref1 = 5 . generally it means by taking and operation you'r AND_pref will decrease(same for AND_suf) and for every i if it is valid permu then it would be equal.

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

Can someone explain what does overlapping of segments i and j means in F?

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

My idea for problem B:
So we have to find some elements that we can put at start & end. We will check something for all elements bit by bit. Let's say we have a set which contains potential candidates for start & end and we have to remove some candidates. And we are checking for $$$kth$$$ bit. There are three cases possible:
1. All elements have $$$kth$$$ bit set.
2. All elements have $$$kth$$$ bit unset.
3. Some elements have $$$kth$$$ bit set and some have unset.
Now for case 1 & 2, we have to do nothing. And for case 3, we can see that we can't let the first element of permutation have $$$kth$$$ bit set and similarly for last element. So we will remove all the candidates which have $$$kth$$$ bit set. We will do this for all the bits. Note that we have all the elements from $$$1$$$ to $$$n$$$ in our set initially. After doing this for every bit, lets say size of our set is $$$x$$$.
So, for choosing and permuting first & last element we have C(x,2)*2 ways. And permuting the remaining elements will give us (n-2)! ways. So total ways: C(x,2)*2*(n-2)!
My submission

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

    So can we say that , the minimum element of the array would be the best choice for first and last position because in many solution I have seen that they are finding the minimum element .

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

deleted Thank you

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

https://codeforces.com/contest/1513/submission/112755031

this code for problem C gives time limit exceed and can not figure out why? can any one please check!!!!

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

it lookes like codechef helped our problem maker. lol

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

Ignore.

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

In problem E "ways filling (n−src−snk) identical values in (src+snk+1) places)" should be equal to Binomail(src+snk+1,n-src-snk). But it is getting me wrong answer but when i use Binomial(n,src+snk) my got accepted. Can anybody explain?

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

    Checkout the formula for different ways to put K identical balls in N non-identical boxes.

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

The complexity of E should be O(nlogn) because of when we count the frequencies of every number cost us nlogn times(using the STL map or just sort).

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

This is an easy solution for B s1=s2&s3&s4&s5, ----------- (eq-1) s1&s2=s3&s4&s5, s1&s2&s3=s4&s5, s1&s2&s3&s4=s5. These are the condition for a Array to which is valid,so from equation one if s1=s2&s3&s4&s5 therefore s1=s2&s3&s4&s5=s1&s2&s3&s4&s5; So by taking AND of the elements in the array we get some value 'X'. If there is no or one 'X' present in the array then output 0. Now count the total number of 'X' present in the array and select two of them and also we can arrange them so we get xC2*2! and now we selected and arranged both the corners we are remaining with total (n-2) elements and we can arrange them (n-2)! so our final answer will become

x=number of element X n=total number of elements

xC2*2!*(n-2)!

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

In problem C, why is the dp recurrence not dp[i][j]=dp[i-1][j-1] if j is not 9 and why is it dp[i-1][j+1] for digits upto 8? This is really confusing me.

Question only for those who solved this using dp[MAX][10] way. pls help

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

Guys, What does super mask means??

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

    Assume that there are two numbers A and B such that B is a submask of A. Then in such case A is a supermask of B.

    Generally speaking, a supermask of a number is a number of which current one is a submask.

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

simple solution for problem D

this is what i have done
Maintain a list of edges with there weight

first push n-1 edges between neighboring nodes
(For Ex) a1 a2 s3 a4 (given array)
then push (1,2,p) (2,3,p) (3,4,p) in our edges, where first 2 numbers are indices and last one is weight

the observation is GCD(in a range) == min (in a range)
if an only if min divides every other value in the range

For example say one of the subarray is this
9 6 3 3 9 6 array
1 2 3 4 5 6 ind
then min is 3 and it divides every element
so push(3,1,3) ## here 3 is the index of element 3 and 1 is index of 9 and last 3 is (gcd weight)
and push(3,2,3) (3,4,3) (3,5,3) (3,6,3)
what my code would do is push them in 2 iterations in forward iteration push (3,4,3) (3,5,3) and (3,6,3) and in backward iteration push the rest

Originally u had n-1 edges this forward and backward iteration may push 2*(n-1) edges more so total 3*(n-1) edges<br?

now since u have O(n) edges apply any Min Spanning Tree algorithm

cheers

https://codeforces.com/contest/1513/submission/112722912

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

I can't understand why the number of edges considered in problem D would be O(N) ? We are also rejecting the edges forming a cycle which takes O(1) time with DSU. Can somebody please help me understand.

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

    So are you referring to my code.

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

    since total edges already there is n-1 then in 2 (forward and backward iterations i at most push (n-1)edges in each iteration)

    total 3*(n-1) which is O(n) edges for cases like
    10 10 10 10 10 (array) (total edges will be 3*(5-1) i guess)
    u can simply print edg to verify

    now Coming to DSU Part Just Search Minimum Spanning Tree algorithm based on UnionFind on youtube.

    I hope this clears it.

»
8 months ago, # |
  Vote: I like it -19 Vote: I do not like it

Simple Solution Problem B

What is asked in the problem is this
Count all permutation such that binary and of any prefix would match the binary and of remaining suffix

For Example
Say array elements are A1 A2 A3 A4 A5 A6 A7
so lets say one of the prefix is A1 A2 A3
then A1 & A2 & A3 must equal A4 & A5 & A6 & A7
this must be true for all prefix and resulting suffix with length greater than 1

lets just call them prefAnd and SuffAnd
since prefAnd == SuffAnd
Therefore prefAnd & SuffAnd == prefAnd == SuffAnd since and of 2 same numbers is the same number
but prefAnd & SuffAnd == FUllArrayAnd

so just find the all array and; say this comes out to be A

now every permutation must begin and end with A

since there can be prefix of size 1 and this must equal prefAnd == A
similary there can be a prefix of size (n-1) leaving suffix of size 1 and this has and values as SuffAnd == A

now you can show that any arrangement in the middle cannot affect any prefAnd and SuffAnd

For Example given array 1, 3, 5, 1
whole array and is 1 and hence it should always begin and end in 1
and middle part can be juggled as you wish giving (n-2)! for the mid

Proof of why the prefAnd wouldn't change observe any prefAnd >= wholeArrayAnd (since a&b <= min(a,b) and just generalise this by taking more numbers)
NOTE: WHOLE ARRAY AND IS THE SMALLEST NUMBER IN THE ARRAY (IF NOT PRINT(-1)) WE WILL USE THIS FACT LATER.

observe only 1&1 yield rest (0&1 0&0 1&0) yield zero
lets look at our example
001 (1)
011 (3)
101 (5)
001 (1)
001 (whole array and) (observe if ith bit is on here then it is on in every number)
so all the numbers have atleat all the bits on as in (A or wholeArrayAnd)

now suppose 1 3 1 5 is given
we arrange 1 number as 1
1 _ _ _
now suppose we put 5
then 1&5 will always be (A == 1 == wholeArrayAnd)

since both 1 and 5 will have all the bits open as in wholeArrayAnd the And will atleast be WholeArrayAnd or A
so FirstElement & SecondElement >= WholeArrayAnd (Eq 1. )

again since a&b <= min(a, b)
so (FirstElement & SecondElement) <= min(FirstElement, SecondElement) = FirstElement = WholeArrayAnd
(Eq. 2)
(since FirstElement == WholeArrayAnd and WholeArrayAnd is the smallest)

from equation 1 and 2 we have FirstElement & SecondElement = FirstElement
so that does it for any 2 elements at the beginning

for 3 elements just replace the first 2 elements by their binary and which again is FirstElement as shown and case of 3 elements at the beginning will be the same as case of 2 elements.

Here you go prefAnd would never change irrespective of arrangement in the middle.

if Prefand doesnt change then suffAnd wouldn't change either as wholeArrayAnd is constant.

so arrange at begging and end is C(A, 2)*2 (multiply by 2 since we are arranging indices and not element values) and middle permuation will be (n-2)!

Answer is 2*(A,2)*(n-2)! % MOD;

cheers

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

    Here is my code

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

    Don't know why you got so heavily downvoted. Your explanation was very clear!

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

Please help regarding my submission of problem c.. my submission is https://codeforces.com/contest/1513/submission/112704547 looking at the time complexity it looks fine to me... please explain if any changes are required

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    ios_base::sync_with_stdio();
    

    Maybe you mean:

    ios_base::sync_with_stdio(0);
    

    Actually the first one is as same as none. It got TLE because of slow IO.

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

      Man... I am very very thankful for your response.. Thank u for ur time to give a read to my code... that it why I always took a couple of milliseconds every time even after adding this... It was indeed my learning of the day... Wish u will always reach new heights and many more achievements are underlying in your way..

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

I did really bad during the contest.

I got wrong attempts in every problem of the first three ones, and I did't solve D in the contest.

IMG_2268.png

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

    PS: It's my hair which dropped during the contest.

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

Problem D is just amazing. Tried something with 3 segment trees, binary search and lazy propagation but did not work out. The solution idea in the editorial is really cool. I wonder how you thought about such a problem idea xD.

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

    Yes, Very Good application of the Krushkal Algorithm.

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

    Hey can you elaborate on the editorial? I am still trying to upsolve this.

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

    I had the same idea and managed to implement it during the contest (Instead of 3 segment trees, I used 2 sparse tables and 1 segment tree) Code

    I felt really stupid after reading the editorial xD and felt I did a really big overkill

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

For $$$D$$$, why does the following approach give wrong answer
1. Join $$$i$$$ and $$$i - 1$$$ with edge weight of $$$p$$$ for all $$$2 \leq i \leq n$$$
2. Pick up the minimum unvisited element, call it $$$minVal$$$ at $$$minIndex$$$. Start from this value and do dfs to the neighbours if and only if they are multiples of $$$minVal$$$. Connect $$$minIndex$$$ to this vertex, with edge weight $$$minVal$$$. Repeat for the next unvisited minimum
Now, run "kruskal-algorithm" on this graph to find the minimum spanning tree. Here is my submission

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

Such a pathetic way to write problem description for Problem B.

»
8 months ago, # |
Rev. 6   Vote: I like it +14 Vote: I do not like it

I find a different way of problem C, link it to Pascal triangle, but unable to implement it, my submission failed testcase n = 98, m = 100, see the picture of my approach and the wa submission : https://codeforces.com/contest/1513/submission/112781701 . I would appreciate it if anyone could help! 714C.jpg

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

Problem E was really fun to solve! Thank you.

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

In problem E, can somebody prove the 3 and 4 or explain why these conditions are sufficient ?

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

For problem E, shouldn't it be $$$Binomial(n, src + snk)$$$ in the third to last line of the editorial? (Since we are using stars and bars basically?)

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

Can anyone please explain (cnt⋅(cnt−1)⋅(n−2)!)%(109+7). Why do we have to do this?

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

    It's the number of ways to choose 2 elements among those who have minimal value which need to be at the start and the end of the array multiplied by the permutation of the other $$$n - 2$$$ elements. In other terms, we're doing: $$$Binomial(cnt, 2) * 2 * (n - 2)!$$$, where $$$cnt$$$ is the frequency of the smallest element.

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

      Ohk got it. Thanks.

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

      please explain a sample case suppose 1 3 5 1 of problem b thoroughly. How and What will be the permutations satisfying the condition.

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

nice contest.

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

in editorial of problem E how did we get C=(# ways filling (n−src−snk) identical values in (src+snk+1) places) = Binomial(n,src+src) could someone explain or elaborate?

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

    See bars and stars:

    To place N identical values into K places (with potentially multiple items in each place), you think of it as partitioning the N items into K places using K-1 partitions. So think of placing N items along with (K-1) partitions down in a row, which is N+K-1 total things. You'll choose the spots of the K-1 partitions, and there is: Binomial(N+K-1, K-1) ways to do it.

    Then plug in N = n-src-snk, and K=src+snk+1

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

Can anyone explain a sample case suppose 1 3 5 1 of problem b thoroughly. How and What will be the permutations.

»
7 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Alternative solution for 1513F - Задача об обмене: let $$$i$$$, $$$j$$$ be the indices of the swapped elements. Fix the signs of $$$a_i - b_j$$$ and $$$a_j - b_i$$$. With a merge sort tree (or a BIT of vectors), you can find, for each choice of the signs and for each $$$i$$$, the valid $$$j$$$ and, among them, the optimal one (the one that maximizes $$$|a_i - b_i| + |a_j - b_j| - |a_i - b_j| - |a_j - b_i|$$$). Complexity: $$$O(n \log^2(n))$$$.
113102167

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

what is super mask, in tutorial for problem B

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

plz someone help me understand the approach of problem D, that when we find a cycle we don't need to proceed further?

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

Problem C can probably be in O(logm) time. It is matrix powers.

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

I am getting TLE in problem c: add one. can anyone tell where im getting it wrong? 113394660


#include<bits/stdc++.h> using namespace std; typedef long int li; typedef unsigned long int uli; typedef long long int lli; typedef unsigned long long int ulli; #define MOD 1000000007 #define MP make_pair #define PB push_back typedef pair<int, int> PII; typedef vector<int> VI; typedef vector<string> VS; typedef vector<PII> VII; typedef vector<VI> VVI; typedef map<int,int> MPII; typedef set<int> SETI; typedef multiset<int> MSETI; int arr[200005]; int main(){ lli t; cin>>t; while(t--){ int m,n; cin>>n>>m; lli res=0; for(int i=0;i<=9;i++) arr[i]=1; for(int i=10;i<m+20;i++){ arr[i]= arr[i-10]+arr[i-9]; arr[i]%= MOD; } while(n>0){ res+= arr[m+(n%10)]; n/=10; } cout<<res% MOD<<endl; } }
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For every test_case you are pre — calculating your arr , take the upper limit of M precalculate it once store the answer and answer queries in o(n);

    Here is my submission 114217490

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

While trying to hack solutions in 1513F - Задача об обмене, I got a number of unexpected verdicts. From what I understand, it happens when the problem authors' solutions are inconsistent.

Can problem setters please resolve that? Thanks in advance.

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

I have not found error in my logic. 1. i+10=(i+1)(i) [in decimal format, for i=0 to 9] and digit number becomes 2 times 2. for the rest add the number of ~~~~~

include<bits/stdc++.h>

using namespace std; void sum(long long a,long long n,long long arr[],long long digit){ long long i; if(n>9){ for(i=0;i<10;i++){ arr[(i+1)%9]+=arr[i]; } sum(a,n-10,arr,2*digit); } else{ for(i=0;i<10;i++){ if((i+n)>9) digit+=arr[i]; } cout<<digit<<endl; }

} int main(){ long long t,a,n; long long i; cin>>t; while(t--){ cin>>a>>n; long long arr[10]={0},digit=0; do{ arr[a%10]+=1; a/=10; digit++; } while(a); sum(a,n,arr,digit); } return 0; } ~~~~~

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

In problem E, in the first example with array $$$[1,2,3]$$$ the notes say the total cost must be 2, but consider the following transformations:

$$$ [1,2,3] \stackrel{3\rightarrow2,x=2}{\rightarrow} [1,4,1] \stackrel{2\rightarrow1,x=2}{\rightarrow} [3,2,1] \stackrel{1\rightarrow3,x=1}{\rightarrow} [2,2,2] $$$

The total cost is $$$6$$$ ($$$2$$$ for each step) and as far as I can tell I followed the rules. Am I missing something?

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

My idea for D was exactly the same as Editorial's. Somehow I failed 3rd test case and couldn't figure out why.

Please help. Code

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

    Hey, did you find the bug ? I had the same idea for this and my implementation even resembles yours. My Submission

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

      Unfortunately, I couldn't figure it out. If you do, please let me know.

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

    One of my friends was having the same difficulty and their output was same as yours.

    We found a case —

    1

    4 75

    6 30 5 2

    Correct output — 86

    The mistake was not visiting 30 again as it was already visited before by 5.

    However, I checked your latest code and it gives the right output for this case, but a mistake I found in it was that you were not marking done for the current element, what I mean is that you should do done[index] = true as well, since it can give you wrong output in case of elements having same value as an edge can be counted multiple times.

    I hope I explained well what I meant to say. Hope this helps!

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

i was just reading the editorial for problem C-Add one it was hard to understand but it is such a beautiful solution after u understand it i wanted to write it out

so for all the numbers for 0 to 9 in n we can take it to 10 if (10-s[i])<m otherwise this digit would not contribute to increasing the number of digits which gives the final formula

now our problem remains to count number of digits whenm-(10-s[i]) operations are applied to 10 for this . lets see for any number lets say 123419 we apply 10 operations the numeber of digits will be double plus as 9 will become 109 so dp[i]=2*dp[i-10]+number of 9's in the number (i-10) operations

now to calculate number of 9's in i-10 using dp[i-9]-dp[i-10] because in one operation from i-10 to i-9 all the digits that increase would just be due to the 9s in number thats is there after i-10 operations

hence dp[i]=2*dp[i-10]+dp[i-9]-dp[i-10]=dp[i-10]+dp[i-9]

which i think can be a general expression for any number not just i th operation on 10 if we set base case right

this is my understanding uptil now please tell if there is something worng about it

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

Hi, how the last number in test case 1 2116 not 6 ??

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

Problem: A.array and peaks { if(!ans[i]) ans[i]=cur++; }

I didn't get the "if(!ans[i])" what does this mean ?