Hello, Codeforces!

I am very glad to invite you to the Codeforces Round #861 (Div. 2), which will take place in Mar/29/2023 12:05 (Moscow time). **This round will be rated for the participants with rating lower than 2100.**

My sincere thanks to:

Wind_Eagle, BaluconisTima, kartel, gepardo and 244mhq for the tasks ideas, and also BaluconisTima, 244mhq, VEGAnn, Vladik and andrew for preparing the tasks.

vilcheuski and programmer228 the rest of the author team, without whom this round would not have happened.

BaluconisTima for the splendacious pictures, which complement each problem.

MikeMirzayanov for Codeforces and Polygon platforms.

You for participating in this round.

~~You will have 2 hours and 30 minutes for solving 6 tasks, ~~ The round is based on the problems from the Belarusian National Olympiad. **one of which will be divided into easy and hard verions.****We kindly ask all Belarusian students who participated in this olympiad, to refrain from taking part in this round and discussing the problems publicly before the round ends.**

I hope you will enjoy the round!

**Round testers (will be available later):** Ormlis, 4qqqq, nnv-nick, olya.masaeva, Makcum888.

.**Preliminary score distribution: 750-1000-1500-2000-2500-3250**

**UPD: the round was rebalanced.** You will have 2 hours for solving 5 tasks, one of which will be divided into easy, medium and hard verions.

**Score distribution: 750-1000-1500-1750-(1750+1000+750)**.

Editorial: https://codeforces.com/blog/entry/114523

Winners:

Div. 1 + Div. 2:

2) maspy

3) happylmb

Div. 2:

1) happylmb

2) Cherished

3) 2021_yes

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

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

From the score distribution, I guess problems gonna be interesting,hehe

SpoilerSounds like a

goodround in advance. :)Notice the unusual time

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

true

Rating change in the image seems terrible :dead:

Something SUS!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.

Hope to see the color change. I am looking to see. Enough number of problems. Thanks.

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

Belarusian National Olympiad round <3

Bad time. I can't participate

OMG 750 A and unusual time round!

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

Codeforce contest

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.Is this the usual time?

Many participants are surprised from this!

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

SpoilerScore distribution is really interesting.

Unusual time...

Now it's not a joke

Unusual time but hope for a positive delta rating.

omg 3 version E round

Will it be harder than Div 2 usually that we give?

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!

Know me?

Yes, you study chuyentin.pro, right?

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

Thank you so much for the advice, actually after reading the problem statement, i thought D was doable, but it failed at 7th pretest, but i will practice for sure and be a better programmer.

The rating graph seems like a warning to me. Anyway, I'm still gonna appear for it.

will E3 >3000 ?

maybe :v

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!

A beautiful time for Muslims in Ramadan

hope to be Expert:D

Uhhhh, forgot to register

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

fastin my opinion.Which problems did belarusian students get on a contest from the Round?

