kartel's blog

Codeforces Round #861 (Div. 2) Разбор
By kartel, history, 19 months ago, translation, In English

1808A - Lucky Numbers

Solution

1808B - Playing in a Casino

Solution

1808C - Unlucky Numbers

Solution

1808D - Petya, Petya, Petr, and Palindromes

Solution

1808E1 - Minibuses on Venus (easy version)

Solution

1808E2 - Minibuses on Venus (medium version)

Solution

1808E3 - Minibuses on Venus (hard version)

Solution
  • Vote: I like it
  • +62
  • Vote: I do not like it

Comments Comments (57)
| Write comment?
»
19 months ago, # |
  Vote: I like it +26 Vote: I do not like it

I liked the problems and the contest overall. The beautiful illustrations were the cherry on top !!!

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +46 Vote: I do not like it

E2,I cannot understand why multiplication is O(lognk^3).For each fixed sum S,we need to recalculate the matrix.why is not O(lognk^4)?

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

    I had the same doubt (indeed Matrix exponentiation TLE's). If you look closely, we don't really need a k*k matrix, all we need is a k*1 vector. Notice the nature of the transitions:

    dp[i+1][j+k]+= dp[i][j]*g[k].

    Where g[k] = 1 if the digit k is allowed for the value of S that we fixed.

    So, all we need is g^n.

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

      Sorry if this is dumb, but how to do g^n on a vector?

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

      This is more like convolution. How can we do the convolution using the matrix?

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

    the $$$g$$$ for different $$$S$$$ could be the same, if we change the $$$f[0]$$$ for fixed $$$S$$$.
    thus we could calculate the $$$g^n$$$ once, and calculate $$$f(s)[0] * g^n$$$ for k times.

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

      E1 for different S,we have different y that we can't use,so the transition matrix is not the same,i think.

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

    So does anyone have a explanation for this question now? I'm still confused.

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

      May be you can get g Matrix at first because g Matrix is the same for any i.

      And then,for each question you just need to calculate f with O(k^2logk) because f is a vector

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

        Oh,sorry,maybe I'm wrong

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

          Maybe what you need is just a vector.Because for any remainder ($$$mod$$$ $$$k$$$) the transfer is the same,so you just use a vector times another vector which just use $$$O(n^2logn)$$$

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

C is also solvable with Digit DP!

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

    Here is a bit clean code with digit dp idea —

    Submission

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

      Can you explain the approach?

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

        We use the standard digit dp approach to enumerate all numbers from [l,r] (l = n,r = m in code). There are 3 additional variables that I have used in the recursion code (greater , smaller, curr). Here,

        greater = greatest digit used so far in recursion.

        smaller = smallest digit used so far in recursion.

        curr = number formed finally after using different digits in recursion. (in string format).

        every time we reach the end of recursion (index == b.size() see in code), we have to update our answer if and only if difference between greater and smaller is lesser than what we have encountered so far.

        Now, in the input it is not guaranteed that l,r have same digits. So, we have to put some zeroes in the starting of number l to make number of digits (l) == number of digits (r).

        There was just one edge case I missed when I first implemented the code — You cannot update smaller variable in recursion till you encounter the first non zero digit in number l. This is because we have appended zeroes for our own implementation and it was not given in the original problem.

        Hence you can see this line in the code which handles the case discussed above —

        (idx < flag ? smaller : min(smaller,i))

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

          Very great explanation, it allows me to understand a lot!

          I just wanted to add that when the lower bound and the higher bound are both negative, we can complete the number with the first digit of l and in this case the memoization is not necessary.

          Also just to simplify, in my implementation when the two numbers l and r don't have the same size, I just use a string of 9 digits with the length of l.

          Submission

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

          I dont know why memoisation should work here , since we are changing the curr after ever operation , what is the subproblem here ? Can you explain what exactly is the subproblem here ?

          → Reply
»
19 months ago, # |
  Vote: I like it +69 Vote: I do not like it

ans of E is

$$$ \left\{\begin{align}k^n-\left[(k - 1)^n + (-1)^n\left(gcd(n + k - 2, k) - 1\right)\right],\ k\ is\ odd\\ \frac{k^n}2-2^{n - 1}\left[(k/2-1)^n+(-1)^n(gcd(n + k / 2 - 2, k / 2) - 1)\right],\ k\ is\ even \end{align}\right. $$$
→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

https://codeforces.net/contest/1808/submission/199905893

Problem C I tried to solve with simple maths but idk why getting Wrong Ans in TC7 (158 case).Is there any corner case?

I have added my approach :

Approach:

First im checking whether l and r of same length (cnt1 and cnt2)

a) in case they are nothing for ex say 12 and 113 then answer is simple 10^cnt1 -1 (99 in this case)

b) in case they are of same length then we traverse from right to left( in v1 ,v2 vectors we store digits of l and r from right to left) Till we get their first point of difference

