## Hello Codeforces!

We're glad to invite everyone to participate in Codeforces Round 940 (Div. 2) and CodeCraft-23, which will start on Apr/21/2024 17:35 (Moscow time). The contest will be rated for all the Div. 2 participants (Rating < 2100).

The Programming Club at IIIT-H organizes this event as a part of our techno-cultural fest Felicity @ IIIT Hyderabad.

You will have 6 problems to solve in the duration of ~~2 hours~~ 2 hours and 15 minutes. One of the problems is divided into 2 subtasks. Do ensure you read all of the problems!

There have been a bunch of people that have helped us in making this contest a (hopefully) great one!

- ScarletS and KAN for their wonderful coordination.
- Alexdat2000 for translating the problem statements to Russian.
- akcube, fangahawk, GenghizKhan, JadeReaper, kevaljain, keyurchd_11, lezirtin, ppt1524, Prakul_Agrawal, SilverTongue1729, shakr, TheRaja who helped with brainstorming problem ideas and preparing them.
- A_G, dorijanlendvaj, Andreasyan, MridulAhi, codelegend, prvocislo, satyam343, shiven, mwen, JagguBandar, fishy15, islingr, nor, golions, WAtoAC2001, hackerbhaiya, carnation13, Murinh0, AbhijnanVegi, freaksier for testing the round, and giving useful advice regarding problem preparation to make the contest better.
- And MikeMirzayanov for the amazing platforms, Codeforces and Polygon, which has made contest preparation an even greater experience.

**Score Distribution:** $$$500 - 1000 - 1500 - 1750 - 2250 - (2250 + 1250)$$$

Hope you enjoy the problems!

**UPD**: The editorial can be found here.

**UPD**: The Winners

Hmm...purple allowed to coordinate?

> inb4 goodbye 2023 2.0

Hmmm cool

I hope I will not reach specialist in this round

As a participant,hoping for clear and short statements

Damn, never hoped that after Indian ICPC, IIITH Programming club would go international! Really looking forward to attend it!

Well... :p

Crazy 0_o

good

Hope to the positive delta after this round

bet

Will the score distribution of the problems be published? Or will the contest be held on ICPC rules?

It will have a score distribution. We will publish it soon.

fangahawk akcube orz!

fangahawk akcube orz!

Hope so there is no moss for this :)

As a tester I really liked the problemset and encourage everyone to participate in the round!

akcube fangahawk orz

Great to hear you enjoyed the problem set! Your encouragement really makes me want to dive in and give it a go. Thanks for the motivation!

Can you post the score distribution as well?

Hoping for pupil

I will upvote if I become CM

What if you become master?

then I will downvote

what if you become IM ?

Is that even possible?

Yes if you got rank #1 :)

That's only if either you've done ≤ 5 contests or if you're 2080+ rating.

then I will

Wishing everyone a good codeforces round after a week.

akcube round, orzzz!!!

what algorithms book and resources gennady korotkevich (tourist) read?

He is an algorithm book and resource by himself.

Will the score distribution of the problems be published? Or will the contest be held on ICPC rules?

Best of luck so that you can get good response for your questions, from IIIT Hyderabad.

clear and short description we like it

Minecraft !!

I can speedrun minecraft, does that mean that I will AK the contest?

That mean you'll get IM

whats AK?

all kill. Solving all

IIITH Programming Club orz

As a participant, I would like to get upvotes as minus looks ugly in my profile!

1K stalkers and I will write this one.

me first

yo I was your 1000th

i love you

Now you'll have to write the contest

I think I would be breaking several Codeforces rules by doing so

Let me help youLessgooo!

As a monkey tester, I was offered $$$6+9+6 \times 9$$$ bananas to write this comment.

I too wanted to join IIIT bcoz of the coding culture there, my clg sucks

Yeah I hear a lot about IIIT too....but then everything can't be helped I guess....at this point you should be contributing to building the culture there.

Hoping to reach pupi.

Why codecraft-23 in 2024, isn't it codecraft-24?

it's annual hackathon by IITH codecraft-24 will by 2025 ig

*IIIT-H

