### kartel's blog

By kartel, history, 15 months ago, translation,

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
• +62

| Write comment?
 » 15 months ago, # |   +26 I liked the problems and the contest overall. The beautiful illustrations were the cherry on top !!!
 » 15 months ago, # | ← Rev. 2 →   +46 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)?
•  » » 15 months ago, # ^ | ← Rev. 2 →   +30 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.
•  » » » 15 months ago, # ^ |   +8 Sorry if this is dumb, but how to do g^n on a vector?
•  » » » » 15 months ago, # ^ |   0 Use simple polynomial multiplication and binary exponentiation.
•  » » » » » 15 months ago, # ^ |   0 can E3 be solved using that? I tried but TLEed with FFT.
•  » » » 15 months ago, # ^ |   0 This is more like convolution. How can we do the convolution using the matrix?
•  » » 15 months ago, # ^ |   0 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.
•  » » » 15 months ago, # ^ |   0 E1 for different S,we have different y that we can't use,so the transition matrix is not the same,i think.
•  » » 14 months ago, # ^ |   0 So does anyone have a explanation for this question now? I'm still confused.
•  » » » 11 months ago, # ^ |   0 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
•  » » » » 11 months ago, # ^ |   0 Oh,sorry,maybe I'm wrong
•  » » » » » 11 months ago, # ^ |   0 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)$
 » 15 months ago, # |   +4 C is also solvable with Digit DP!
•  » » 15 months ago, # ^ |   0 Here is a bit clean code with digit dp idea — Submission
•  » » » 15 months ago, # ^ |   0 Can you explain the approach?
•  » » » » 15 months ago, # ^ |   +3 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))
•  » » » » » 3 months ago, # ^ |   0 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
•  » » » » » 6 weeks ago, # ^ |   0 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 ?
 » 15 months ago, # |   +69 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.
•  » » 15 months ago, # ^ |   +18 If someone is interested, I've made a video, where I accessibly explain this formula (as well as all other problems):https://www.youtube.com/watch?v=i1i_7lqnGwA
 » 15 months ago, # | ← Rev. 2 →   +2 https://codeforces.com/contest/1808/submission/199905893Problem 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 lb2) 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 diffElse 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 iSo for I>=a and I<=b find min diff and print
•  » » 15 months ago, # ^ |   0 "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.
 » 15 months ago, # |   0 Can someone please explain D in simpler way?
•  » » 15 months ago, # ^ |   +1 Here is a similar atcoder problem, its editorial is amazing.Editorial
 » 15 months ago, # |   0 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
 » 15 months ago, # |   +11 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$))
 » 15 months ago, # |   0 For problem A, there's a solution using sparse table if you couldn't get the observation like me. 199925584
 » 15 months ago, # |   0 can somebody explain solution of B in simple terms?
•  » » 15 months ago, # ^ |   +8 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 $ji$ 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.
 » 15 months ago, # |   0 Problem D has O(n logn) solution: https://codeforces.com/contest/1808/submission/199685296In 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).
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 I have a similar solution but with a segment tree instead of BS.https://codeforces.com/contest/1808/submission/201087741
 » 15 months ago, # | ← Rev. 2 →   0 Deleted.
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 You should also try 4 and 6. Maybe it is not so clear, but you should check all three variants.
•  » » » 15 months ago, # ^ |   0 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$?
•  » » » » 15 months ago, # ^ |   +15 Hmm, seems you are definitely right here, editorial of C is pure trash. Will rewrite it later, thank you for the help.
•  » » » » » 15 months ago, # ^ |   0 Wind_Eagle When?
•  » » » » » » 15 months ago, # ^ |   0 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
 » 15 months ago, # |   0 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.
•  » » 15 months ago, # ^ |   0 In details,see my solution:200069214
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 ThanksBut we know about all these solutions :)
•  » » 14 months ago, # ^ |   0 In fact,Problem E3 have one solution that costs O(log(n)+log(k)).K can be 10^18.https://codeforces.com/contest/1808/submission/199698216
•  » » » 14 months ago, # ^ |   0 It‘s creative！！！
 » 15 months ago, # |   0 Simple O(n) solution for D: https://codeforces.com/contest/1808/submission/200108231
•  » » 15 months ago, # ^ |   0 Since $a_i \leq 2 \times 10^5$, just use an array instead of unordered_map.
 » 15 months ago, # |   0 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
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 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<=nAlso, ai and aj have to be in one subarray of length k, that is:j-k+1<=i<=j-2Ultimately we get:max(k-j+1,j-k+1)<=i<=min(j-2,2n-k+1-j)Hope it helps207331593
 » 15 months ago, # |   0 Since no one has mentioned it before, it is possible (and is very pleasant) to solve E3 in logn + logk using roots of unity
 » 13 months ago, # |   0 The tutorial of problem C really sucks!!!
 » 12 months ago, # |   0 I have a cool digit dp solution of C
 » 12 months ago, # |   0 Why ans of 1 10 is 10 .. Difference of digits is max for 9 na?For 10 it's 1
 » 11 months ago, # |   0 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
 » 7 months ago, # |   0 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