The Programming Club, IIT Indore is proud to present our flagship event, **Divide By Zero**! The contest will take place on Apr/11/2021 17:35 (Moscow time). This round will be rated for all participants with a rating lower than 2100.

Thanks to the following people for making the round possible:

- KAN for coordinating throughout the round.
- kalpitk, ajit and 7dan for setting the problems.
- dvshah, bhanushali, sundesh, AniketSangwan, krishanu21saini, somyamehta_24 and hk2102 for their contribution to the problemset.
- Um_nik, dorijanlendvaj, 16204, Osama_Alkhodairy, ScarletS, taran_1407, kassutta and Jellyman102 for testing the problems.
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.

There are 6 problems, and 2 hours to solve them. The points distribution will be updated later.

**Update**: The scoring distribution is **500 -- 1250 -- 1500 -- 2000 -- 2750 -- 3000**.

**Update**: Editorial is up.

**PRIZES**: Twenty Codeforces T-shirt will be given to:

- Top 10 Indian Participants
- Random 10 from top 100 (rank 11-100) Indian participants

Hope you guys enjoy the contest! See you on the leaderboard!

**Update**: Here is the list of winners who won T-shirts. We will contact you guys soon. Congrats!

Top 10 Indian Participants

- kshitij_sodani
- amnesiac_dusk
- jtnydv25
- pikel_rik
- JrNTR
- piyushsethia1999
- kesh4281
- scansex
- _deactivated_
- Rahul

Random 10 from top 100 (rank 11-100) Indian participants

We have uploaded the link to the code for generating random numbers and ranklist here.

Indian round ,Cool,,, Hopefully I will be gray this round :)

It's not about hope, You'll be gray if you participate.

It was joke comment.

wow you are genius

Yess bro....Thanx for motivating me,,,,I will participate this tym,,,,I tried many time but I am not able to solve even one problem :)

EDIT:SpoilerTo be honest, I wasn't motivating, wether you solve all of the problems or none you will be newbie after your first contest.

This just got me to think, what's the maximum delta one could achieve? Like, say a new account finishes 1st in a combined round (like the global round). She will gain 500+(actual delta). Where actual delta might even be 500-600s considering it's a combined Div1+2+3 round. That's quite close to pupil, right?

Well, first of all it depends on the contest, as you mentioned global round is rated for the 3 divisions and it's nearly impossible that an unrated account ranks the first place. So second and third divisions are left(since an unrated account can't participate in a first division contest), and I've seen unrated accounts reaching the first place in a second division contest and gained at most 900 delta.

The person said max delta so it doesn't matter if its almost impossible for an unrated account to win a contest, plus you are also forgetting alt accounts.

An unrated account starts from 1400, the maximum is gotten from winning a contest. Also notice that the more the people in a contest, the higher the rating for the people at the top also same if the opponents are of higher rating, so the best case is winning div 1 but its unrated for a 1400, so we have to stick to global rounds and div 2s . You can use CF visualizer to check for the contests with the highest number of people in global and div 2 and 3.

Unrated accounts now start from 0 rating.

The real rating is 1400, 0 is just the display rating.

https://codeforces.com/blog/entry/77890

Yes, that is why I mentioned common rounds for all divisions. With div 2 or 3 the maximum change would be less.

Ifit ispossibleto get +700 then along with 500 (being first contest) one can still skip newbie and become pupilJrNTR

EDIT: Just wanna say he got 1000 in first round (I guess maximum possible)

Indian round ,Cool,,, Hopefully I won't be green this round :)

why indian guy ?

because IIT indore means The Indian Institutes of Technology Indore

I really think the "The" you mentioned was knowingly... Seriously..

i think its time to change the country part in the setting to india for this round :dicaprio:

Maybe time for getting a Shipping address in India too, and also ID proof.

PS.: Currently, shipping t-shirts would be tough in India too, shipping worldwide is almost impossible.

you can sell it to someone in india $

Not worth the effort xD

i know XD it was a joke but some people take it seriously lol

How is blue coder setting problems? I think rules were changed this year, you need to be at least 2100.

A blue can't set alone but he can do with orange or red. Orange/Red can only set contest.

I think yellow can set a contest.

As a contributor, I hope my contributions will become positive after this contest XD.

