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 |
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!
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
aryanc403 testing back to back contests
About to turn into
aryanc404with 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
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!
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.
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.
with one of the problems having 2 versions One or more interactive problems XD XD
indian setter = mathforces
it was very enjoyable contest
Waiting for problem setters pics
There 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
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 \gt 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 \gt 60$$$ calculate $$$f(n)$$$ using the above formula. I didn't prove, but the results of experiments seemed very promising.
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?
1
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
spent whole contest time for problem C
C was really cool problem
same
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!
What DO you Do in Interactive Problems???? Can someone pls explain
I followed the instructions but still getting Idleness Limit Exceeded
My Code
Thanks!
You have to flush before taking input and after giving output, you're flushing after taking input.
MathForces
XORForces
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.
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.
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
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. :(
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).
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!
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.
D1: 249146196 WA3
1<<j-->1ll<<j249177813 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
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 <3
Thanks
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 it
I 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...
For 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.
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 behavior
In 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,
vectorhas 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
when will the rating change happen?
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?
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?
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.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
@harsh__h why my code get skipped? mine whole code is written by me why plag then?
It's very interesting contest).