b1) if there is no diff ie l and r are same we print l

b2) suppose there is difference at index i. So we keep a track of maxi,mini of digits till i-1 and these digits will surely be in ans. Suppose at index i, l has digit a and r has digit b . then the value at index i can move from [a,b]

So I made a for loop from a to b: In case I =a ,we have to make sure than maxi doesnt increment else diff may be inc. So suppose we keep

276___ say 6 is a If we get any digit less than maxi till index i, All the next digits can be madi Suppose l = 276134 So in this case we will store the val 276777 And compute min diff

Else if digit is greater than or equal to maxi we will move with same digits (I=2 and a=6) Suppose l= 276814 So corresponding no will be 276888. Now compute maxi-mini and check.

If I= b ,same reverse logic for I=a,

Else if i b/w a and b , keep all the digits from point of difference as i

So for I>=a and I<=b find min diff and print

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

    "Else if digit is greater than or equal to maxi we will move with same digits (I=2 and a=6) Suppose l= 276814 So corresponding no will be 276888. Now compute maxi-mini and check."

    what if the number is l = 123456789, and we are checking 1234_____.
    we wont be able to use 123455555.

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

Can someone please explain D in simpler way?

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

D: For every index $$$i$$$, let's see all such indexes $$$j$$$, that there is exists such subarray of $$$a$$$ $$$[l; r]$$$ of size $$$k$$$, that $$$i$$$ — $$$l$$$ = $$$r$$$ — $$$j$$$; for index $$$i$$$ let's call all such positions $$$j$$$ good.

We can see, that for all odd $$$i$$$ good positions are odd too, for all even $$$i$$$ good positions are even.

For every index $$$i$$$ we have to count $$$z$$$ = number of non-equal to $$$a_i$$$ elements on good positions, to do this we can count $$$x$$$ = number of good positions and $$$y$$$ = number of equal to $$$a_i$$$ elements on good positions, $$$z$$$ = $$$x$$$ — $$$y$$$.

Let's build two Merge Sort Trees, one for elements on odd indexes and one for elements on even indexes.

The number of good positions is just some simple math, the number of equal to $$$a_i$$$ elements on good positions is just one Merge Sort Tree query (if $$$i$$$ is odd, query to first MST, otherwise to the second).

Answer is (sum of all $$$z$$$ for all $$$i$$$) / $$$2$$$.

Time complexity: $$$O(n$$$ * $$$log$$$ ^ $$$2)$$$.

My solution: 199667931

→ Reply
»
19 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Is the total time complexity of E2's solution O($$$k^4logn$$$)?(for each sum from 0 to k-1 there's a O($$$k^3logn$$$))

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

For problem A, there's a solution using sparse table if you couldn't get the observation like me. 199925584

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

can somebody explain solution of B in simple terms?

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

    Let's solve task for $$$m=1$$$. In this case we have one array and we need to calculate sum of absolute difference with every pair of elements. Let's sort our array. If we fix index $$$i$$$ and write all absolute difference with this element. We can see, that for indexes $$$j<i$$$ we increase answer by $$$a_i-a_j$$$ and for indexes $$$k>i$$$ we increase answer by $$$a_j-a_i$$$. For every index $$$i$$$ we maintain prefix sum and suffix sum for calculating answer in this index.

    For case $$$m>1$$$ we write all above for every column.

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

      firatly, m can't be 1. second, even in that case answer = 0 as there is no one to win against. didn't understand your explanation pls clarify it

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

Problem D has O(n logn) solution: https://codeforces.net/contest/1808/submission/199685296