As an advisor; Try rewriting; as a contributor, in the beginning, that will surely stonk your contribution.

One of my little dreams is to see my contributions positive !! Certainly anyone no likes negative contributions, so don't be harsh with me and help me achieve this little dream ..

I have noticed you comment in almost each blog Maybe you should try to control your urge as it seems too irritating for others.

Thanks for your kind words, which caused more negative votes.. After this comment, I am no longer interested in my Contribution. I assure that you will not upset about see my comments anymore :)

Indian round cool. Expecting to do good and atleast come closer to green :)

All the best everyone .... Jai Hind

Many indian contest recently. You guys are motivated.

Naah, just population I believe xD

The same reason why there are so many smart Chinese :)

Hi Sir, I am not able to attend these contests which startsat 8:05 PM. So, Please Change the timing to Sunday Morning 10:00AM. So, Please consider my request. Thank you Sir

Anything else?

make earth flat i guess

On April 6th, a contest was held in Codechef which was prepared by IIT Varanasi. After competing in it I felt it's some what like a classical math question paper than a programming contest. So, is it Déjà vu ?

Indian round, cool

insert nationalistic commentsChina>India

k

Yes in inventing viruses

An eye for an eye only ends up making the whole world blind.

Hello Do Lund Trump

good to see India here.

I wish this contest have interesting problems and strong pretests.

Wish you all luck and rating increasing)))

Auto comment: topic has been updated by mtnshh (previous revision, new revision, compare).1250 for a B problem,The B is going to be some mind-fuck problem IMO.

I think it is just free points.

What a positive attitude you have, but then again you are a MASTER and I am a grasshopper(literally because i am green).

Funny thing is IMO can be read as International Math Olympiad:)

I have a feeling that this contest is going to be terrible.

Why?

looking at the score distribution

But you should not judge a contest by just looking at the score distribution.

Ok now I know what you were saying

