Привет, Codeforces!
Я очень рад пригласить вас на Codeforces Round #861 (Div. 2), который пройдет в 29.03.2023 12:05 (Московское время). Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 2100.
Моя искренняя благодарность:
Wind_Eagle, BaluconisTima, kartel, gepardo и 244mhq за идеи задач для раунда, а также BaluconisTima, 244mhq, VEGAnn, Vladik и andrew за разработку задач.
vilcheuski и programmer228 — остальную команду авторов, без которых этот раунд бы не состоялся.
BaluconisTima за прекрасные картинки, дополняющие все задачи.
MikeMirzayanov за платформы Codeforces и Polygon.
Вам, за то, что участвуете в этом раунде.
У вас будет 2.5 часа на решение 6 задач, одна из которых будет разбита на простую и сложную версии. Раунд основан на задачах заключительного этапа республиканской олимпиады по информатике в Беларуси. Просьба всех белорусских школьников, участвовавших в заключительном этапе, воздержаться от участия в раунде и обсуждения задач публично до конца раунда.
Я надеюсь, вам понравится раунд!
Тестировали раунд: Ormlis, 4qqqq, nnv-nick, olya.masaeva, Makcum888.
Предварительная разбалловка: 750-1000-1500-2000-2500-3250.
UPD: раунд был перебалансирован. Вам предстоит решить 5 задач за 2 часа, одна из задач будет разбита на простую, среднюю и сложную версии.
Новая разбалловка: 750-1000-1500-1750-(1750+1000+750).
Разбор: https://mirror.codeforces.com/blog/entry/114523
Победители:
Div. 1 + Div. 2:
2) maspy
3) happylmb
Div. 2:
1) happylmb
2) Cherished
3) 2021_yes
Belarusian National Olympiad <3
Belarusian National Olympiad <3
Why not Div. 1 / Div. 2? Is the final stage of Belorussian National Olympiad so easy?
Please more contests at this time
Please no more contests at this time.
We have to set this round at such time because original olympiad ends in 12:00 SET.
If you are in Italy, the usual time is not even bad for you. Please be considerate for the poor people who have this one at 5AM :)
This will be 2AM for me :<
He is doing an exchange semester in Australia
I agree, it's 5PM for me, really good
For me who live in Korea, Both contests are good 09:05 UTC -> 18:05 GMT+9 14:35 UTC -> 23:35 GMT+9
It's 17:05 CST (UTF+8). Great for Chinese users.
Notice the unusual time
The graph is opposite!
Почему у вас на картах бубны чёрные?! Почему на карту если с разных сторон посмотреть, то там или шестёрка, или девятка? Вы их в киосках заряжаете, что ли?
Это все п..производители карт
У вас дилер есть...
задачи в другом порядке разложены...
Я щас всем расскажу, что вы тут исполняете...
One more raid on cheaters?
what's that image in the post about?
There is a meme in russian community. If you wanna check it, you can google it like "случай в казино".
It's a hint for one of the questions ;)
The rating of people that didn't participate in the Belarusian National Olympiad
I don't know why but the meme is so relatable to my current situation :)
Rating change in the image seems terrible :dead:
Black diamond card of 6 isn't usual (bottom-6 should be flipped), is it a hint stating something not usual?
Anyways!
- Notice the unusual time everyone!
- Hopefully everyone gets +ve delta (make the image state false).
- Hoping for a balanced round :)
The length of the contest in the post differs from that shown in the contests tab
Last time I managed to upsolve A1-D. I hope I can perform well today too and become specialist again!
Is it 2.00 hours contest or 2 hours 30 minutes contest?different contest duration were given in blog and contests section
Wind_Eagle Please clarify this.
For those who don't know https://www.youtube.com/watch?v=3dYRN1rtncA
Still didn't get it!
Hope to get CM this time
i see it coming bro!
Congrats !
could the timings be shifted to the normal timings, not a conducive time to conduct contests
Does the picture imply that this round will be the next big milestone in my downward trend in rating?
Not rated for you LOL.
Very soon it may be...
Эта картинка идеальна...
OMG 750 A and unusual time round!
I can see my rating graph in the picture of picture :)
All the best everyone!
I think my new dp predicts my future rating graph
Best of luck everyone!!
Hoping to have a balanced round !
College viva or codeforces contest ＞﹏＜
Neither. I would like to choose dating.
The rating graph in the meme is opposite!
Hello Wind_Eagle,
I just found a typo in the blog where you say "divided into easy and hard verions." Although it is a minuscule one (of course, we are humans) but it would be nice to be corrected. BTW, I love your rounds and hope that this round would be fun for everyone too <3.
TT first time finally to participate in a CF round this early hahaha. I stayed up late in the dorm till midnight most of the times. Good luck guys!!
Score distribution is really interesting.
Now it's not a joke
Unusual time but hope for a positive delta rating.
omg 3 version E round
Am I the only one who noticed that master is above international master on the graph?
Expect three versions of E and hopefully increase ratings.
Go to Pupil bruhh
Wishing everyone the best possible work!
This is my first contest on codeforces, can someone give some tips to do good on codeforces.
Just do your best. Don't give up during the contest (This is what I used to do). No problem is hard and if others can do it then you can do it too.
Best of luck =)
Thank You :)
well!! , i suck :(
Hey! don't be sad, this was a tough contest indeed for everyone. I and every other cper started like this. This is the time when you should learn from your mistakes to avoid them in future, not to be sad. We are with you. Just practice as much as you can.
(BTW, I would recommend you to solve easier problems first then move on to the harder ones. As I stated before, you should not skip problems until you have given it your best.)
The rating graph seems like a warning to me. Anyway, I'm still gonna appear for it.
will E3 >3000 ?
No
Maybe 2600-2700
He said: The round is based on the problems from the Belarusian National Olympiad. We can ask the Belarusian students who participated in this Olympiad or find the solution in anywhere. So, I think this contest should be unrated because everyone can search the problem in Google (?).
No, they happen in the same time.
Good luck & Have fun!
hope to be Expert:D
The Hardest problems in Div. 2 I've ever seen.
Hardforces :(
Belarusian students had no problems with solving C. Half of the students successfully solved this task.
I couldn't imagine this task will be so hard.
I think it is not hard in general, it is just hard to come up with a solution fast in my opinion.
Which problems did belarusian students get on a contest from the Round?
ahhh
What do those Belarusian students eat?
Planets :')
Great round btw
This contest was held at 4 am for my timezone, I tried using segment tree for A and fenwick tree for B before I came to my senses xD
Test case 4 of Problem C irritated me in the whole contest
So do I...
How to solve B? Can anyone help.
Hint: I solved it by sorting each column and using prefix sums
Ohh ok just now i just sorted it and got the ans. But why won't it work if i don't sort it?
Think about the case like:
4
6
2
We can't discern between the 6 and 2 because they give the expected value of 8. So we need to take the sum of all numbers higher than the value ahead of it and also the sum of all numbers lower than the value ahead of it. We can solve this problem by sorting so that there are no lower numbers in front of it.
How to solve c? I can only think of digit dp Here is the wrong submission
There are two cases depending on the lengths of the numbers: 1. if the lengths aren't equal, you can spam 9s. 2. if the lengths are equal, find the common prefix(you can't change that part no matter what) and brute force the next two digits. You're answer will be something like common_part + x + spamming y's until you fill the length of the number. There won't be much candidates for the answer so you can check all of them.
Can you tell me why you have considered 2 digits, not 3 or 4?
Dunno, just observed it. If I have to give a concrete reason, probably because two digits are enough to set a min/max digit for a number. Even if we choose three digits — x < y < z — that would be useless, because we can just choose x = y.
I understand that we only need two digits for min/max. But do you have any reason why we don't need more than 2 digits for the purpose of the number being in between l and r?
I combined not equal length part of your solution and for euqal i applied digit dp. It Worked now, but still dont know why dp didnt worked for non equal length.
Thanks
You can break the problem col wise. Observe the pattern.
Hint1: Try to find contributions of each element to the ans.
Hint2: the solution involves sorting.
I guess u told ans for b , but i asked for c
You can use a greedy approach. You first try to create number with luckiness = 0, then 1, 2... To find number with luckiness = k, you can try out all intervals [i, i + k] where 0 <= i <= 9 — k You stop as soon as you find one
if l and r have different length, the answer is '9' * len(l). Else let i be the first position where l[i] != r[i] (I'm thinking of l and r as strings). We can bruteforce the digit on i-th position (l[i] <= d1 <= r[i]), and then fill the suffix with a single digit d. Then we just compare the numbers. Let our number be m. If l <= m && r <= m, we update the answer
thanks , i liked this approach
thanks a lot sir . could u please tell why this approach works
I don't really know why, just feels like it should work
Although all the greedy solutions explained here are probably correct, I will explain how to solve it using digit dp.
dp[n][mx][mn][t] -> largest number consisting of max n digits, having max digit mx, min digit mn, and tight t. After you compute the dp till r, you look for the number with minimum difference mx — mn, that also is bigger than l. The implementation is pretty tedious though.
Code
Hey , i also coded digit dp, my states were [idx][small][big][put][max][min], can u tell if i did something wrong there?
My solution uses digit DP approach: https://mirror.codeforces.com/contest/1808/submission/199670890
Maybe we can consider this round as Div1.5...2 hard 4 me.
was b is a copy from this:
https://www.geeksforgeeks.org/sum-absolute-differences-pairs-given-array/ i know here we compute the abs on a matrix but isn't it just a little different? ( since we can consider every column just an array)
My $$$O(4 \cdot k^2 \log n)$$$ solution is giving me TLE on E3 :((
Would be nice if this round lasted for 3 hours instead of just 2
Agree! Or at least 2.5 hours as originally planned.
Amazing contest, E problem is really cool!
can you please share your approach on C if you solved it.
seems like digit dp . But not able to solve due to time constraint
Hardest C I've ever seen :(
I spend more than a hour to solve it.
This round motivated me to solve more problems ;)
How to do A? i tried and i'm getting tle.
I'm very bad at cp.
Just run a loop from l to min(l+101,r) and check each in range :D
Can you please explain why the loop is till min(l+101,r)?
because it's guaranteed that you can get a number with final two digits '90'
Another approach for A link
Got 10 wrong answers on D,really keen to know what went wrong.
Loved problem D! very educational problem
Mathforces
Here is my code of problem B, but it got wrong in the pretest3. How can I modify it? Thanks:)
First, there is something wrong in your
if (n == 2). Then, maybe your solutionans+=tmp[j]*X, X+=2;is wrong.You can remove the unnecessary special judgement, and reverse the vector dimension for convenience. As you did, you can sort and then let
sumbe the prefix sum and when get the answer for $$$j^{th}$$$ person, justans += v[i][j] * j - sum.Sorry for my poor English. :)
Maybe my code can help.199651953
Problem 1808D - Petya, Petya, Petr, and Palindromes can be solved in $$$O\left(n \cdot k\right)$$$ on GCC with auto-vectorization in $$$795$$$ ms. You can compare left half of segment with reversed right half of segment. AC submission from contest
How did this got AC? This should TLE!
Deleted
Worst case is $$$k = \frac{n}{2}$$$. With such $$$k$$$ this solution requires $$$\dfrac{n^2}{8} = \left(\dfrac{\left(n-k\right)\cdot k}{2}\right)$$$ comparisons.
So, $$$\dfrac{n^2}{8} = 5\cdot 10^9$$$.
AVX/AVX2/FMA can operate with 256-bits registers called YMM. It means that GCC can keep $$$8$$$ integers in one register and compare these registers element-wise in single operation. Number of indexes where
a[i] == b[i]is the popcount from the bitmask of result of element-wise comparison.So, real number of operations something like $$$\dfrac{5\cdot 10^9}{8}=625000000$$$.
625 millions operations in predictable for GCC order it is not so much — less than second. All we have to do is help GCC to do his job in code optimizations and don't bother him.
Damn bro, from where can I learn all of this. By this way, we can solve many problems with larger time complexities too right.
I think that it can be used only with lightweight operations under subsegments of array.
You can read a book on performance engineering. The author is sslotin. Also you can read his CF blogs.
WA on pretest 4 for 4 times on problem 4
OMG
Problem C , 123 lines get WA on test#2 ^_^
Debug long time for C. In the end, I found that there may be overflow in my solution, but I have no time to change. :)
Nice registration count. Haven't seen anything like this before.
Also a prime
luckiness = 1
23333333
Wonderful round with interesting problems
totally agree
In A, why is the correct answer for the test case l=r=6 equal to 6? The largest digit of 6 and the smallest digit of 6 is equal to 6, so the answer should be 6-6 =0. Same goes for all numbers m such that 1<=m <= 9.
because you asked to output the luckiest number, not the amount of luck
Thanks!
My brain completely bricked. I had if r<=9: return 0 in my code the entire time and I didnt even consider that to be an issue.
Output the number,not its luckiness.
Could someone shed some light on how rating delta is calculated when the first problem is harder than usual? For participants who couldn't solve first problem, they are not considered to be in the contest, and this reduces the total number of effective participants.
Solved A-D. Unusual time and unusual difficulty.
A: For any 100 consecutive numbers, there must be a number end with "09" and it will reach the maximum luckiness (9). So we can let r=min(r,l+99) and solve by brute force.
B: For 1<=j<=m, consider the contribution of the j-th number on each card. We can sort all n j-th numbers, and the contribution of i-th number is ((i-1)-(n-i))*c[i].
C: Let t be the number we find, and assume L<t<R (we can do this by let L=L-1, R=R+1), then there must be a number d that d satisfies floor(L/10^d)<floor(t/10^d)<floor(R/10^d), but d+1 doesn't. Then we know that floor(L/10^(d+1))==floor(t/10^(d+1)) or floor(t/10^(d+1))==floor(R/10^(d+1)). First assume floor(L/10^(d+1))==floor(t/10^(d+1)), then if we know d, we can know (d+1)-th, (d+2)-th, ... 19th digits of t, and we can try for every possible d-th digits and check if floor(t/10^d)<floor(R/10^d). If so, we can assign (0~d-1)-th digits of t to the d-th digit (which means, the (0-d)-th digits of t are the same), and let it be a candidate answer. Similar for assuming floor(t/10^(d+1))==floor(R/10^(d+1)). Therefore, by considering all possible value of d and d-th digit of t, we can get at most 2*19*10 candidate answers, and we just need to check them to get the final answer.
D: Denote r=(k-1)/2. We need to count pairs of (i, j) such that:
i<j and j<=i+2*r and (j-i)%2==0.
a[i]!=a[j].
let mid=(i+j)/2, then 1<=mid-r<=mid+r<=n.
We can change the 2nd condition to a[i]==a[j] and subtract it from (n-k+1)*r. We store the positions of occurences of each number into different buckets (we need to store odd and even positions separately), and for each j we find the number of valid i by binary search.
how binary search in D is applicable ..plz explain.
using upper_bound(all(v),R)-lower_bound(all(v),L) to find the count of numbers in range [L, R] in a sorted vector v.
I use quite the same idea as yours for problem D but got wrong answer. Any idea why?
199778993
199684592 any idea why it gives Run Time ?
stollinstead ofstoi?Yes, this stupid silly mistake cost me penalty
In problem C, many solutions are giving wrong output on the test case
1 1000000000000000000 1000000000000000000such corner test cases should have been there.When will tutorial be posted?
A=B<<<<<<<<C=D
what is intended complexity of E2?
I assume it is k^3 * logn, because limits seems to dictate that, yet my solution of k^3 logn had to be optimized several times before fitting in TL with a pragma, and finally getting uphacked :(
If intended was k^3 logn, you could have relaxed the limits quite a bit, i think.
Can someone help debug this solution of D- 199696312 ,there is something wrong with implementation and i can't figure it out.
Take a look at Ticket 16788 from CF Stress for a counter example.
How to solve D ? Can anyone please explain in simpler way ?
Consider all the possible pairs of (i, j) that may be different which would result in a +1 in the answer, minus the pairs such that a[i] = a[j] and you will get the pairs that a[i] != a[j], you can calculate the a[i] = a[j] part using a vector and binary search, and the total number is the same as (n — k + 1) * (k / 2)
Here is my code, maybe looking at it is a lot more simple R199691512
Nice round! though D is a bit too similar to ABC290E
But I wrote a useless line of code but it resulted in an RE in final tests in D :( droped from ~100 too ~200 in rank, so sad ...
Another C solution, in $$$O(t \cdot 2^{10} \cdot 18)$$$
Let's implement function
next_mask(x, mask)($$$mask$$$ is the mask of the digits from $$$0$$$ to $$$9$$$) which return smallest integer $$$y$$$ such that $$$y \geq x$$$ and all digits of $$$y$$$ are in $$$mask$$$It can be implemented by bruteforcing prefix of $$$x$$$ that will be same in $$$y$$$ and then putting smallest digits from $$$mask$$$ in the remaining suffix but you need to be careful with corner cases.
So for actual solution we just bruteforce all $$$masks$$$ and check whether
next_mask(l, mask)is not bigger than $$$r$$$ and relaxing answer. Code: 199692880Instead of iterating through all of the masks you can just iterate through the pairs of minimum and maximum set bits in the mask and then build the answer.
I did something similar, but instead of constructing the answer I did digit dp. Code: 199704153.
Nice round.
What about the cheater raid this time?
)
For C,I code for an hour but Failed at Pretest.
Maybe D cost less time on coding than C.
First I appreciate all the time and efforts for all the contributors to this round for the interesting problems.
There was just a little bit of confusion to me since E1/2/3 was nothing more than an inclusion-exclusion + binomial theorem. To me it just didn't fit 3s of TL and only range <= 2000 for parameter k, which made me thinking of some other complicated algo till near the end of contest.
I'm just curious that were the constraints set so by design or by carelessness?
(I meant no offence to anyone that made this round possible, I'll apologize if I did so unknowingly = =
For E2 we have two solutions for $$$O(k^2 + \log(n))$$$ and it is easy to optimize this solution to $$$O(k + \log(n))$$$. It make no sense if we setted constrains for $$$O(k + \log(n))$$$. That's why we set $$$k \leq 2000$$$
please see this 199700596
it is based on similar technique to derive the closed form of answer, and it runs in $$$O(\log k + \log n)$$$, I guess
We know about this solution :)
So what's the solution can pass for k<=100 but can't pass for k<=2000? I can only come up with O(k+log(n)) solution.
Well, there's $$$O(k^3 \log n)$$$ (or $$$O(k^2 \log k \log n)$$$ with fft). For each total sum (k options) find the number of sequences with this particular sum that are bad. And subtract it from $$$k ^ {(n-1)} $$$ (amount of sequences with any fixed sum).
[deleted because of mistaking a powerful person for someone else]
I am glad to be mentioned.
I am struggling for this problem for a very long time. Then I realized that, an integer with the suffix that all number are same will never make the answer worse.
Maybe change the allowed runtime in problem D to 1 second? a lot of wrong solutions are passing: https://mirror.codeforces.com/contest/1808/submission/199698146
It's really hard to hack.
Better to increase limitation for $$$N$$$ and $$$K$$$ to $$$300000$$$, because changing TL is linear function, but changing of limitations is quadratic function.
Thanks to this round which make me be CM finally :)
seems that there exists $$$O(k)$$$ and $$$O(\log n)$$$ solutions for E......
$$$O(k)$$$ solution: https://mirror.codeforces.com/contest/1808/submission/199658264
$$$O(\log n)$$$ solution: https://mirror.codeforces.com/contest/1808/submission/199673882
So we can make E4 E5 now :P
In problem D, I was trying an approach similar to https://atcoder.jp/contests/abc290/tasks/abc290_e with some modifications but I cannot understand what's going wrong. Can someone explain? https://mirror.codeforces.com/submissions/SamyakSinghania
Take a look at Ticket 16789 from CF Stress for a counter example.
Thanks! Understood the flaw in this approach.
Thank you for Problem C. Refreshed my digit dp practice.
Nice Round! I think the problems were great, if you find yourself stuck on A,B and C then maybe these tutorial videos could help you out — Problem A, Problem B, Problem C video tutorial
Really nice contest. I personally liked the problems a lot. A little different than the normal div2 rounds. I loved it. Duration could have been more.
It's good to know that I am not the only one who used segment tree for problem A :)
I used sparse table for problem A
Nice balance of round
Any predictions of E1,E2,E3 rating?
see here
weird E xd
if (n == 1) { cout << '1'; return; } if (k % 2) cout << (poww(k, n) — poww(k — 1, n) — poww(-1, n) * (gcdd(n — 2, k) — 1) + m) % m; else k /= 2,cout << 1ll * poww(2, n — 1) * ((poww(k, n) — poww(k — 1, n) — poww(-1, n) * (gcdd((n — 2) % k, k) — 1) + m) % m) % m;
(poww means pow and gcdd means gcd) luckily didn't participate today or collapsed maybe lol
Why are the constraints on E3 so low? IMO, anyone who can get a solution that's $$$O(k^2\log n)$$$ should also be able to get the $$$O(\log n + \log k)$$$ one...
(not to say that E3 isn't difficult as is, it took me at least an hour of work after contest to solve it, haha)
Fast: 199736258 Slow: 199729972
Problem C:
if l and r not same number of digits, fill l with 9 and return.
if same number of digits, first find max common prefix. After that, brute force the next digit d, which is the first digit that l and r differs.
if we choose digits_l[d] < digits[d] < digits_r[d], then obviously just greedily fill the rest with digits[d].
if digits_l[d] == digits[d], then if we know the max_digit, we greedily fill everything after d with max_digit.
if digits_r[d] == digits[d], similarly, fill everything after d with min_digit.
Thus, just brute forcing the next two digits is enough.
Edit: Formatting
cockatooo_2025GM what do you mean by max_digit and min_digit?
Can anyone help me debug why my Digit DP solution is not working?
My Solution
Here's how to solve problem E in $$$O(\log n+\log k)$$$:
First, handle the special cases with $$$\min(n,k)\le 2$$$. Now assume this is not the case.
In a lucky number, call a digit "special" if it is equal to the remainder when the sum of all other digits is divided by $$$k$$$. Then, we will enumerate all lucky numbers by the location of their first special digit.
Suppose $$$k$$$ is odd. If the first special digit is not the last digit, say it is $$$a_i$$$ in the number $$$\overline{a_1 a_2\ldots a_n}$$$ then there are $$$k-1$$$ ways to choose each of $$$a_1$$$ through $$$a_{i-1}$$$, $$$k$$$ ways to choose each of $$$a_i$$$ through $$$a_{n-1}$$$, and then the value of $$$a_n$$$ is uniquely determined to force $$$a_i$$$ to be special. The sum of the number of lucky numbers with first special digit at index $$$i$$$ over all $$$i$$$ between $$$1$$$ and $$$n-1$$$ is $$$k^{n-1}+k^{n-2}(k-1)+k^{n-3}(k-1)^2+\ldots+k(k-1)^{n-2}=\frac{k^n-(k-1)^n}{k-(k-1)}-(k-1)^{n-1}$$$.
To count the number of lucky numbers whose first special digit is $$$a_n$$$, notice that if the first $$$n-1$$$ digits do not contain $$$a_n$$$, we can decrease each of the first $$$n-1$$$ digits by $$$a_n$$$, so that the first $$$n-1$$$ digits don't contain 0 and sum to $$$(2-n)a_n$$$ (all operations are mod $$$k$$$, of course). Using the roots of unity filter on the polynomial $$$(x+x^2+\ldots +x^{k-1})^{n-1}$$$ (or alternatively just using small cases to guess a pattern), we can compute that for each possible value of $$$a_n$$$, if $$$(2-n)a_n$$$ is a multiple of $$$k$$$, then there are $$$\frac{(k-1)^{n-1}+(k-1)(-1)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$, and otherwise $$$\frac{(k-1)^{n-1}-(-1)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$. There are $$$\gcd(n-2,k)$$$ possible values of $$$a_n$$$ that fall into the first case, and others fall into the second case, so we can add them to $$$\frac{k^n-(k-1)^n}{k-(k-1)}-(k-1)^{n-1}$$$ to get the answer.
The k even case is similar, only that now if $$$a_i$$$ is the first special digit, then $$$a_i+\frac{k}{2}$$$ also cannot appear before $$$a_i$$$. We get that there are $$$\frac{k^n-(k-2)^n}{k-(k-2)}-(k-2)^{n-1}$$$ lucky numbers whose first special digit is not $$$a_n$$$. Using the roots of unity filter again on $$$(x+x^2+\ldots+x^{\frac{k}{2}-1}+x^{\frac{k}{2}+1}+\ldots+x^k)^{n-1}$$$, we know that if $$$(2-n)a_n$$$ is equal to $$$0$$$ or $$$\frac{k}{2}$$$, then there are $$$\frac{(\frac{k}{2}-1)(-2)^{n-1}+(k-2)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$, otherwise there are $$$\frac{(k-2)^{n-1}-(-2)^{n-1}}{k}$$$ lucky numbers whose first special digit is $$$a_n$$$, and the first case covers $$$2\gcd(n-2,\frac{k}{2})$$$ values of $$$a_n$$$.
My submission which actually runs in $$$O(\log m+\log k)$$$ using Fermat's Little Theorem: https://mirror.codeforces.com/contest/1808/submission/199734771
Is this solution worth rating 2800? I think that the problem is overrated..
Finally reached pupil after 39 contests.
How to solve E2/E3?
Why is this solution accepted in problem C?
I'm not sure about the time complexity of the solution, but it was not hacked. Could anyone hack it or explain why it's correct?
Editorial when?
Can anyone explain the idea to solve C, I did see a lot of solutions but none of them really helped to get to the intuition.
The task C can be solved without DP. The key idea is constructing an answer number, trying to use the same value as at the previous index.
Submission: https://mirror.codeforces.com/contest/1808/submission/200894232
Let's cover edge cases first.
Considering l and r, as arrays of integers in range [0..9]: we have l and r of the same size and at some index i, where r[i] > l[i].
The value in the answer (array ans) at index i should be in range [l[i]..r[i]].
So let's go over all possible values for ans[i] and for each of them check all the possible endings, constructed using a single digit.
Can be implemented like that:
How do you prove the part where size of L == R?
When I thought about proving the solution, I found an even simpler solution. I will update my previous post. If you visually imagine all possible answers and L and R as lines on the same graph you can find it obvious.
Wait somehow C is 1900 and D is 2100. Feels like D is actually much easier.
A good contest!
Wind_Eagle Why not make $$$N$$$ $$$K$$$ larger, like $$$300 000$$$ in $$$D$$$?
Wanted to allow n * sqrt(n) pass. Didn't notice that nk with avx can get AC.
Can you kindly tell how can we do this avx thing. (By the comment it seems like some runtime optimization trick but I am not sure)
This line allows compiler to use avx assembly instructions. These instructions use vectorization and can do monotonous tasks faster, for example, do this code four times faster:
So you mean that $$$4*10^{10}$$$ can pass by using this in 1.5 seconds if the operations we are doing are small? It would be really nice if you give me the $$$nk$$$ solution that works with this technique for more clarification of the work avx can do.
https://mirror.codeforces.com/blog/entry/114392?#comment-1017510
I was just warned by the Codeforces system because my Problem C code is the same as someone else's. It's obvious that the reason is that I live-streamed the contest and some viewers copied my code. I want to ask if there is any way to avoid being plagiarized if I have to live-stream, or is live-streaming on Codeforces completely prohibited? But I always see some Grandmasters live-streaming on Codeforces.
Live streaming is a flagrant violation of the rules. You can publish a screencast AFTER the end of a round.
Why the picture in E3 uses gaster language?