Hello, Codeforces!

I invite you to participate in Codeforces Round 931 (Div. 2), which will be held on Mar/01/2024 17:35 (Moscow time).

The round will be **rated** for participants with **rating lower than 2100**. Participants with higher rating can participate in round unofficially.

You will have 2 hours to solve 5 problems, with one of the problems having 2 versions. **One or more interactive problems may occur in the round**, so please read guide for interactive problems before the contest.

All problems are authored by me.

I would like to thank:

Akulyat for round coordination and help with preparation

A_G, okwedook, rui_er, jdurie, lunchbox, _rey, wjli, .-O_O-., aryanc403, akshaykhandelwal, PartTimeCoder, carnation13, its_pranjal_83, Ianlsam, Immerser, vikram108, praneeth6116, soham976roy, and Dev_30 for testing the round and providing useful feedback.

MikeMirzayanov for Codeforces and Polygon platforms.

Good luck to all participants!

**UPD**: Score distribution: **500 — 1000 — 1500 — (1500 — 1250) — 3250**

**UPD2**: Editorial

**UPD3**: Congratulations to the winners!

**Div1 + Div2**

Place | Participant |
---|---|

1 | Um_nik |

2 | BurnedChicken |

3 | arvindf232 |

4 | turmax |

5 | hitonanode |

**Div2**

Place | Participant |
---|---|

1 | mlmlml |

2 | 2018LZY |

3 | q1w2e3r4_1 |

4 | shade34 |

5 | damjandavkov |

first comment of this contest! first day of spring season! first ... hmm what else? let's add something)

your first comment in a leap year :3

As a tester, problems are very interesting :)

You mean tough?

well, I believe you my master

As a tester, I can assure that you will enjoy the problems.

harsh__h first contest orzz

As a tester, I enjoyed testing this round a lot! :)

harsh__h Thanks to all the authors for arranging the back-to-back contest.

ruler姐姐！

.

As a tester, I can ensure you that the problems are quite engaging. You will love solving them. Lots of learning on the way!!

Hoping for the best Div.2 round!

[deleted]

[deleted]

Why downwote?

First contest on the spring!

I hope the tasks will be as short and clear as the announcement of this contest!

Good Luck for EVERYone!

OMG purple round

Interactive problems? I don't even know how to solve them, does anyone has resource which I can refer

Interactive Problems: Guide for Participants

Thanks a lot for authour and tester for very good and high quality of problemset(at least A,B and C)

score distribution???

Updated:)

sounds like a tough contest tho

Codforces Round 931 (Div. 2) i think there is mistake

Thanks

IIT Guwahati orz <3

interforces

I hope it's better than last round

aryanc403 testing back to back contests

About to turn into

`aryanc404`

with the missing stream links.he took a break till Tuesday

Back to back cf contests. I like it !

As a second time tester, this is definetely one of the top 2 rounds I ever tested.

jdurie tester orz

jdurie :heart_eyes:

Jdurie

Hope C is not interactive :D

u guessed exactly btw

don't hope again