LOL at least it was bad for me, problem C destroyed me.Such tight time limits :((

Edit: Turns out it was long long maing the TLE:(((

Sorry to bug but can you please point out what went wrong here.

https://codeforces.com/contest/1513/submission/112713639 https://codeforces.com/contest/1513/submission/112714167

Edit: Missed fast I/O ;-;

I think it's cool than chinese round,because chinese round is too hard,although it's my country...

hope I remain expert after this contest :)

Is it rated?yes

wake the firck up samurai

MikeMirzayanov it's kind reuqest. please no codeforcoes round during CSK matches. As you know this season dhoni last season. I want to enjoy both codeforces and msd. Please atleast change timings of CSK matches

what is it in cricket that you like?

LMAO

you can watch match recordings as well as participate virtually

The score distribution is wrong, lol

Why is my nlogn solution giving TLE for B? 112705441

You are initializing an array of size 2,00,001 in each testcase. Maybe that's the reason?

can anyone plz tell me why D wrong on pretest 3??

tujhe_kyon_janna_hai

isnt_it obvious? because he got WA on pretest3

Yes, someone please tell me what is the Pretest 3 in D.

Try this -

1

12 12

2 4 10 16 2 6 3 21 30 17 20 16

Answer — 55

I figured it out in the end but was not able to implement it in time.

It is passing. You can check my submission here.

Can someone explain me the approach of C?

I precomputed number of digits for 0 to 9 until 2e + 50 and then solved eatch testcase in log10(n) by simply adding values from the array.

I did the same thing. https://codeforces.com/contest/1513/submission/112704320

mine passes in 857 ms. hella dude, your passes in 140ms, i think yours is too much optimized, can you explain what you did ?

I think you used

mod(%)much more than I did. Also you used#define int long long.F, I read somewhere that #define int long long will comeback to bite me someday. xD

Can you please explain a bit like what went wrong here? One is with pre-computation and the other one without. https://codeforces.com/contest/1513/submission/112713639 https://codeforces.com/contest/1513/submission/112714167

Edit: Missed fast I/O ;-;

I think, we don't need to precalculate all the answers from 0 to 8. It is a big optimization not to do this. For more information, see my comment below.

its a series. https://oeis.org/A103377

What is the formula to that series?

Is it cool to access oeis, during the contest ?

As long as the resource being looked up exists before the start of a contest, it is okay to take help from that resource during contest

I have just debugged my code :( But I think it will be AC. EDIT: It got AC: 112711140

We can calculate answer independently for every digit, so we can use precalculation.

Precalculate all the answers (200000) for 9. It will take about of 2*10^6 operations

Then, in every test case count how many times every digit is present in n. I have used cnt array for that.

Substract every number from 1..9 from 9 and check if it's less than m. If it is, just add calc[m — (10 — i)] * cnt[i] to the answer. Else, simply add cnt[i] to the answer.

Time Complexity: amortized O(1) per every test case.

Code:

Codehttps://codeforces.com/contest/1513/submission/112705430

I am getting TLE On Pretest 3? What is wrong with my submission?

try to add ios::sync_with_stdio(false); also add #pragma GCC optimize("Ofast") and #pragma GCC target("avx,avx2,fma")

ModuloForces

How to solve D?

Can anyone explain why I am getting Runtime error on pretest 1 for problem C? Its working fine on my local machine! https://codeforces.com/contest/1513/submission/112707395

your code has "index out of bound" on line 51

How did you check that? My local runtime env doesn't complain..

Add

`-fsanitize=undefined`

to your compiler's flag. But even without any flag I still got segmentation fault.Btw, thanks it was indeed the mistake. I reckon, you deleted your comment of -Wall, but that was some good info for me again, so thanks for that. In my case -fsanitize=undefined does give me runtime error now. Thanks a bunch! :)

so hard :(

I agree.

For problem A, I noticed someone's solution only printed "-1" if n>=k

So I tried to hack it with a test case of n=3, k=1

But the solution was in python and I forgot integer division works differently in python :(

This contest is hard and required to know a lot of Math knowledge, just in my opinion. It is hard for everyone who has no experience. Bye bye Blue. I am back to Cyan soon.

It's harder than usual but not because of the math knowledge imo.

I agree that it needed more math knowledge than usual, but mostly math that occurs pretty commonly in competitive coding, not anything completely out of the blue.

A — Adhoc, maybe a bit mathy

B — Required some basic combinatrics, so fair enough its pretty heavy math for a B.

C — Pretty standard dp, no math involved

D — First observation is somewhat math intensive for a D (gcd = min means all elements are multiple of the min), but the rest of the problem requires no other math, just intuition of why Kruskal's algo constructs an optimal MST.

E — Pure math, all non-combinatorial observations can be made using just the samples. Then its just standard combinatorial ideas that most 18-1900+ rated participants should have likely come across.

F — didn't solve, no comments.

Oh, ok. Thank you for your problem comments.

For some reason, everyone's problem A sols were hacked but its been reverted

Problems were hella good imo, especially D

how to solve b

The condition in the problem is equivalent to finding the number of permutations of Indices of the array's elements so that ap1 and apn are bitwise and operation of all of the elements in array a. So let cnt be the number of occurrences of (a1 & a2 .. & an) in array a, if cnt is less than 2 then there is no such permutation and the answer is 0, otherwise the answer is cnt * (cnt — 1) * (n — 2)!.

For intuition, consider n = 2. This has a valid permutation when both elements are identical.

Now consider n > 2. What if the first and last elements in the permutation are different? Then, this is not a valid permutation since you can always make a 1-element group which has just the larger endpoint, and a (n-1) element group with all the other elements. The AND of the group with the smaller endpoint is strictly smaller so there's no solution.

Now we know the end points have to be the same. What about the middle elements? Assume there's an element in the middle that has a 0 in a bit where the endpoint has a 1. Then, we can always make a (n-1) element group that will have an AND smaller than the other endpoint. So, every element a_i in the middle must equal the endpoint when ANDed with the endpoint, i.e. satisfy (a_i AND a_0) = a_0. This also implies the endpoints must be the smallest values in the array.

So the answer is (count_of_smallest_element nCr 2) * ((n — 2)!), assuming there's at least 2 of the smallest element and all values in the array equal the smallest value when ANDed with it.

nice observation, need to study byte manipulation. weak area of mine.

Actually it is called bit manipulation ;)

Lol yes that's what I meant

If only I never knew matrix expo, would have I not made three TLE attempts at C, coded the intended dp solution and saved the contest. Unlucky day, though I had fun nevertheless. Good contest.

matrix expo is not needed

I realized, the constraints made sure it doesn't pass.

Nope, I passed.

Missed D just by a minute :(

I really need to know why my D failed, sumission, else my brain might explode. Please.

I have the same code... also very curious :) submissions

I also have a similar solution. Maybe our logic isn't correct.

It is quite similar to the one that passed, but rn I can't find the mistake. https://codeforces.com/contest/1513/submission/112692615

Try this -

1

12

12

2 4 10 16 2 6 3 21 30 17 20 16

Answer — 55

nope,this is not a good test,my code is right on this but wrong on 3rd TC

Maybe, but the above person's code failed on this test and mine too.

There are 5 components:

So cost of all is 5*2 + 2*3 + 4*12 == 64

How to get 55?

You can connect 3 and 6 to get a cost of 3 instead of 12.

Ok, thanks :/

Let's say you have a testcase like this:

Your algorithm connects 2 to 6, then doesn't connect 6 to 3. This can be fixed simply by using DSU instead of your

`vis[]`

array.I made the same mistake and realized it after contest. Think of the following p=10 2 4 6 3

here 2 will connect 4 and 6 and 3 will be connected to(2,4,6) by p=10 in your case but the better way will be to connect 3 to (2,4,6) by the edge of weight 3.

Yeah, there's a catch out there! Notice that every time you're trying to connect your current index to some node on the left or right, you're checking if the left or right has already been considered or not! Now, consider the case like array [2,6,3]. Your algorithm will start from the first node and mark both 2 and 6 as connected So when you try to connect 3 to 6 (as 3 is the gcd of [3,6]), your algorithm denies saying that 6 is already visited! Now you can observe that the accepted codes have incorporated a slight change that allowed every node to be considered by potential values both on the left and right. An easy way out is always the DSU method, and when you wanna avoid that, you need to be careful about the components! So yeah one possible input is:

1

3 100

2 6 3

I just don't get it, why my solution of C fails with TL. Looks like some very dumb mistake, which I don't see.

This is the main part. The rest of the code is precomputation that doesn't depend on inputs and takes just 124ms.

try adding fast io

tie(nullptr)

sync_with_stdio(false);

Yep, that was the issue. Got AC with 327ms

I got same tle, then i change cin and cout to scanf and printf and it passed

also you use endl, which flushes the output on each iteration, use "\n" instead

Nice point! Using endl instead of "\n" takes 826ms vs 327ms

Btw, had to rewrite it from python to c++ because the most natural implementation didn't fit into time limit

Unnecessary tight time limit for D2C

Slow I/O operations, i.e., cin/cout.

Just added this to your code:

Btw, it got WA due to integer overflow: 112713355

Yes, I've already fixed it: https://codeforces.com/contest/1513/submission/112712250

https://codeforces.com/contest/1513/submission/112698905

This is my solution for Problem C. According to me, its Time Complexity is O (10 * m) which is 2 * 10 ^ 6, which is very well for 1 second, I believe. It is giving TLE verdict on pretest 3.

What can be the possible reason behind this ?

Thank you !

every time you count dp again

Its O(10*m*t)

I believe time limit per test case is 1 second, so why is t being included in Time Complexity ?

Correct me if I am wrong.

Each test includes t test cases. Time limit for ALL t test cases is 1s

You are given t <= 200000

The time complexity of your solution is O(t*10*m) which can be around 10^11 in worst case. So, it is giving TLE.

deleted (answered the wrong comment)

deleted

Just precalculate the dp once instead of calculating it every time.

Could somebody tell me how to do E and F :<? Thanks <3

For E, we want to reach $$$\frac{sum}{n}$$$ as the value of all elements. Lets call this the $$$\textbf{good}$$$ value of the array, all elements smaller than it as $$$\textbf{low}$$$ elements and all elements larger than it $$$\textbf{high}$$$ elements.

Clearly a high element can never be made less than good, as it can never be used later as a sink (due to step 4), meaning we can never make it good. Same for low elements and greater than x. For the same reason, good elements can never be used in an operation.

Now lets notice that if there exists any subsequence of the form $$$\textbf{low high low high}$$$ or $$$\textbf{low high high low}$$$ or $$$\textbf{high low low high}$$$, we can get different end costs by mapping the lows to different highs. So if there is more than 1 low and more than 1 high, we need them to all be separate, that is all lows before highs or vice versa.

So we just want to arbitrarily choose where to place the $$$\textbf{good}$$$ elements in the array, multiply that by the number of ways of individually permuting $$$\textbf{low}$$$ and $$$\textbf{high}$$$ respectively. (and that by 2 if the array actually has $$$\textbf{low}$$$ and $$$\textbf{high}$$$ elements for the other direction)

Ways of choosing places of good elements is clearly just $$$n \choose cnt_{good}$$$. Ways of placing low and high can be found is just multinomial theorem.

In E array is balanced if sum is divisible by n and there is no subarray [x, y, x, y] where x is less than sum / n and y is greater than sum / n. You can calculate number of combinations with multinomial coefficient.

Wow now that I realized I misread the problem statements. I thought i can't be source anymore :<. Wonder how many people like me and can't solve E :<?

I did as well for 20 mins and asked a clarification for the sake of my sanity after seeing it was the other way around. That part is really unnatural, like you'd expect it to say $$$i$$$ and $$$j$$$ can't be used again as source and sink respectively but it says the opposite. Once you realize the reason for the condition its obvious which it is, but till then its something that's really easy to miss and should have been bolded.

Totally agree!

My Submission for C got TLE on pretest 3. Afterwards, including fast I/O and changing

`for(auto x:s)`

to`for(auto &x:s)`

,it got passed. How?because t <= 2 * 10 ^ 5 and you code for passing system test needed for ios_base or scanf & printf

The constraints were too tight:)

I had resubmitted my same correct solutions of first two questions later but my earlier correct solutions were skipped in system testing and my rank got changed .What can I do now?

You can do nothing. That's the rule.

But I had submitted same solution both times.

Yes, but CF doesn't know that. And even if it does, that's literally the rule. You can't really complain about this.

yeah, the one submitted later is considered even if the previous one was accepted, also I don't think codeforces lets you submit exact same solution twice.

He just removed some comments of the old submission so that's kind of unfortunate.

Codeforces considers the most recent submission even if the earlier one is correct:)

I think codeforces doesn't allow the exact solution to submit twice. At least when upsolving.

problem A: here take some cheesy math! problem B: here take some more math! problem C: hold on! I got some more math!

honestly speaking, Problem set sucked! you know math you solve it easily, you suck at math you get rammed!

>see numbers

>"MATHFORCES!!!"

None of the problems were related to math excluding B, besides that they include numbers and digits... C was DP, B had an observation, counting permutations was an easier part and A was just a constructive.

I thought it was quite a well balanced round in terms of topic variety.

Could someone please provide me counter case for my submission of problem D .Test case 3 is very long.

Here is a counter:

See this comment, I think it is same problem as my code.

The problem is, we do connect adjacent elements only if they have same gcd on both directions. But that is wrong, something like

`2 6 3`

gets connected for the price of 5 instead of 2+pthanks VTifand for counter case.

thanks spookywooky.Yes it was that mistake. I corrected it.

The problem C and D are wonderful! Really nice round.I love it.

got the idea of solving C when there was only a few minutes left. tried my best to implement it but just couldn't finish in time :'(

https://codeforces.com/contest/1513/submission/112708303 Here is my solution for question c.. which is giving TLE.. but I suppose it's time complexity is O(m*10+t*10) in the worst case.. please explain

you have long long everywhere, try to replace it with int

Try to use "\n" instead of endl because endl takes a lot of time as it clears the buffer after each output

He has #define endl "\n"

Replace endl by "\n", as it takes about 500ms more

.

What about the submission links and their usernames? Copy pasting the code doesen't help much.

https://codeforces.com/contest/1513/submission/112681391

Can someone please explain why I am getting TLE on this solution of C? I think the time complexity is O(m+t*log(n)) which should run well within 1 second?

Same issues as in my solution, see comment https://codeforces.com/blog/entry/89520?#comment-779333

Let me know why my solution is getting TLE . I have used fast I/O https://codeforces.com/contest/1513/submission/112700123

You are actually do the dp 10 (or 20) times you need to. Consider that a digit x produces the same result after m steps as the digit x+1 after m-1 steps.

Ya i have implemented the same

No, you did not. You can get rid of this outer loop

`for (int k = 0; k <= 9; k++) {`

, would make it 10 times faster. for example see this submissionOk thanks

U have used endl ,which itself takes too much time,in case of big test cases, just replace endl by "\n" ,u will see the time will be reduced to half of the previous execution time.

Got it thanks!

Thanks. Got AC with FAST I/O. 732ms to 186 ms with printf instead of cout.

try using FAST I/O statement you can go and see into my submissions your code is accepted after using FAST I/O

Thanks. I didn't know about FAST I/O

use scanf, printf

For heavens' sake, stop using scanf and printf in c++ and don't recommend them to others. They don't belong to this language

Incredible contest:)a contest with decent level gradient in the questions.

Here I see a lot of comments related to problem C. Most have implemented using a 2d array of size [2e5]*[10].

But, here you need to note that instead of precomputing till 2e5, you will have to precompute till at least 2e5+9.

You can check my submission here.

C is nice!!

Those who are unable to do it let me explain

lets think in this way if the number is this 023109

so if we know that after m operation what is the length if we start from "9" so if we know that after m operation what is the length if we start from "2"

so we just have to add cnt(0,m) + cnt(2,m) ..... cnt(9,m)

where cnt(x,y) denotes what is the length after y operation if we start from x

we can precompute ans for 0 to 9 for each m this wont take O(m*10*10) time complexity which satisfies our time limit

I am extremely disappointed with test cases of problem C of this round. I wrote a perfectly correct algo for the problem and was constantly getting TLE in testcase 3 of the problem. After the contest ended i just changed cin/cout by scanf/printf and boooom, it passed all test cases. You should avoid such test cases which show TLE just due to the way of taking I/O.

I wonder how did you solve problems with large input before.

You should always use fast IO (the ios_base......stuff)

Can anybody help me to find why my solution is wrong for problem B? Thanks in advance. https://codeforces.com/contest/1513/submission/112687504

ans=(c*(c-1)*fact_table[n-2])%modu;

Replace the above line in your code with-

ans=(((c*(c-1))%modu)*fact_table[n-2])%modu;

and see if it works.

why is my solution to B giving wrong answer? please tell. 112718984

The problem is with the precedence of operators (sad). In your code, if you change this line

`if(a[i]&mi != mi)`

to this`if((a[i]&mi) != mi)`

. It will work. This kind of mistake sucks xDThank you!

waiting for editorial .....

Does anyone have an idea why is this (https://codeforces.com/contest/1513/submission/112721127) nlognlogn solution too slow?

EDIT: nvm I know where I made a mistake

Thanks for your effort!

Problems B, D and E are beautiful and so good in my opinion.

Problem C is just rude because of its TL, in my opinion. It's just about pre-calculation. Testcases are queries, in fact. Matrix exponentiation solution with O(1e3 * log(m) * testcases) should pass, because it is not a simulation solution anymore. Even matrix solution with O(1e3 * 2e5) pre-calculations didn't pass. Why so tight TL?

I saw lots of solutions for problem C with precalculating length after m operations separately for different digits. But notice that after applying 1 operation to 1 we get 2, then 3, ..., 9. This means that for example applying m operations to 7 is the same as applying m + 7 operations to 0. So, we can precalc this values for 0 only.

I tried the same but failed. Can u share your solution?

It‘s dirty, but here it is 112685719

My submition is still waiting for recounting(((

We'll check tomorrow.

Does somebody know why identical submission show different results?

Submission 1: https://codeforces.com/contest/1513/submission/112726786

Submission 2: https://codeforces.com/contest/1513/submission/112726577

lol, because one problem is C and the other is D

wow, im actually stupid, thank you

Memorable contest for me. I became an expert:)

I got this message after the contest:

This is my submission : https://codeforces.com/contest/1513/submission/112682833 This is the other submission : https://codeforces.com/contest/1513/submission/112679357 I don't see how that is not a coincidence! And I already got another warning in another contest for compiling in ideone (which, at that time, i did not know was a violation of rules)

Who experienced rollback rating for this contest? I am unrated this contest and come back to Blue? Some thing went wrong???

Can you guys please announce the selected random 10 contestants for a t-shirt from 100?

Updated!

Hey I just checked the list of top 100 participants. My name was not there, although I think that it should be there. Any specific reason?

We have updated the ranklist; there is no change in ranks.

It was an honest error from our end; sorry for the inconvenience.

No issues. I thought there was some other reason.