### kartel's blog

By kartel, history, 2 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 Tutorial of Codeforces Round 861 (Div. 2) Comments (55)
 » I liked the problems and the contest overall. The beautiful illustrations were the cherry on top !!!
 » 2 months ago, # | ← Rev. 2 →   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)?
•  » » 2 months ago, # ^ | ← Rev. 2 →   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.
•  » » » Sorry if this is dumb, but how to do g^n on a vector?
•  » » » » Use simple polynomial multiplication and binary exponentiation.
•  » » » » » can E3 be solved using that? I tried but TLEed with FFT.
•  » » » This is more like convolution. How can we do the convolution using the matrix?
•  » » the $g$ for different $S$ could be the same, if we change the $f$ for fixed $S$.thus we could calculate the $g^n$ once, and calculate $f(s) * g^n$ for k times.
•  » » » E1 for different S,we have different y that we can't use,so the transition matrix is not the same,i think.
•  » » So does anyone have a explanation for this question now? I'm still confused.
 » C is also solvable with Digit DP!
•  » » Here is a bit clean code with digit dp idea — Submission
•  » » » Can you explain the approach?
•  » » » » 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))
 » 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.
•  » » 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
 » 2 months ago, # | ← Rev. 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
•  » » "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.
 » Can someone please explain D in simpler way?
•  » » Here is a similar atcoder problem, its editorial is amazing.Editorial
 » Here is my solution for problem C which can even find kth smallest number with the least luckiness
 » Can someone provide the solution for A in O(1). My O(1) solution threw WA on Pretest-2, test case 596.
 » Can anyone pls explain D in a simpler way?
 » 2 months ago, # | ← Rev. 2 →   For problem A both *90 and *09 are have maximum luck so in fact it is possible to reduce the brute force gap down to 80 as long as you exclude r < 10. Sadly I terribly misread the problem description during the contest and failed to notice until it was pointed out to me :D
 » 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
 » 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$))
 » For problem A, there's a solution using sparse table if you couldn't get the observation like me. 199925584
 » can somebody explain solution of B in simple terms?
•  » » 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.
 » 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).
•  » » 2 months ago, # ^ | ← Rev. 2 →   I have a similar solution but with a segment tree instead of BS.https://codeforces.com/contest/1808/submission/201087741
 » 2 months ago, # | ← Rev. 2 →   Deleted.
 » 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.
•  » » even i did'nt get that. this editorial sucks
•  » » You should also try 4 and 6. Maybe it is not so clear, but you should check all three variants.
•  » » » 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$?
•  » » » » Hmm, seems you are definitely right here, editorial of C is pure trash. Will rewrite it later, thank you for the help.
•  » » » » » Wind_Eagle When?
•  » » » » » » 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
•  » » You can see my approach above.
 » 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.
•  » » In details,see my solution:200069214
•  » » 2 months ago, # ^ | ← Rev. 2 →   ThanksBut we know about all these solutions :)
•  » » 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
•  » » » It‘s creative！！！
 » Problem C: Digit Dp approach — Codell l, r, curr, dp; str L, R; void cal(ll i, ll mx, ll mn, bool lt, bool ut, bool isStarted, str &formed, str &ans) { if (i == n) { if(mx - mn < curr) curr = mx - mn, ans = formed; return; } if(mx >= 0) { if(dp[i][mx][mn][lt][ut][isStarted] != -1) return; dp[i][mx][mn][lt][ut][isStarted] = 1; } ll lb = lt ? L[i] - '0' : 0, ub = ut ? R[i] - '0' : 9; for (ll dig = lb; dig < ub + 1; ++dig) { if (!isStarted and dig == 0) cal(i + 1, mx, mn, lt & (lb == dig), ut & (ub == dig), 0, formed, ans); else { formed += (dig + '0'); cal(i + 1, max(mx, dig), min(mn, dig), lt & (lb == dig), ut & (ub == dig), 1, formed, ans); formed.pop_back(); } } } void solve() { cin>>l>>r; L = to_string(l), R = to_string(r); while(L.length() < R.length()) L = '0' + L; n = L.length(); curr = inf; str ans, formed; memset(dp, -1, sizeof dp); cal(0, -100, 100, 1, 1, 0, formed, ans); cout<
•  » » can you plz explain the approach?
 » Simple O(n) solution for D: https://codeforces.com/contest/1808/submission/200108231
•  » » Since $a_i \leq 2 \times 10^5$, just use an array instead of unordered_map.
 » 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
•  » » 10 days ago, # ^ | ← Rev. 2 →   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
 » Since no one has mentioned it before, it is possible (and is very pleasant) to solve E3 in logn + logk using roots of unity
 » Can someone explain C with digit dp?
»

Code of B:

# include <bits/stdc++.h>

using namespace std;

# define fast \

ios_base::sync_with_stdio(false); \
cin.tie(NULL);                    \
cout.tie(NULL);

int diff(int x, int y) { if (y > x) swap(x, y); return x — y; } void solve() { int n, m; cin >> n >> m; vector<vector> v(m); // given input: // 4 3 // 1 2 3 // 3 2 1 // 1 2 1 // 4 2 7

// =====================
// =====================

// Our v=
//  1 3 1 4
//  2 2 2 2
//  3 1 1 7
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
int x;
cin >> x;
v[j].push_back(x);
}
}
for (int i = 0; i < m; ++i)
{
sort(v[i].begin(), v[i].end());
}
// Our v after sorting=
// 1 1 3 4
// 2 2 2 2
// 1 1 3 7

// Formula : calc[k]=calc[k-1]+(countOfElements*abs(v[i+1]-v[i]));
// Calcultion  for each row of sorted v:
// calc for 1st row : 1 + (1*1), (1+2*2), (5 + (0*3))=1 , 5, 5
// calc for 2nd row : 0+(0*1),0+(0*2),0+(0*3)=0,0,0
// calc for 3rd row : 4+(0*1),4+(2*2),8+(0*3)=4,8,8
// Total = 1+5+5+0+0+0+4+8+8
int sum = 0;
for (int j = 0; j < m; ++j)
{
int count = 1;
vector<int> calc(n);
calc = 0;
int k = 1;
for (int i = n - 2; i >= 0; --i)
{
calc[k++] = calc[k - 1] + (count * diff(v[j][i], v[j][i + 1]));
count++;
}
for (int i = 0; i < n; ++i)
{
sum += calc[i];
}
}
cout << sum << endl;

} signed main() {

fast int t;
cin >> t;
while (t--)
{
solve();
}

}

 » The tutorial of problem C really sucks!!!