Not able to solve any of it, TLE on second ques too.. :( Long way to go for me..

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

I got hit with TLE on the fourth test case too :D

Us bro us

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.

Ohh ok understood thx a lot. becoz while calculating the ans might be in negative (before applying abs) if it's not sorted.

After sorting, find the sum of the absolute difference of all pairs of an array by using i*a[i] — (n-i-1)*a[i].

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?

Sounds good to me

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

Oh yeah. Sorry. My brain is dead.

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

ndigits, having max digitmx, min digitmn, and tightt. After you compute the dp tillr, you look for the number with minimum differencemx — mn, that also is bigger thanl. 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://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.

spent almost whole time on C and still not able to solve it completely.

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.

SpoilerI'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'

ohh yeah now i undertood that, I was thinking something else the whole time. Thanks for the explaination :D

try to break when you encounter difference of 9 it might not give you TLE it should work for A not for C

Another approach for A link

Man you Made it So Simple How did get the intution for solving by policy based DSA

Got

10wrong answers on D,really keen to know what went wrong.Loved problem D! very educational problem

--DELETED--

Mathforces

By kewang_zhili, history, 1 minute ago, In English, Attach this blog to some contest as a resource Edit text I have 2 accounts on my name (one kewang_zhili) and (KiritsuToKetsui).(with different ID's) .I created the second handle today(29/03/2023) and saved the handle on my PC.Then I registered for Codeforces Round 861(Div.2) and solved the A and B qns with id's "199686950" and "199683280" ;without realising that I was on the 2nd(KiritsuToKetsui) handle,and when I did recognise it I logged out and hastily submitted the same back in (kewang_zhili) handle.BUT I FORGOT THAT THERE WOULD BE A PLAG CHECK.Kindly excuse me for this time,as it was a genuine innocence,which shall not be repeated again @MikeMirzayanov

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 solution`ans+=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

`sum`

be the prefix sum and when get the answer for $$$j^{th}$$$ person, just`ans += 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

ExplanationWorst 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

Don't tell me you submitted the wrong solution 4 times just to comment this

Problem C , 123 lines get WA on test#2 ^_^

I have 2 accounts on my name (one kewang_zhili) and (KiritsuToKetsui).(with different ID's) .I created the second handle today(29/03/2023) and saved the handle on my PC.Then I registered for Codeforces Round 861(Div.2) and solved the A and B qns with id's "199686950" and "199683280" ;without realising that I was on the 2nd(KiritsuToKetsui) handle,and when I did recognise it I logged out and hastily submitted the same back in (kewang_zhili) handle.BUT I FORGOT THAT THERE WOULD BE A PLAG CHECK.Kindly excuse me for this time,as it was a genuine innocence,which shall not be repeated again @MikeMirzayanov

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

Iam reading your comment since last few contest and I find it very useful

suggestion : you can first give hints and then approach (you can hide hints and approaches it helps more in upsolving )

And Thanks for the simple explanations :)

199684592 any idea why it gives Run Time ?

`stoll`

instead of`stoi`

?Yes, this stupid silly mistake cost me penalty

In problem C, many solutions are giving wrong output on the test case

`1 1000000000000000000 1000000000000000000`

such corner test cases should have been there.I wouldn't expect such problems. But cool. I liked them. The most interesting question was C for me. What was the approach for that guys?

i solved it after the contest end, i fixed every possible smallest and largest digit and then i took some digits from this range so that it fits in the range from L to R.

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

What should be the Probable rating of Problem B

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

Unable to parse markup [type=CF_MATHJAX]

. 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://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://codeforces.com/contest/1808/submission/199658264

$$$O(\log n)$$$ solution: https://codeforces.com/contest/1808/submission/199673882

SpoilerSo we can make E4 E5 now :P

problem A the way luckiness is defined wouldn't the luckiness of 9 be 0

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

Take a look at Ticket 16789 from

CF Stressfor a counter example.Thanks! Understood the flaw in this approach.

Thank you for Problem C. Refreshed my digit dp practice.

can you explain it in bit detail please

testmayank123 hello

why are tagging me

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

I tried upsolving the problems last night. I could not solve A lol. I used segment tree but got a TLE and had to read the official solution. I am planning on using sparse table and coding up another submission soon to make me feel better about bricking a div2 A

Edit: Got it Accepted XD 199865819

Nice balance of round

Any predictions of E1,E2,E3 rating?

see here

Simple editorial for the problem A. Lucky Numbers.Here is the detailed explanation: Linkweird 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

Jerry20110434 what do you mean by max_digit and min_digit?

A lucky number where is my fault please reply me this is my code

## include<bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t--){ int l,r; cin>>l>>r; vectorv; int Max=0; int Min = INT_MAX; int count=0; int Maxres = 0; int n=0; for(int i = l; i<=r; i++){ v.push_back(i);

}

You can break when you encounter MAX-MIN ==9 it should work

No bro its is not work if i am written if((Max-Min)==9){ break;

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

You can see my code

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://codeforces.com/contest/1808/submission/199734771

Is this solution worth rating 2800? I think that the problem is overrated..

Finally reached

pupilafter 39 contests.Wind_Eagle when the editorials for this contest will be released? thanks

When will be solutions come out?

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?

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

Tried Ques C (without digit dp) using simple maths . giving wrong ans TC 7 (158 case Wrong ans). idk which case I'm missing . TLE doesn't seem to an issue.

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.

You can have a look on my solution. Here is the link :)

thank you

No problem bro

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://codeforces.com/contest/1808/submission/200894232

Let's cover edge cases first.

Considering

landr, as arrays of integers in range [0..9]: we havelandrof the same size and at some indexi, 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

avxthing. (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://codeforces.com/blog/entry/114392?#comment-1017510

Cool! thnx <3

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.

I'm sorry, I'm the copycat. I lost my mind during the competition and copied DLUT_Zeratul's code. I can guarantee that this kind of thing will not happen again, if it does, the administrator can shut down my account. I really think Codeforces' anti-plagiarism system is great and reminded me to correct it in time. Let's hope Codeforces has no more copycats in the future.