Give us the score distribution,precious! (Read in Gollum's voice.)

I want to become blue wish me luck

contest on the first day after 29th February. Let's see!

What happened to the chain of pictures of authors?

hope no bitmasks(

never hope again!

Bring it on, It's time for My Redemption.

Seems we both suffered last div2. Atb for this one!

That's true I guess

Bro i suffered this one also :(

:( last 2 rounds have been tough...

One and only author harsh__h :)

Can anyone explain me why downwote?

Welcome to Codeforces bro

Wow. Two contest in a row and two positive delta.

Can I be a newbie tester for some future contest. I want try what it's like to be a tester.

It's easy you just have to write that that were the best problems you've ever saw in your life in comments.

This problems were indeed the best problems I solved in my entire life. Especially the interactive problem, I just loved it

How can we hack others in interactive problems?

In many of them, the author of the question was clarifying this. I hope it will be the case this time.

Problem setters pic where

Oh, post a selfie

with one of the problems having 2 versionsOne or more interactive problemsXD XDindian setter = mathforces

lol true :)

it was very enjoyable contest

Waiting for problem setters

picsThere is only one author.

There is just one author and people are asking him to post his selfie onto the announcement which will be shown on the home page lol. (no offense)

Amazing maths problem (propply)

Looks like recent Div 2 demotions in the current contest are considered “out of contest” even if their rating is 2100 by the start of the contest. Any reason why?

https://mirror.codeforces.com/contestRegistrants/1934/page/2?order=BY_RATING_DESC

whats wrong with last 2 rounds?

Probably it's a part of Goodbye Codeforces series

i'm apologizing on my knees

awful contest

Wtf, why C is interactive again? Is it so hard to make up NOT interactive problem for Div2?

No early screencast from Um_nik? :-(

can we stop with the interactive C please, welcome back pupil

i really like it personally, even though i couldn't solve it. You may never do interactive problems if you don't encounter it in a contest

russian translation for D1 is a bit strange. In english text it says: "This is the solo version of the problem". But word 'solo' is also used in russian text "Это сольная версия задачи". At first I thought it was somehow 'salty' version of problem D (salty is used to describe contention, bitterness, anger, or an otherwise-foul attitude). I got confused for a second, I even changed the language of the text to doublecheck.

I think the better way to say it both in english and in russian was "This is non-interactive version of the problem" / "Это неинтерактивная версия задачи"

Though I guess it would change the meaning — I suppose that by 'solo' the authors meant that unlike in D2, D1 IS NOT a two player game [as of game theory classification] (:

Such a beatiful contest , I decided to give up just like my crush.

not able to solve problem B I should quit CP

Author probably thought he was proposing these problems for a math Olympiad

see y'all in green :|

Why is the limit on operations 63 in problem D when there is a solution with 2 operations?

May be to make question more easy. :)

Problem C seems to essentially be a duplicate of a problem which I wrote in a previous DMOJ round, but with one fewer step.

bruh that's basically my National OI problem in 2019

Damn, seems very easy to reinvent then.

deleted

What's wrong with this contest?

why c is interactive

can someone please explain me problem B

First, observe pair $$$10,15$$$. What can you say about it?

i use 15 coins (n/15)

then switch case 14 cases...(remain of divided by 15)

Let's call the answer of this problem $$$f(n)$$$. I did some experiments and found that for almost all $$$n > 30$$$, $$$f(n) = f(n - 30) + 2$$$, but there seemed (only!) two exceptions: $$$f(35) = 3 \ne f(5) + 2$$$, and $$$f(38) = 4 \ne f(8) + 2$$$.

So my solution was as follows: generate a table of $$$f(n)$$$ up to $$$n \le 60$$$ using DP, and for $$$n > 60$$$ calculate $$$f(n)$$$ using the above formula. I didn't prove, but the results of experiments seemed very promising.

I solved it in a partial DP sort of way. Calculate the least number of coins required for creating sum up until 30, beyond which the optimal way would be to first reduce the amount to below 30 by taking as many coins of 15 as possible and calculate the minimum for what's left.

The main problem arises when you have 23/20 coins left, because if you blindly apply greedy you will get 15 + 6 + 1 + 1 and 15 + 3 + 1 + 1, when the optimal way is actually 10 + 10 + 3 and 10 + 10, respectively

What is the maximum times you can use any number? [1, 3, 6, 10, 15]

Is there any point in using 3, 3, 3, 3? Or 1, 1, 1, 1, 1, 1? Or 10, 10, 10?

In some cases yes, just google unbounded knapsack it's a standard problem

Yes I've solved unbounded knapsack problem but in this problem we had to minimize the number of coins so I thought its best to replace 3, 3 with 6 and so on.

For small numbers all coins necessary. For huge only 15.

For a math contest my solution is wrong, but that's how programmers do it, just precompute and forget

There is no hack phase this time?

Only in div. 3 and edu div. 2. You can still hack but you'd have to do it during the contest.

How do you do it during the contest?

I don't know sorry

First, lock a problem using lock icon visible on dashboard. Then, click on the Room tab, where you can see coders who are in your room, you can only hack among these. The locked problems here should be visible in bold format. Click on the solution of any other coder for the same problem and hack it.

Amazing interactive problems; I don`t know how to start.

Did anyone else get this annoying error for Problem C

wrong output format Unexpected end of file — int32 expected (test case 2)?Also, I technically never submitted a problem and passed test case 1, so is my participation unrated?

no, its rated for you

the problems were nice although I could only solve A , B

spent whole contest time for problem C

C was really cool problem

yeah but, I'm terrible at geometry

I guess its about pattern. SO if there is only

ONEmine — you can request 1,1 and if dis is less then n, we will request (n-(n-dis), 1) cause it will be on diagonal of n, else (n-(dis-n),m) then we within 2 request we can find mine. But there are two mines, so we will spend two more request, cause one mine will be on diagonal and the second mine is tricky. Maybe I complicated the solution, but anyway you can check my code.same

A and B problems Screencast here: https://www.youtube.com/live/iSkTzLR84pQ?si=EbJ_9lnTspSnm6Pw

D was easier than B.

imo D2 < D1 < B < C lol

though I must add that i think problem D2 was quite nice

how to solve D?

You just need to change x such that MSB of Y is set in X.

For D2, the consider the parity of the numbers of '1's in the binary representation of $$$p$$$. (Hint: when played optimally, the current player wins if and only if there are an even number of '1's in the binary representation of $$$p$$$)

249172627 can anyone please tell me why Div2.C giving such error?

there should be space between "?" and x and y.

also you are using endl multiple times.

I know this is a skill issue on my part, but still — CF should really give a interactor / tester like GCJ used to. I presume me and many others just YOLO submit interactive problems without testing at this point since it is a pain to validate compared to normal problems.

You can use jdoodle for testing them, there's a separate switch to enable interactive input

For simpler problems like C, I somehow manage to make a judge function in my local environment, but yeah for complex problems like D2 where the interactor needs to be smart, such thing would really save a lot of time.

So bad...

Can someone please say, why I'm getting rt here? 249171286

You are printing both (x1,y1) and (x2,y2) as answers

Oh, yeah, I was in a such rush that I didn't read the statement properly

I had a terrible experience in this round as well as the previous, both C and D1 are true mind benders.

Signing up AB -- 15mins, wrong idea for C -- 15mins, trying D1 and getting 3 WAs -- 45mins, correct idea for C -- 25mins, work on D1 again -- 15mins

C is a good problem but very painful to implement. Took so much of time for me.

Good round overall, thanks harsh__h and all testers!

Yeah good round, thanks harsh__h

What DO you Do in Interactive Problems???? Can someone pls explain

I followed the instructions but still getting

Idleness Limit ExceededMy Code

Thanks!

You have to flush before taking input and after giving output, you're flushing after taking input.

It wasn't accepted lmao

MathForcesXORForces

Which problem used maths ?

InteractiveForces

Fair. I like them in general, although I always have a bad time debugging my programs. Especially this time.

-100 lets go

also what happened with my C

edit: lines intersect outside of boundary. Accepted now

You only need to ask any three out of c1,c2,c3,c4 queries. (c1,c4) and (c2,c3) are complementary equations, so each mine satisfies exactly one of these equations. On solving the three equations, you get two solutions, exactly one of which is a mine. For the final query, you can ask the distance from either of these solutions. If the distance is zero, then it is a mine. Otherwise, the other solution is a mine.

Worst day ever

us moment... not as worse as yours yet a bad one

At least you are not alone

are you sure?

it hurts

A: Sort a[i] and the answer is a[n]+a[n-1]-a[1]-a[2].

B: We can believe that for some n0, we have dp[n]=dp[n-15]+1 for all n>=n0, and we can solve the problem by brute force for n<n0. (n0=300 can pass)

C: First query for (1, 1), let answer be d0, then there will be a mine on the line L0: x+y=2+d0. Then we query for the 2 endpoints of the intersection of L0 and the grid, let these points be A1,A2 and answer be d1,d2, then the circle (A1, d1) and (A2, d2) will have exactly 1 intersection with L0 in the grid, one of them will be the answer.

D1: If n is power of 2 we cannot do any operation. Otherwise, let r=floor(log2(n)). If 2**r<=m, then (m^n)<n, we can solve the problem in 1 operation. Otherwise, let t1=floor(log2(n-2**r)), t2=floor(log2(m)). If t2<t1, we can solve in 2 operation: n --> 2**r+m --> m. If t2==t1, we also have (m^n)<n and solve in 1 operation. If t2>t1, there's no solution.

D2: Let ppc(n) be the count of '1' in the binary representation of n. Then if ppc(n) is even, we always can do some operation to turn it into n1, n2 such that ppc(n1), ppc(n2) are odd. If ppc(n) is odd, for any n1, n2 such that (n1^n2)==n, one of ppc(n1) and ppc(n2) will be even. So If the initial ppc(n) is even we play first, otherwise we play second, and we can always let ppc(n) to be even on our turn. To win in 63 turns, we can let n1=2**r, n2=n-2**r, if the opponent choose n1 they will lose immediately, if they choose n2 the value of n will be halved.

For B, is n0 = 30 the right minimum value for it?

For B I think that n0 = lcm(1,3,6,10,15) = 30 is the "optimal" choice

B could be solved greedily. Grab 10 or 1 (based on the current n) until it is divided by 3, then grab 3, 6, 15 greedily for the rest. Submission

Explain you approach. Also why you are keeping n>= 10 ?

I'm not keeping n >= 10. If n < 10 then obviously I couldn't grab 10 coins.

249172491

I think I did what you said, but it tle on test 1, could you help me with it please?

In this section p1 will be the lowest bit of n. Try to let p1 be the highest bit of n.

Oh I see what can happen. Now it works, thanks!

May be I am wrong, but in problem D1 are you not using operation of type 2 ($$$x := x \oplus y$$$)?

I hate myself. Due to a series of stupid oversights I spent 35 minutes not seeing a single missing +1 in E, thinking that I verified all possible tests locally

Yes, it's interesting

Thank you, author, for a great contest! Both problem B and C were really cool! C is one of the best problems I solved so far. Sad i didn't have enough time(

I enjoyed thinking about problems D2 and E.

Thanks for the contest!

Amazing contest and Again amazing problem C. I think every contest need an interactive Problem.

What is the error in this code?

The code seems correct for C question, please help me find bug

You should either provide a link or use a spoiler, and you're not even telling us which problem. :(

This might be where it is going wrong. You will need to check whether the two lines actually intersect or not by performing modulo 2, I made the same mistake in my first submission.

I got your point. Thanks

Bro sent the code as a spoiler or as a link

B and C were very appropriate difficulty-wise. Good job.

Amazing problems and huge thanks to the author! Problems involving binary representations have always been one of my most feared type, and D1 and D2 really teached me a lot!

interactive forces ftw

Why am I getting Idleness Limit Exceeded in this Code?

Maybe you don't even output an answer

fvck interactive

In problem D1 I tried to derive what those operations mean.

Let number $$$n$$$ has at least $$$2$$$ digits $$$1$$$. Then we can take prefix of these digits $$$1$$$, and either change them all to $$$0$$$ and the last to $$$1$$$, or change them all to $$$1$$$ and the last to $$$0$$$. All digits after the chosen prefix can be changed to any other without restrictions.

But it turned out, that the intended solution is "we can see that..."

Yup, same (I actually got the solution with 2 operations for one case, but since there were 63 operations, I thought that there would probably be some "change bits one by one" sort of solution).

Are ratings decided based on (no of Problems solved + time taken to solve each problem — incorrect submissions) or is it based on ranking ??

Fast system testing..

In problem B some people have

pre-computed a string of length 30. How they are approaching that problem?It can be proven that after n = 23 there is no combination where you shouldn't use 15 coins. So we always use 15 coins before we get to the 23 (or less) left, where we can brute force the correct combination.

do you have a formal proof for that?

Thank you, interactive problems made my purple handle gone.

After the contest, I realize that I only used 3 operations on problem C, and got choke till now.

B number problem is literally same as the famous coin change dp problem solution of which is also available throughout youtube and other sites. Then how come this problem is unique?People can just use the available code changing the coin denominations!

You can. But u'll get TLE.

Nope, the simple DP won't work, because the limit of $$$n$$$ is too large -- you can't create a table with $$$10^9$$$ elements. You need to find a way to calculate the answer for a large $$$n$$$, which is the core of this problem.

I'm learning basics of dp now like knapsack problems but still in the basic ones so do you recommend trying this problem to learn something helpful ?

D1: 249146196 WA3

`1<<j`

-->`1ll<<j`

249177813 AC

Pain.

Compiling with -fsanitize=undefined can catch these types of overflow errors, just so you know

What is wrong with this code for C?? 249143051

Never mind, I got it, few of my queries were going out of bound.

Why making a invalid query in c gave WA

rating updates ?

Troll

C is harder than D1 imo

B is harder than c imo

How come 9k users solved it?

cheating exist

why am I getting idleness limit exceeded? I have flush after every write, can this be due to my wrong approach? 249177547

sorry to say, but your code is not that clean. Writing clean code is important, as it can save time and make it easier for others to find and fix errors. In general, if your code is messy, people may not even bother to look at it.

Thanks for letting me know, I will try improving on this, any tips?

remove unusual functions and store them to somewhere else. use functions only when it's necessary. In addition, try to learn C++ properly. java isn't suitable for problem solving.

Even though my rating is below 2100, I am somehow not included in the official standings

I have a doubt during upsolving of problem B: Can anyone let me know, what is the difference in my 2 codes and why I get WA on 3 in 1st one and Accepted on 2nd, that feels so weird why dp fails in 1st one

249181823 : My Incorrect Submission

249181977 : My Correct Submission

Lookin forward for a positive response. Thanks <3

First is not correct for cases like 15005 where you use 1000 15s, 3, 1, 1. Instead of 15,3,1,1 use 10,10.

Amazing C !! LOVE MATH. Thanks for this problem setter

What is your solution for c?

If we set the the point (1,1) as fixed and ask(1,1) then we will get the nearest point to (1,1) now one of the following (1,m) or (n,1) must have the same near point no we have

d1 = ask(1,1)

d2 = ask(1,m)

d3 = ask(n,1)

let (x,y) is the our point that can be obtained from d1,d2 now ask(x,y) if the result is zero then this is the point else we have to take (x,y) with respect to ask(1,1) , ask(n,1)

How to obtain a possible (x,y) from two queries you can solve equation of two variables form any two of the following :

d1 = (x-1) + (y-1)

d2 = (x-1) + (m-y)

d3 = (n-x) + (y-1)

You can have a look on my submission that also have some comments that may help you 249181821

upvote if that helps you <3Thanks

Note that the third equation is not correct

It should be

`d3 = (n-x) + (y-1)`

i solved B with this code ,

does this count as brute force ??ps : if i am not allowed to post solution here plz inform me and i will delete itI don't exactly know how your solution works, but I think it's really cool because it works in the time limit and it doesn't involve hard-coding some magic values...

Nice solution. Can you please explain how you did this?

it pretty much generates 'all the possibilities' and takes the minimum of those possiblities, it even calculates the possibility when the number of coins is max lol,

for the base cases :

the loop inside the dfs function will call dfs recursively with what's left of n after taking the

max possible number of coins with current coin (c) k = num //cadd that number to the current number of coins we have (curr+k) and pass that number and what's left of n to coins with value inferior than the current coin, so for example at 3: we will pass the same (what's left of n and curr+k) to coin 1, at 6 we will pass them to 3 and 1 at 10 we will pass them to 6,3,1 and we will calculate until we reach the base case , and update the minimum forthe second dfs call inside the loop dfs(num — (c * (k — 1)), i, curr + (k — 1))it takes care of the possibility where i can replace 1 coin of 15 with x coins , of any coins with value inferior to it and if such possibility provides an inferior curr it will be updated in the ans,like the case for number 98**it better to take 98 = 15 * 5 + 10 * 2 + 3 * 1 = 8 coins , than 98 = 15 * 6 + 6 * 1 + 1 * 2* = 9 coinsThe outside loop that calls the dfs

is for the possibility when the original n is directly divisible by any coin , like the case of 20 , if i don't call dfs in a loop and call it only on 15 or index= 4 in my case it will return 20 = 15*1 + 3 * 1 + 1* 2 = 4 coins, because if i call it only on 15 the 20 will never reach coin = 10 untouched , it will reach coin = 10 with the value 5 = 20 — 15, so i need to also call dfs with 10 as the starting coin,and the original n as the starting value in this case it will return 20 = 10 * 2 = 2 coins and as i said in the start the algorithm will take the minimum of all those possibilities and return it

Sorry if my explanation is unclear , if you have any other questions regarding the solution i will try to answer itFor addressing Problem B, let's denote the solution as f(n). Through empirical observation, it appears that for nearly all n greater than 30, f(n) follows the recurrence relation f(n) = f(n-30) + 2. However, there are two notable exceptions: f(35) = 3, which doesn't align with f(5) + 2, and f(38) = 4, contradicting f(8) + 2.

To tackle this, I adopted the following strategy: I constructed a DP table to compute f(n) for n up to 60. For values exceeding 60, I employed the aforementioned recurrence relation. While I haven't formally proven this approach, extensive experimentation suggests its efficacy.

Through empirical observation, $$$cnt(1)<3$$$ because otherwise we can change the surplus $$$1$$$'s into $$$3$$$.

I have a complain. I have solve Question B & C of today's contest was succesfully run in pretests, but after the contest it's showing runtime error. & submitting the same code after this problem it is succesfully accepted. Please Check, or tell me how it's happened.

C: During Contest & after contest

B: During Contest & after contest

Welcome to the land of

undefined behaviorIn problem B when i = 30, you are accessing sieve[30] but your vector size is exactly 30 (should be > 30)

In problem C you didn't delete the code from problem B and the same thing happens

shittt. I got it,but why there is no runtime error in test 1, it should come at the earliest testcase only. & Please tell why the same code is successfully submitted after the contest.

The thing about undefined behavior is your code will become completely unpredictable

You can try submitting that same code for some more times and see that it might get different verdicts for different submissions of the same code

You can read more about undefined behavior here: https://en.cppreference.com/w/cpp/language/ub

(I know that it's kinda weird that C++ doesn't immediately throw a rte on invalid array accessing, but I guess it's just a quirk of C++ that you have to deal with...)

Also as a side note,

`vector`

has a`.at()`

method and it is guaranteed to perform bound checking (It will throw an exception in case of invalid accesing), so you might want to use it instead of the normal`[]`

operatorhow to report cheating ? have a look.. exact same code.

249197369

[249112538](https://mirror.codeforces.com/contest/1934/submission/249112538 edit : bro I'm new. Why so many down votes :(

Tag mike

That's not cheating, 249197369 was submitted after contest

Get used to it :(

when will the rating change happen?

B can be solved greedily 249152430

.

It's my first comment in pupil, Thanks for an amazing contest <3

I was unrated even though I was purple when joining… Could someone please look into this issue? It would’ve been my best perf by far :(

To much interactive questions, that's not great

Was the name for problem A chosen as a reference to the solution? Taking the two min and two max?

Yeah, after sorting, you can choose i = 0, j = n-1, k = 1, l = n-2, so you can get maximum value.The answer is 2·(a[j]+a[l]-a[i]-a[k])

LoL, this round was a rated for me, even though my rating was >= 2100

The round was unrated for me even though my rating was < 2100.

Feedback on the problems:

A: A typical easy problem, but I don't think it's interesting — just boring casework. There must be an origin if need to choose 3 elements.

B: I don't know why the authors set $$$1,3,6,10,15$$$, still boring.

C: Good problem. Maybe it's not a good choice to place an interactive problem on D2C. Many participants are familiar with it.

D1: Normal problem imo. It's easy to get a $$$2$$$-step solution by doing some case work, do the authors set $$$k\le 63$$$ in order to mislead?

D2: Nice problem. The parity is traditional in games, and combine it with popcount is cool. Also the example is strong enough to check some mistakes. (I got 10 WAs on pretest 1 because of not using

`long long`

)E: Not read.

Can someone help me to find out why it is WA?

The best Div!!!!!

Why C skip? I am afraid of hack, so I make my code long. Submission

T_T

Well, it is strictly forbidden to use

`__asm__`

. In this case, we cannot tell whether the code is copied.maybe your code coped anyone

Code obfuscation isn't allowed, you aren't allowed to intentionally make your code harder tl understand to avoid hacks

My first solve interactive questions in Codeforces!!!

I hope I can be Expert in the next contest

Hoping for the best Div.2 round!

Became Pupil, Thanks for the contest!

As a tester, I enjoyed testing this round a lot! :)

@harsh__h why my code get skipped? mine whole code is written by me why plag then?

what should i do if my code was similar to some others users? System already skipped this...i am sorry for that

Why my code get skipped? i think this was a similar approch. I request an appeal from Codeforces Sir MikeMirzayanov to review one more time of my code...

Is it rated?

It's very interesting contest).