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
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
1808D - Petya, Petya, Petr, and Palindromes
1808E1 - Minibuses on Venus (easy version)
1808E2 - Minibuses on Venus (medium version)
1808E3 - Minibuses on Venus (hard version)
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://mirror.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$$$ 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 $$$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.
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
did you read the constraints? m can definitely be 1
Problem D has O(n logn) solution: https://mirror.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://mirror.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://mirror.codeforces.com/contest/1808/submission/199698216
It‘s creative!!!
Simple O(n) solution for D: https://mirror.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
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
Problem D cannot be solved with matrix but polynomial multiplication.277253973
awful explanation for C