**Solution**

**Solution**

**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**

By Shayan

Before stream
04:41:23

# | User | Rating |
---|---|---|

1 | tourist | 3845 |

2 | jiangly | 3707 |

3 | Benq | 3630 |

4 | orzdevinwang | 3573 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3532 |

8 | ecnerwala | 3501 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 154 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | pajenegod | 144 |

10 | orz | 143 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

1808D - Petya, Petya, Petr, and Palindromes

Tutorial is loading...

1808E1 - Minibuses on Venus (easy version)

Tutorial is loading...

1808E2 - Minibuses on Venus (medium version)

Tutorial is loading...

1808E3 - Minibuses on Venus (hard version)

Tutorial is loading...

Tutorial of Codeforces Round 861 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2024 15:18:37 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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)?

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[0]$$$ for fixed $$$S$$$.

thus we could calculate the $$$g^n$$$ once, and calculate $$$f(s)[0] * 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.

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

Oh,sorry,maybe I'm wrong

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)$$$

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))

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

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 ?

ans of E is

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

https://codeforces.com/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

"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

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$$$

goodpositions are odd too, for all even $$$i$$$goodpositions are even.For every index $$$i$$$ we have to count $$$z$$$ = number of non-equal to $$$a_i$$$ elements on

goodpositions, to do this we can count $$$x$$$ = number ofgoodpositions and $$$y$$$ = number of equal to $$$a_i$$$ elements ongoodpositions, $$$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

goodpositions is just some simple math, the number of equal to $$$a_i$$$ elements ongoodpositions 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 $$$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.

Problem D has O(n logn) solution: https://codeforces.com/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).

I have a similar solution but with a segment tree instead of BS.

https://codeforces.com/contest/1808/submission/201087741

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.

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

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

Thanks

But 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！！！

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<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.

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

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

The tutorial of problem C really sucks!!!

I have a cool digit dp solution of C

Why ans of 1 10 is 10 .. Difference of digits is max for 9 na?For 10 it's 1

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

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