In a same way as in the post we can transform orignal problem into counting pairs of equal elements, with some restrictions on distances between them.

Idea is to group all numbers by (array value, parity of its index), and for each group have an array of indexes. In each such array we have indexes of equal numbers, and for each element we need to only count a number of elements in some segment (coming from the distance restrictions).

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

Deleted.

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

Can somebody explain problem C tutorial's the first paragraph? For example, input values are $$$l=2340$$$ and $$$r=2360$$$. Common prefix: $$$23$$$, so $$$a=4$$$ and $$$b=6$$$. Condition $$$b-a >= 2$$$ is true, so tutorial advices to put $$$4+1=5$$$ as next digit of answer. But correct answer is $$$2344$$$.

Thanks in advance.

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

    You should also try 4 and 6. Maybe it is not so clear, but you should check all three variants.

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

      But what should be tried on $$$l=8710$$$ and $$$r=8762$$$ to choose the 3rd digit? $$$1$$$, $$$2$$$ and $$$6$$$?

      The second paragraph is unclear as well. How to apply it on following input value $$$l=536268$$$ and $$$r=536300$$$ to get answer $$$536277$$$?

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

        Hmm, seems you are definitely right here, editorial of C is pure trash. Will rewrite it later, thank you for the help.

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

          Wind_Eagle When?

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

            I'd suggest the following solution:

            First, let's observe, that if the numbers are of a different lenght, we can take $$$9..9$$$, as an anwser, where number of $$$9$$$'s is the lenght of $$$r - 1$$$.

            So, now the numbers are of a equal lenght. To construct an anwser let's trace $$$from$$$ the first different digits from left to right and maintain maximal and minimal digits in prefix. Let's say current digits are $$$a, b$$$ respectively to $$$r, l$$$. Now, we try to add to our prefix either $$$a$$$ or $$$b$$$, and if $$$a > b + 1$$$, we can continue our string with whatever we want, with the first element of a suffix in $$$(a, b)$$$. Also, we are free to add whatever we want, if our current anwser is not a prefix of either $$$l$$$ nor $$$r$$$.

            But, if we are, we may only add element from $$$[0, a]$$$, if our current anwser is the prefix of $$$r$$$, and $$$[b, 9]$$$ if it is of $$$l$$$.

            $$$\mathcal{O}({2^{\mathrm{|r|}}})$$$

            Solution: 200873882

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

In fact,the Problem E3 have one solution that costs O(k*log(n)).K can be much larger,for example,10^6 is ok. We can even develop a solution that costs O(log(n)) based on my thinking possibly.

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

Simple O(n) solution for D: https://codeforces.net/contest/1808/submission/200108231

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

    Since $$$a_i \leq 2 \times 10^5$$$, just use an array instead of unordered_map.

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

For problem D, I'm not completely sure about the first half of the 3rd paragraph in its solution. In particular, I get what the setup for array a looks like. However I'm not sure why the condition that a_i*a_j = 1, j-i<k, and (j-i)mod2 is enough. For example if the array a looks something like this: 101000101 and k = 5, then i can match the first and third indices as they satisfy those conditions. However they wouldn't correspond to each other in any substring of length 5.

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

    Agreed. For corresponding pair (ai,aj), its corresponding index need to satisfy:

    (i+j)/2-(k-1)/2>=1

    (i+j)/2+(k-1)/2<=n

    Also, ai and aj have to be in one subarray of length k, that is:

    j-k+1<=i<=j-2

    Ultimately we get:

    max(k-j+1,j-k+1)<=i<=min(j-2,2n-k+1-j)

    Hope it helps

    207331593

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

Since no one has mentioned it before, it is possible (and is very pleasant) to solve E3 in logn + logk using roots of unity

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

The tutorial of problem C really sucks!!!

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

I have a cool digit dp solution of C

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

When I solve E, the first thing I come up with is PIE, well the computation is not much and easily passed in O(K) runtime :v

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

Problem D : Brute force solution (count dissimilar pair for all subarray) is accepted using pragmas !! Taking only 1.1 second to be executed :) Note: Worst TP — (n^2)/8

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

Problem D cannot be solved with matrix but polynomial multiplication.277253973

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

awful explanation for C

→ Reply