Not to be mixed with IITH :(

Oops! I just forgot to that 'I'

Not to be mixed with IITD :(

Best wishes for everyone's A, B, C, D

When will the score distribution be announced?

what meant by score distribution

Usually contest happen in either icpc style, i.e. every question has equal weightage, i.e. whoever does any question first gets higher rank. Whereas normal contests on codeforces (non educational rounds) have ratings attached to them so that they are indicable that it is 50% chance that it can be done by someone having rating about equal to what's shown, and the if you do a higher rated question its more rank than doing first few questions.

Score distribution $$$\neq$$$ problem rating, those are two separate things.

But scores are proportional to the earned points ig

Usually, yes, but his explanation was still wrong, he mixed up the two systems. The score distribution does not tell you how much a problem is rated, only its value in the contest.

Yeah agreed problem ratings depends on the problems itself there is no way one can just guess without opening the problem and not even the order justifies that I have C labelled 800 rated problem

To clarify, scoring distribution is different from the ratings attached to the problems post-contest. Ratings are given to problems after the contest is over based on number of solves, etc. and are indicative of the rating required to solve the problem in contest. Scoring distribution is just the points you as a contestant would gain if you solved it at the 0th minute. It's more or less only meant to be indicative of what the setters + testers approximate the relative difficulty of the problems to be.

Got it — "Ratings are given to problems after the contest is over based on number of solves"

Will try to solve 3 questions !! Wish me luck :)

ee sala cup namde

Good luck everyone

I taught this was a programming contest,looks like a math test to me

Only if you knew math, 2021 would have come by now

ouch

so much math i loved it, knew solutions within minutes of every question, but while implementation so many mistakes :(

can someone pls enlighten me on how to solve D

it is clear from the question that we need for each y

ax ^ ax+1 ^ ax+2 ... ^ ... ^ az-1 ^ az > ax ^ ax+1 ^ ax+2 ... ay ^ ... ^ az-1 ^ az.

note in lhs, ay is missing so basically what we need is all those ranges(x, y) in which sum of MSB of ay is even.

we need x, y, z. traverse through y, now for each y calculate no. good x and z pairs.

suffix and prefix dps can be maintained for each bit for odd and even counts.

Is MSB = max set bit? That makes sense but I'm kinda confused about how you would implement the prefix and suffix dp. If you don't mind, can you please give me the gist? Appreciate it.

Edit: oh wait nvm I see how to do it. Thanks broski

okay, both will have 3 states -> suffix/prefix, bit, odd/even. i will tell for prefix, suffix is similar. pref[n+1][30][2] (n+1, for simple implementation, 30 bits and 2 odd and evens)

dp state pref[i][j][0] represents count of bit j till ith elements such that parity/zor of that bit is 0(even)

basically

a1, a2, a3, a4, a5, a6, a7 a8 ....

if we are at a8, and we are taking a look at 4th bit (i.e., bit at this position -> (1<<4)) then if we take all suffixes ending at a8 and xor each suffix, the state represents no. of such suffixes that have THE 4th bit off.

think for transitions it's not that difficult/look at my code., if you don't understand then ill write it. (if anything is unclear don't hesitate to ask or even dm me.)

thx bro I understand <3

why msb ?

because in a range for a particular bit there can either odd or even no of that bits. now, we are taking a range (x, z) and we have to remove any element from that range new range -> (x, y-1) ^ (y+1, z), if in new range there are odd bits, then old range will have even bits of MSB.

basically i am structuring my solution such that it is dependent upon MSB.

ok,i know what you mean, just because remove aj will happen some change, and MSB will be make this change simple. thx

can you explain this part please, I get the pO*aE + pE*aO part but why did you add aO+ pO, can you please explain

SpoilerBecause x == y or y == z is also a valid option.

got it, thanks

I was way too close to solving problem C! Great problemset :D

Thanks for the math contest authors. Always appreciate a -100 delta.

C was way too hard for me... After an hour of intense math i found a formula, which gives much bigger answer for the second sample, but i just can't find any single thing wrong with it... If we won't place any rook on main diagonal there are $$$30$$$ possible positions for the first rook, after that there will be $$$12$$$ possible positions for the second rook and $$$2$$$ positions for the last one. In total it is $$$30 * 12 * 2 = 720$$$, which is already bigger, than $$$331$$$... What's wrong?

I was able to find a recurrence for C but was not able to submit in time because of runtime errors.

F(n) = F(n-1) + (2*n-2)*F(n-2)

where n is the total number of row and column numbers which were not used. Not sure if it is correct.

I also came up with same relation but I got WA 257630731

I forgot to add

`dp[0]=1;`

Oh god.same bro

me too

Can you provide the intuition for this?

Let us assume some n pairs (r,c) where the rooks have already been kept. Now we cannot keep the rook in any of those (r,c) or (c,r). So, that leaves us (n — r -c) rows and (n — r -c) columns.

Now, let us list down these x = (n-r-c) viable rows and columns as a1, a2, a3 .. ax.

So, we can keep the rook at a1,a1 and a1 will be removed from the above list and we will have x-1 elements in the list. (so, f(x-1) part)

If we take any other ai, we will have x-2 elements left, and we can arrange a1 and ai in 2 ways multiplied by numbers of ways to arrange those x-2 elements. And there are x-1 ways to chose some ai. Hence 2*(x-1)*f(x-2).

So, the recurrence becomes : f(x) = f(x-1) + 2*(x-1)*f(x-2).

I'm not great at explaining, so forgive me if this isn't clear.

Initially, I noticed that placing a rook at coordinates (ri, ci), where ri ≠ ci, eliminates 2 rows and 2 columns, reducing the chessboard from n*n to (n-2)*(n-2). Similarly, if ri = ci, it removes 1 row and 1 column, making it (n-1)*(n-1). Let's say after K moves, we've removed some rows and columns, leaving a chessboard of size m (m ≤ n). Now, this smaller board becomes a blank canvas for determining how many boards we can build by arranging the rooks. The challenge lies in determining the number of possible boards we can build. Initially, I considered a brute force approach where I place a rook on a cell, compute the resulting reduced matrix after the computer's move, and repeat.

\begin{cases} f(n-1),& \text{if } i=j\\ f(n-2), & \text{otherwise} \end{cases}

\text{ where cell } i,j

\text{ has a white rook}$$$

However, this solution is inefficient with a time complexity of O(N^2) and suffers from overlapping solutions.

For instance, consider a 3*3 matrix where a white rook is fixed at (1,1) you will get 3 possible boards.

Also when you fix rook at (2,2) you will get 3 boards.

As you can see we have one overlapping solution.

By examples I observed that we can calculate all possible boards by fixing the rooks in just one row. So we take a row and see all the variations of that row and calculate the number of boards for each variation and this would give us the unq count.

Below is the formula of our revised approach ( the base condition remains same)

\begin{cases} f(n-1),& \text{if } j=1\\ f(n-2), & \text{otherwise} \end{cases}

\text{ cell } 1,j

\text{ has a white rook} + \sum_{j=2}^n f(n-2)

\text{ cell } 1,j

\text{ has a black rook} $$$

If you simplify this you will get

.

I think the problem is that operation order doesn't matter, so it should be divided by $$$(n/2)!$$$

Maan, I am so bad at combinatorics)

Thank you)

Thought the same. Someone enlighten me.

The 720 possibilities are overcounted. Eg. These two configs are same;

The final rook positions are same in above 2 cases.

yeah, thought the same, i could figure out only that 1 is the way we put all in diagonal, so i need to come up with 330, maybe 720/2 gives 330 lol

I just solved it once the contest was over:(((((((((((( Unfortunately I couldn't submit my solution which I am sure that it is correct :((

I dunno what got into me, but i have found a recurrent formula, similar to yours, but for some reason I was trying to make it linear...

My way of thinking was similar. There are $$$10$$$ ways for the second rook, because $$$30-(4*8-4*3)=10$$$. And because by filling up the remaining diagonals, all these could be considered as final positions. So after placeing 2 rooks, there are $$$30*10=300$$$ possible positions, which again could be considered as final ones. And then $$$1+30+300$$$ gives $$$331$$$ (the $$$1$$$ is needed because the initial position can also be considered as a final one). But what I don't get is that we overcount the positions after 2 rooks, so it should be $$$150+30+1=181$$$. Can anyone please explain it to me?

Btw, my A got WA on system testing, wow... $$$a_i \le 100$$$ got me there... Definitely, not a good day for me...

this solution would have been correct if two rooks position swapped yields a different setting. but according to problem, they are same. and if you notice carefully, its 6! = 720 and there is a reason for that.

you can look at my solution i did not do recurrence i used combinatorics only.

did the same!

what you need to do is to divide this big number i.e. 720 with 3!.

It is because there are repeated groups in counting. and the number of repetitions for each group is 3!.

Does anyone have any advice for improving on problems like C in today's contest?

solve dp I think

OMG, I SUBMITTED D 8 SECONDS BEFORE THE END

I think D is more intuitive than C.

Problem B in a Nutshell, huge skill issue

Spoiler...

basically you can just check whats the biggest number for Math.pow(2,x)-1 <= k because Math.pow(2,x)-1 is only 1's, the rest of the number doesnt really matter and you can sum it up with the difference and the rest 0's

How to solve D?

UPD :- i was correct 257663607

can someone please explain b? I am getting wa.

Think about how any number that looks like this $$$2^{n}-1$$$ has all ones in it's binary representation. Also if $$$n=1$$$ just print the value of $$$k$$$. In all other cases where $$$n\geq1$$$ you only really need to print two numbers that sum up to $$$k$$$.

Let $$$b$$$ be highest bit in k. Then you can get $$$b-1$$$ bitcount by just printing $$$s = 2^{b} - 1$$$. Then print out $$$k - s$$$ and fill the rest with zeros.

Why does this work?

Either $$$k - s$$$ will be greater equal than $$$2^b$$$, then you've got all bits in answer and you can't make it bigger (note that it means k has no 0s in its binary representation,

or $$$k - s$$$ will be smaller, but that means that you "spent" 1 from b-th position to cover up all 0s in lowest bits.

Hello, I want to report a cheater "Sputnik123". No need to long text lol, he just cheated.

I Solved C during the contest but once I fixed some minor bugs in my code I found that the contest is over :(

Here is my (should be) Accepted code for problem C:

I didnt had dream last night for maths formula of c. so i was not able to solve it( btw one of worse c i have seen). (If author love maths then give olympiads)

Found my bug in C five seconds after contest ended. That sucks.

Any idea why this fails for B? Please help.

Hint: Brute force a solution for cases in which n = 2. Generate random testcases keeping n = 2 and see where your code gets a different answer from the brute force solution.

Solved D but at what cost.. nice D tho 🙂road to pupil :pray: thank you

how to solve F?

Anyone explain why this fails? 257627963

Try cases with low value of $$$n$$$.

Your submission fails for cases like n=2 and k=100. One answer is [63,37], with 7 1s, however your code returns [1,99] which has only 4 1s. The optimal way is to find such m, that 2^m-1 <= k

Any hints for problem F? I thought of doing merge sort segment tree with heavy-light decomposition, then binary search to find the lowest value that the count is not equal, but I realized there some edge cases.

My B problem got Judgement failed veredict, what that means?

Same here

Mathforces

problem C last minute submission got very much raised after 2:05 due to this solution being leaked online in a telegram group please MikeMirzayanov look into this behaviour of participants : screenshot of the solution , i will later reveal those solutions which are being cheated from here!(https://ibb.co/TTQGHV3) Vladosiya othmaine also look into this once please

one submission which was a random person in my friend list: link

found three cheaters they tried very much to keep their submission for not being detected 257640596 useless variables and deleting those we will get exact same as the solution even the line space etc is also exact same (spacing is same) ! 257641772 exact same , 257640016 exact same again . Please look mostlikely they may be undetected due to some minor changes but the format and spacing is exact same . MikeMirzayanov Vladosiya

I also checked out the previous contests which those three gave, Infact there too they cheated from a telegram group . Infact now the first user upsolved the B ,C problems which he/she already did in contest time . That also leads us to why he/she cheated the same code exactly which i shared earlier just because of some useless variable declarations like int p1=INT_MIN; he/she will not get caught at all.

Could anyone please tell me why the answer for n=6 in E is 24? I am getting 23 by hand and code, I was able to simplify the formula for C(i,j) mod j as follows:

1) if j is prime then ((i/j) mod j)*(j-1)

2) if j is not prime then we only need to do this for j=4 because (j-1)! mod j is 0 for all other composite numbers

Found my mistake

I guess D can be solved using dp

It's more observation i would say, if you can think of the final equation the dp is strightforward to use to calculate it

It's not combinatorics which has exponential time complexity in brute force. It's just a very classical "change your perspective to group quantities together" type of problem.

Exponential? You mean cubic?

Please read carefully of what I wrote before commenting. That's basic respect.

Oh sorry, I thought the combinatorics had something to do with the problem

Could anyone please explain how to do problem C? I always seem to struggle in these types of problems related to combinatorics :(

It is possible to solve using combinatorics but the solution would be way harder. (You need some techniques to reduce time complexity).

I guess the official solution would be DP: DP[n] = DP[n-1] + DP[n-2] * (n-1) * 2.

Would you kindly explain how you figured it out? Like explain why this works? I haven't solved many dp problems too.

Assume there is an N X N chessboard, and you know how many different configurations are there for 1 ~ N-1. Think N X N chessboard as an extension of an N-1 X N-1 chessboard.

yes

mathForces

Can't believe I'm this bad. Can't even solve 3 problems

no , contest was trash(2.25 hours wasted)

Problem C was quite to my liking and I was able to sprint to rank 50 after solving C, although temporarily(^_^)

But D was too difficult and I fell to rank 900+ for not solving any problem after C._(:3]<)_So how to solve it? I was confused by my prefix and suffix array, so tried brute force, but it got WA rather than TLE.

For any number, $$$a_i$$$ you can find that it satisfies the condition only when the xor of subarray in which $$$a_i$$$ is present has the MSB of $$$a_i$$$ set to zero, now you just need to find these subarrays for each element which can be done using dp for each bit j.

To find the first observation, try to think of an answer for $$$n^2 logn$$$ where you iterate on each subarray and find the number of possible y's in that subarray. What will be the condition for y?

why only MSB? If any bit is set in ai, but not set in xor of the whole subarray, then it would lead to a valid answer, right? It doesn't necessarily have to be MSB.

yes,i mean same of you, but i think twice MSB just make this question be simple. MSB just a "point"

because if the msb is set in the subarray then taking xor will make it zero and then for any bit< msb even if u set it you can't satisfy the conditon since $$$sum_{i=1}^{n-1} 2^i < 2^n$$$.

Can someone explain to me what this test result means? Also it's not even shown like -1 in results, just empty square, as if I havn't submitted this problem

https://codeforces.com/contest/1957/submission/257589755

Same with me, i investigated a bit and it seems that it's a internal error of the system not of the code. Hope they fix the error soon.

I rejudged your submission.

https://codeforces.com/contest/1957/submission/257588877

Bro judgement Failed why?

Rejudged.

Thank you ❤️

I rejudged your submission.

Thanks

Mine too.System test ended but it was not fixed.

Can you rejudge my submission for B. It sys judgement failed

Same problem with my B solution , it is still not judged when system testing is finished

Same here: https://codeforces.com/contest/1957/submission/257591439

https://codeforces.com/contest/1957/submission/257627565

same here

combinatorics is the most no skill thing you can ask a programer to do

My solution for q1 has been given the verdict as judgement failed, what does it mean?

everyone solved C using dp but I only did some n choose r math thingy 257639189

Getting Judgement Failed

https://codeforces.com/contest/1957/submission/257588877

How to solve E, F?

bruh

bruh

It says judgement failed for problem B https://codeforces.com/contest/1957/submission/257590765

E problem was just observations i think.. i didnt prove anything concrete, just saw first few values and came to conclusion that n = 4 and n = prime are kind of special cases to handle.

I am getting judgement failed verdict on this submission.

https://codeforces.com/contest/1957/submission/257590736

Rejudged and Got Accepted... Thanks

does anyone know what the verdict "Judgement failed" means. Muhammad-Saram got it and I feel bad for him. His logic was on point. Here's his submission

my solution for B is still not judged https://codeforces.com/contest/1957/submission/257594447 even when system testing is finished :/

codeforces broken or what? this is so so dumb

3 pages of judgement failed, strange.

And all of them were made almost at the same time

What is judgement failed??? Is it wrong answer?

https://codeforces.com/contest/1957/submission/257616209 I faced judgement failed in this submission?

https://codeforces.com/contest/1957/submission/257627565 https://codeforces.com/contest/1957/submission/257651698 submitted the exact code again and it passed now but gave runtime error during system testing. What's going on? Codeforces high or wat?

After contest i was looking for other participants codes and many many people have the same code for problem C. coincidence?

There are few :

https://codeforces.com/contest/1957/submission/257631107 https://codeforces.com/contest/1957/submission/257641417 https://codeforces.com/contest/1957/submission/257631632 https://codeforces.com/contest/1957/submission/257639699

https://codeforces.com/contest/1957/submission/257639989 https://codeforces.com/contest/1957/submission/257638818

Telegram group

For Problem B, can someone please explain why my submission 257616558 is incorrect? I agree I overkilled it a little bit, but I cannot see how the Jury's answer is better.

I would like to report a suspicious contestant: F9O1OvO

I think he cheated because his template has changed massively:

His submission for problem A in today's contest: 257575498

His submission for problem A in his previous contest: 255636465

His performance is also very unusual — I find it very weird that a specialist who has participated in more than 50 contests suddenly gets 5th in a div.2 round.

I believe he might have given his user to another person.

And they said: "If you solve ABCD, cheaters won't affect you", lol

Yeah lmao. When I previously reported some cheater, some user told sth similar also,

DebunkedCheaters can affect experts too.

Yeah a sudden Rk 5 and his template changing is definitely an indicator it wasn't him doing the contest.

can anyone tell me whats wrong in my code. I thought if sum of array is k and number of 1 bit is maximum it work. but it is not why? sub :https://codeforces.com/contest/1957/submission/257631018

same here

t = int(input())

for _ in range(t): n, k = map(int, input().split()) q = k ans = [0]*n l =0 while k>=2 and n>0: for i in range(0,k+1): if pow(2, i) >k: ans[l]= 2**(i-1)-1 l+=1 n-=1 k=k-(2**(i-1)-1) break

I think there is this set of data:

`n = 14, k = 720729`

. The number of1s actually equals to19, and you give17. I think your solution is inaccurate for the case where s is not equal to k.Nice round, but why problem E doesn't have a bolded notification that sum of n over subtests is unbounded? It messed me a bit up.

i submitted my E in the last 4 minutes just to realise that

✋✋✋**help wanted** ✋✋✋✋✋✋

i know i am dumb but can anyone tell me where the hell am i wrong here!it works like magic bitcount are correct+ sum of the nums are correct then what?t = int(input())

for _ in range(t): n, k = map(int, input().split()) q = k ans = [0]*n l =0 while k>=2 and n>0: for i in range(0,k+1): if pow(2, i) >k: ans[l]= 2**(i-1)-1 l+=1 n-=1 k=k-(2**(i-1)-1) break

atleast format the code before asking for help.

what an impeccable contest and i hope that there will be more contests like that

Mathforces (More like combiforces tbh).

This is one of the best rounds I have had in recent times, with clever ideas in every question! Hope to see more rounds like this~

What is the time complexity of question E？

Cool

In the next codecraft we'll have "How does the Knight move??"

I'm glad someone got that reference :D

哎

Nice Round !

Can anyone explain what's wrong with my Solution

Well

I hope to reach 1200 points after this compete

Why I'm not in the winners list??? I'm 2nd!!!

The two codes are the same but are not disqualify: https://codeforces.com/contest/1957/submission/257624238

https://codeforces.com/contest/1957/submission/257632265

i wish you all reach what u want :)

u too bro <3

thanks bro

oh nice image do u watch jujutsu kaisen too ?

lets be friends?