Hello, Codeforces!
I'm glad to invite you to Codeforces Round #737 (Div. 2) , which will be held on Monday, August 9, 2021 at 16:35 UTC+2.
This round rated for the participants with rating lower than 2100.
You will be given 5 problems and 2 hours to solve them.all problems were prepared by me and AhmedEzzatG.
One of the problems will be interactive. So, it is recommended to read the guide on interactive problems before the round.
I would like to thank -
Aleks5d, for awesome coordination of our round and suggested one of the problems.
Ahmed-Yasser for help us to prepare the problems. compiler_101 ,Kilani ,TripleM5da , and Omar_Elawady for discussing and testing the problems.
MikeMirzayanov, for the amazing Codeforces and Polygon platforms.
Testers physics0523 , BlueDiamond , Tlatoani ,mahmoudbadawy , Andreasyan , IsaacMoris , Error_404 , Basilhijaz , MagentaCobra , wxhtzdy , Blobo2_Blobo2 , elizkaveta , zetamoo , Muhammed_Atef_Hassan , tdpencil , mcdx9524 , mosemAlanfgar , _Hosam , Bakry , Abdo_Naser , kalki411 , Hemose , Uzumaki_Narutoo , and our VIP tester Monogon.
The statements are short and I have tried to make the pretests strong. I encourage you to read all the problems.
This is our first official round on Codeforces. We are sincerely looking forward to your participation. We hope everyone will enjoy it.
Good luck and see you in the standings!
UPD1: I want to thank Aleks5d for translating statements into Russian and mouse_wireless author of one of tasks.
UPD2: Scoring distribution: 500 — 1000 — 1750 — 2500 — 3000
UPD3: Editorial
UPD4:
Winners
Congratulations to all our winners in the round!
Your profile picture is really good and meaningful.
what about problems' rating? If not a secret
Friend++ :)
Monogon was the VIP tester of 2 consecutive rounds!
Orz!
I agree. Orz me.
Orz Monogon
U don't need to say that ,people by default orz you
he has to, for taking over codeforces(and the contribution).
So much downvotes,that's why i love cf but not cfiians
literally no one asked
As a trainee for the author I am so excited and I am sure that the statements are short XD
keep going from ur trainee.
As a trainee for the author I am so excited and I am sure that the contest will be amazing as the author is amazing XD
Amazing!! It will be such a great contest!
I'm excited! We are in a drought of contests, and I'm itching to compete more.
As a tester, problems are great for the participants who love the short statements and like to gain high ratings!
Good luck to everyone :)
Finally a SA3EDY Round #1، I hope it will not be the last one. keep going our heroes♡♡ ♡‿♡.
Egypt Foooooo2 :"D
T3mya UP
As a very cool tester, I would like to say that the problems are nice and the pretests are very strong. I think you'll enjoy doing this round.
So, shamelessly give me contribution.
commenting again instead of editing, double contribution, smart move xD
with the power vested upon me as a tester, I hereby declare thy contest interesting.
Though I'm not a VIP tester, I tried hard testing as much as I can.
Yes, I can assure that you did a great job.
What's the difference between tester and VIP tester?
VIP Tester is supposed to get more contribution than normal tester.
No.. VIP tester is the one who follows 1-gon and of course, was a tester. Normal testers are those who still don't follow 1-gon.
As a contest tester for the first time :), the contest is great and joyful.
I hope you will enjoy it ;)
Someone explain me why the time of this post is showing like 2 days ago ,although it is just posted like 1 hr before i guess
It's going to be a great contest :)
As a trainee of the author i am sure that the problems are epic, Good luck
Give me and my coach contribution :)
I decided to write the ultimate "as a tester comment" since this is the first and hopefully not the last time to be a tester of an official round (except of course if you count #716 #717).
1) as a tester add me to your friend list
2) as a non-VIP tester I hope I can be a VIP tester one day
3) as a tester I assure you that you should give my friend mo2men contribution
4) as a tester... (recursion ;) )
5) as a tester I advise you to read all the problems
6) as a tester I think you should prepare everything you'd need throughout the round because you won't be able to move or blink during the round
7) as a tester this round is pure awesomeness (kung fu panda 2008 reference)
8) as a tester of this round I would like to test upcoming rounds... maybe the next is yours? who knows
9) as I am 50% of the specialist testers population in this round help me by upvoting this comment
10) as a tester I recommend everyone to eat jilaty (ice cream in Arabic)
Note: the profile picture was taken by my friend and the author Mo2men in the Arab collegiate programming contest 2020 (ACPC)
I think you forget to say as a tester (◠‿◕)
Blobo2_Blobo2 u seem like :
ahm 7aga el jilaty ana megahez 3lba fe elfrazer XD
well deserved upvote xD
bruh when you will be a tester again what you will write those are all the "as a tester" comments human invented
cant be proud more my friends keep going [user:IsaacMoris][user:Uzumaki_Narutoo][user:Blobo2_Blobo2] i sure the contest will be so beautiful ♥♥
;)
As a tester give me contributions.
i know this tester and he is the best tester and setter i have met keep going my coash
tdpencil has hacked few of my solutions in the past, so for me he is orZ. yeah!! this orZ has curves.
تحيا مصر ❤️
Wow you really host a div-2 contest when you are just specialist. ORZ
Rating is just a number.
Also, this man was a problem setter in the Arab collegiate programming contest (ACPC) 2020 and a coach for many CP students, these students are now experts and candidate masters.
True Rating is just a number .
P.S. if you have good contacts xdddd
Yes, rating is just a number. You're right.
Bro ,but you have announced to become CM in 2 months ,so for you it's pride now ,best of luck
There are still 8 weeks to go bro.
There are just 8 weeks to go bro :)
I want to get CM too in 2 months, lets race to CM :O
I am in too
I just hope I can become a "Pupil" through this competition.
Bro, you are solving 1600 and some 2000+ level problems! you deserve more than that for sure
But I can only solve 2 or 3 problems in Div.2.I am too poor and I am only Grade 6 as a Chinese.
Ahh......I'm too low to solve div.2 .I think I need to do more div.3.(Rank 8000+)
You are in grade 6! I am in my third year of CS degree and still able to solve 3 problems div2... so you are much better off cuz you have so much time at hand! Relax!
Wait,what does "CS" mean?University?Or middle school?
computer science...
Thank you!But I often call it OI.
No, oi is the short name for "Olympiad in Informatics". CS is computer science which is the name of a major in the university.
小盆友加油 (ง •_•)ง
You are also a Chinese?So how many problems should I solve in a normal Codeforces Div.2 if I what to get tg1=?Or I need to solve Div.1?
当然，我知道tg1=肯定得等初二左右了...
Of course,I know that I should wait for 2 years if I want to get tg1=.
I start very late you see.. I am still a newbie now.. When I was at your age, I was playing mud back in the school yard and knew nothing about OI. So your age and your time are the most valuable thing. Try to solve more problems. Hope you will be the next WJMZBMR :)
First,you were a specialist. Second,my mother says that if I can not get >=300 marks in CSP-J and tg2=,she will let me to be a MOer.But the thing I like is program ,not that complex and annoying math.(Maybe I am extreme,but I hope you can understand what I mean.)
UPD:My highest prize is CSP-J 2= 135 marks,so it is a hard task for me.That's why I want to enhance my strength by CF and Luogu as fast as I can.
I am going to be Grade 9 now,and I got tg1= last year.You still have long time to study,so I don't think you need to worry about it.I was only a Specialist when I got tg1= :) To the honest,getting a tg2= is not difficult,you can even use brute force to get tg2= easily :)
Hope to become "Pupil" through this contest.
Good luck to everyone!
As you get ready for the contest, I wish you all the best of luck
Most valuable advice ❤️❤️
As a tester ,please orz this guy with a lot of upvotes ,otherwise he is gonna comment frequently for getting upvotes.
P.S. just kidding but upvote him.i was the 1st to do so :)
feels like ages since the last round it's like all problem setters are on a vacation or something
We are so proud of you all , keep going :")
Auto comment: topic has been updated by Mo2men (previous revision, new revision, compare).
I will reach pupil in this contest.
Thank You
I am so excited to participate in this round, hope everyone will gain rating
From the score distribution, it looks like it's going to be speedforces for A, B, C.
Lol maybe for high rated people like you it may seem as speedforces but i don't think that guys like me feel so :).best of luck
I sense more like AB speeforces
I missed the part where that's my problem.:)
P.S. just kidding bro .i do feel the same bruder ,best of luck
Author revised the score distribution. Previously it said C was 1250 points, that's why I included C as well. Now it looks better.
Auto comment: topic has been updated by Mo2men (previous revision, new revision, compare).
whenever specialist expert makes a contest they always make it hard. If u are actively giving contests u know what I mean. They think it's cooler to make a harder contest. These pathetic nerds cant solve the all question themselves.
Your Comments suit your Name!
He is true. This round is awful. Tests in E are so strong that every wrong solution can pass it ：)
Do they have better ideas？They got a interesting idea（problem E) and some "strong" tests.
Bad ABCD，real “speedforces”. The worst round I've ever seen.
Finally，thanks the writers for this "wonderful" round ：）：）：）
Short problem statements, thats what we wanted
I always used to think that to increase rating one have to solve more and more problems. Mo2men has solved more than 2000 problems then why his rating is not increasing ( ･᷄ ︵･᷅ )
Maybe mo2men cares about solving problems more than having good ratings! ¯\_(ツ)_/¯
But still +delta motivates a lot
i hope i can get top 10 in this contest
This is what you call stalking*100
i hope i can get top 10 in this contest,too.
https://www.youtube.com/watch?v=9tIFSo_bEVY&list=RD9tIFSo_bEVY&start_radio=1
Oh interactive, is this binary search ? :V
May or may not be, interactive problems need not be always binary search always :)
I know, this is a joke
Looks like today their ll be more of a number theory problems.
How do you know?
just guessing bro .
As a participant I wish to gain some precious contribution through this comment.
Please take good care of this precious contribution that you've received.
nope :D
will be unbalanced contest , I can bet
see I already said, unbalanced round, still got downvotes
Your prediction really comes true :(
hope that a and b will not be interactive
Last few days I faced a lot in my life, Can't reveal what exactly happent. But you can assume that the sadness is as same as when you lose your father or mother or see them cry.Couldn't give last 3 contests with proper emotional and mental strength.But skipping a contest has never been an option for me.It's the only thing I have in my life to live for.I will try my best today.Good luck to everyone too
Come on bro! It's only a part of the life. I hope you can come out of the gloom and step into the light as soon as possible.
Yes!!While there is life, there is hope...If the great Stephen Hawkins figured out life even after getting paralysed,Hopefully I can too.
Is it just me? getting a TLE on tc2 for problem A
Yeah, I got it as well. It's a stupid question. Finally figured out the problem.
My O(n) got tle! Anyway good luck to you for rest of the contest.
My O(n) got Ac.But I'm afraid of getting FST :(
Remind me when I'm trying to take part in another weird round and get negative delta
Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if |a−b|max(1,|b|)≤10−6. How to achieve this in Java ??
use double, It'll take care of it automatically (if your approach is correct).
Why the gap between C and D was a lot ?
toxic:(
check his original comment
How will you know the balance of the questions if you only solved A?
Original comment : fuck you with your fucking unbalanced contest
You can look at the gap of D and C in the standings after system tests :)
Why even care when you even can't solve B? Your toxicity is full of shit
First experience of being able to do B but not A XD.
giving combinatorics without some relatively big testcase — unethical:/
ll n; cin >> n; ll k; cin >> k; vector<ll>arr(n, 0); for (ll i = 0; i < n; i++) { cin >> arr[i]; } ll sz = 1; for (ll i = 1; i < n; i++) { if (arr[i - 1] > arr[i]) { sz++; } } if (sz <= k) { cout << "YES\n"; } else cout << "NO\n";why I am getting wa for this..its the correct soln
you are asking this during contest thats what you doing wroong
give logic atleast
Dude, you don't ask for help during a contest!!
I just erased my whiteboard 5th time full of test-cases for C and yet I am unable to decipher. I am almost sure it's gonna be a one-liner but I just can't figure it out :(
I think the gap between the problems is too big :(
plz answer me a question whether you like the weak samples just because you think they're cool???
My D is failing pretest 4 though :P
Seeing so bad testcases for C, its impossible to know if the solution is even remotely correct. All my submissions passed the samples and failed pretests.
It's not tough to write a brute force solution for C to verify.
Very relatable.
What did you do to fix it?
I just added more parameters into my segmentree nodes and it worked. (Previously I used a set to maintain values.)
Wait, like I should compress values with some more like $$$l - 1$$$, $$$l$$$, $$$r$$$ and $$$r + 1$$$ instead of just $$$l$$$ and $$$r$$$? If this is the case I'll be sad for another few days :P
No, I think I did the same thing as what you did, but instead of keeping the max values in the segment tree, I used minimum values, but I have no idea whether your approach is right or wrong, because I iterated through the rows from 1 to n, not n to 1.
How the hell are 2500 people able to solve C
I'm also wondering this too... So overall I'm too weak...
Telegram I guess
What do you mean?
Cheater , not all but some
My might fail in sys test, I checked the submissions of the people in my room and all of them have similar code but completely different logic than mine....Hope the pretests are strong
I think about this issue like this :
Consider sequentially from the high binary bits to the low binary bits.
The i-th binary bit can be "decided" or "undecided".
Decided means that the i-th binary digit a1 & ... an is already greater than a1 xor ... an, and no subsequent comparison is required at this time.
Undecided means that the value of a1 & ... an and a1 xor ... an can be compared after the i-th binary digit.
Undecided includes two situations : - n numbers are all 1 in the i-th binary digit and n is an odd number. - At least one of the n numbers in the i-th binary digit is 0 and there is an even number of 0s.
Undecided means that all n numbers on the i-th binary bit are all 1 and n is an even number.
The final answer is composed like this ：
my code like this
shitty problems, bad balance and there are only 5 problems AT ALL
How to solve C?
Am I the only one here who had 2 penalties because of ignoring the fact that $$$-10^9 \le A_i \le 10^9$$$
I got soo many wrong answers on B because a[i] can be 0. Why they didn't make a[i] permutation of length n? Anyway, I think that problems were ok but samples and these constraints were horrible.
I had the exact same issue, I got first WA because $$$A_i$$$ can be 0 and 2nd WA because $$$A_i$$$ can be -1
Weak sample for C :(
In div2 B i was rearranging the elements inside subarray for half an hour.
Sad noises.
Same I did , for around 10 minutes.
I liked B it wasn't clear why the simple solution is not working but C is so hard still a good problem though I will try to solve it later
Why did the simple solution not working in B?
1 3 2 <- try this test case
consider this case
4 2
2 3 5 4
simple solution output Yes but it's a No cause you need k=3 you can't put 4 in middle 2 3 5
I compressed elements to 0 to n-1 and checked if a[i] — a[i-1] == 1.
Is there another way to solve problem D instead of using a dynamic segmentree, curious -.-.
As long as the queries are not online, you can (almost) always use coordinate compression and use a normal segment tree.
UPD: my bug was that I had to declare the Segment Tree Array with
8nelementsContrary to popular belief, I liked problem C. A good question based on bit contribution and combinatorics.
Even though I couldn't solve it but it indeed feels like a good problem. I hope to learn something great from the problem
So i had this idea and observation for problem C:
For every number >= 1 times that it occures must be even. For example: 02211, 02222, 22110 etc. Total number of possibilities that pair of numbers can occur is n*(n-1)/2. There can be n/2 pairs of numbers in array, so total number of posibilities for 1 number is n*(n-1)/2 * n/2. Multiply this by amount of numbers: (2^k) — 1 * (n*(n-1)/2 * n/2). There also can be n same numbers that make problem condition true. So i also add 2^k to answer.
Can someone told me if that make any sense :D? Thought that would work but it didn't :/. Maybe it was only right for small numbers dunno
Misses cases like [1,2,3] e.g total xor = 0 total and = 0. Also misses the idea if n is even you can set the leading bit to 1 in all values and set all other bits to any values.
Interesting problems. Is D a segment-tree problem? I think I could solve it if only I could implement a generic segment tree.
and btw. why a * b % c == (a * b) % c and a + b % c != (a + b) % c :<
operator precedence
I know i know
%has the same precedence as/, anda + b / cwouldn't be(a+b) / cnow, would it?How to solve problem D . I think it is similar to longest increasing subsequence problem in a way $$$a[j]>a[i]$$$ if $$$j>i$$$ and $$$ j^{th}$$$ row and $$$i^{th}$$$ row have some common intersection . I tried to use segment tree but could'nt implement in time
Very clever to do tests with k = 1 and k = 0 on a combinatoric problem! Good job!!! Don't do any other contests please.
There aren't any corner cases.
Why in problem A a hack with: t = 1,n = 10^5 and all a[i] = 10^9 gives invalid input?
I spend about 1 hour on D......the solution is easy but it's hard to code :(
Cant' agree more.
How to solve D any hints? do we construct some kind of graph?
use dp
Segment tree with DP is what I did. First compress all intervals, so that we can fit a normal segment tree in. Let $$$dp_i$$$ be the minimum number of rows we have to remove to make rows $$$1~i$$$ good, and keeping the i_th row. Then the dp recurrence is pretty simple: $$$dp_i = min(dp_j)+i-j-1$$$, where (j<i). We can rearrange the formula into $$$dp_i-i=dp_j-j-1$$$ then we can keep the value $$$f_i = dp_i -i$$$ in the segment tree. For the segment tree, we update the ranges of ones of that specific row with $$$f_i$$$ and for the queries to check the previous rows for the dp recurrence, we also query only the ranges where ones are located in the i_th row.
I think the examples of the problems are so easy that it makes me be not able to find the bugs.
I just loved $$$E$$$. Nice puzzle. Here's a small hint for those interested:
Say you try to trap the king in a rectangle and slowly try to make this rectangle smaller. The issue here is that the king might escape this rectangle if you reach it's column or row. To avoid that, can you try to keep the column parity and row parity of the queen and king different after every queen's move?
Okay, as the editorial solution is entirely different, I will describe my solution here (which I liked better).
Let's say you are at $$$(1, 1)$$$ and you don't know exact current coordinates of the king, but let's assume they are both even and it's the king's move now. We will try to maintain that the king's coordinates are both always of parity different than the queen's after our move.
In the king's move, the king will have to change the parity of either it's row or column or both. Whatever he does, we maintain the opposite parity of both the row and column, moving towards the king. Specifically, let $$$dx$$$ be $$$1$$$ if and only if the king changes row parity and $$$dy$$$ be $$$1$$$ if and only if king changes column parity. If we are at $$$(x, y)$$$ right now, we move to $$$(x+dx, y+dy)$$$.
Note that we never stay at the same place. Also, note that we never match the king's row or column. This ensures that the king remains trapped in a rectangle, whose size we keep reducing. We can see that in at most $$$12$$$ moves, we definitely trap the king.
But, this is all fine considering the big assumption we made about the parities regarding the king's initial position. How do we trap the king without this additional info? The trick is that we can repeat a similar process assuming all the $$$4$$$ different possibilities for the king's initial position, with small changes.
Overall we take at most $$$4 \times 12$$$ moves to trap the king over all attempts, and at most $$$3 \times 2$$$ moves to initialize the condition based on assumed parities for the next attempt. Thus, we need at most $$$54$$$ moves.
Code: 125400662
First of all convert all the given ranges to <= 6e5 by hashing. Let's take an array dp with size of the maximum value in ranges and iterate rows from 1 to n. dp[i] indicates the maximum length of the rows taken in the grid where the last row contains 1 at index i. Now for ith row we need to find max(dp[k]) where ith row kth column contains 1 and we need to set dp[k] = max+1. Finally the answer is the maximum value in the dp array. You can do backtracing similarly to find what all rows we should take. We can use segment trees with lazy propagation for range maximum and range set queries.
I’m getting WA on Test Case 4 with this approach :(
Yeah, I also got that first but I found the bug in my implementation and corrected it.
My solution on E seemed to read a direction other than the ones described in pretest 3. It's likely I got a bug somewhere, but did anyone notice any similar weird behavior, because I can't seem figure it out?
Edit: Found a bug and got AC, still not sure what my program managed to read after producing a wrong move.
How to solve C?
For ith bit let the win be b[1]&b[2]...&b[n]>b[1]^...^b[n] and draw be b[1]&b[2]...&b[n]=b[1]^...^b[n] where b[j] is the ith bit of the jth element. Let dp[i] be the answer till ith bit (all elements < pow(2,i). Iterate from 1st bit to kth bit
if i == 1 => dp[i] = number of ways to draw + number of ways to win for ith bit. else => dp[i] = (number of ways to win for ith bit)*(all possible values before ith bit = pow(2,i*n)) + (number of ways to draw for ith bit)*dp[i-1]
dp[k] is the ans.
Your example is so stronger that every wrong code can pass!
Weak example,STRONG pretest.
What is the problem with MLE pretest 4 in Problem D? Was I the only one to struggle with this?
I used a lazy segment tree to build a graph then found the longest path in an acyclic graph. You only need to add an edge to the nearest row that intersects with your current interval. Is that approach wrong or what?
Edit: NVM, FeelsBadMan
Got TLE on C because of 32-bit python.
Very annoying.
nevermind
why you bully me , codeforce ?
What the fuck? I randomly submitted this pattern in E and it passed pretests.
(Edit : It passed system test)
This solution made me feel disappointed :(
And now you will become CM XD. Congrats
and now it's Accepted. wtf
This might be somehow the solution..? Main test had 7000 individual games and it all worked.
Nope. It's wrong. It's just hard to make an opponent to counter all such solutions I guess.
Maybe because the opponent isnt an AI that makes its move optimally, but instead it makes its move randomly so the probability will be so low to fail?
I really really dont think so because when you are on (2,1) and go to (3,1) i can be on (3,6) then move to (2,6) and then to (1,x) and its over. (1,1) is the point in the upper left corner.
And it turns out to be AC in main test.
I can think of a test case where this solution doesn't work. The system tests are weak.
If the gif doesn't work, go to here
ok
I just continue to go in reverse path and it passed main tests. Indeed the solution above fails only last test.
Nice round guys, I enjoyed the problems :D
AhmedEzzatG Mo2men
How to solve C? It looked like a DP-Tabulation type of problem, but all I could figure out is that
$$$dp[n][k]=(2^{n-1}+1)^k$$$ when $$$n$$$ is $$$odd$$$
Let $$$p = 2^{n-1}$$$. Then the answer is
$$$\begin{cases} (p+1)^k & n\ \textrm{odd} \newline \dfrac{\left(2p\right)^k+p\cdot\left(\frac p2\right)^k}{p+1} & n\ \textrm{even} \end{cases}$$$
How I got it:
I brute-forced many small values (my brute force was $$$O(n2^{nk})$$$ and worked well enough for $$$n+k \leq 12$$$ (took only 80 seconds with pypy!). I immediately noticed the powers of $$$5$$$ and $$$17$$$, and checked for $$$65$$$ and $$$257$$$. For the evens, I noticed that $$$\textrm{ans}(2,k) = 3\cdot\textrm{ans}(2,k-1)-2$$$. I plugged this into Wolfram Alpha and got that it was $$$\frac{4^k+2}3$$$. Then, I tried brute forcing expressions in the form $$$\frac{a^k+b}c$$$ for $$$n = 4$$$, but found nothing. Then I tried changing the expression for $$$n=2$$$ to $$$\frac{4^k+2\cdot1^k}3$$$, and checked that form of expressions, and got $$$\textrm{ans}(4,k) = \frac{16^k + 8\cdot7^k}9$$$. From there I generalized it.
The modular exponentiation makes the time complexity $$$O(\log n + \log k)$$$.
Also, looking at submissions of random people, I've seen at least 4 different solutions other than mine (though they're all about $$$O(n+k)$$$, so mine is faster), so there are many ways to solve this problem.
even is $$$\frac{\left(2^n\right)^k-\left(2^{n-1}-1\right)^k}{2^{n-1}+1}+\left(2^{n-1}-1\right)^k$$$.
Video solution, you can also convert the recurrence into a 1D DP (DP solution).
I'll probably fall to Specialist, but I really loved this round! Problem C was interesting, bit-manipulation and combinatorics puzzled me oh so good.
Kudos to the entire problem-setting team!
Can
Cbe solved using DP?I tried to implement via a 4-D dp
dp[i][_and][_xor][eq].At the
ith bit (out of k), I have 4 ways of assigning bit combinations to the_andand_xorvalues ->0 0,0 1,1 0,1 1, andeqcan be 0/1/2, denoting whether the&cumulative value until theith bit is lesser, equal or greater than that of the^cumulative value. Couldn't implement the combinatorics part for each of the combinations in time. But, would this solution work?Clean dp:
not sure what I have done dp:
Count cEven the number of ways to pick an even number of 1's in an n-bit number. Then do dp on the most significant digits: if n is odd you have dp[i] = dp[i-1]*(cEven+1) (+1 is the case of all digits being ones). The second term is the number of ways the first digits can be equal. If n is odd then dp[i] = dp[i-1]*(cEven-1) + 2^(n*(i-1)). Here the second summand is the case of the first digit of the AND being larger than that of the XOR so any combination of digits other than the first works. The first summand is the digits being equals (you remove 1 because if all digits are 1 then there are an even number of them but then the AND term is larger). You can precompute the powers of 2 mod M as n is always the same.
great contest
k = 0 should always be 1 independent of n. I think it's more about them screwing with you and putting k = 0 as a valid test case at all than anything else
Well, it seems there is some disrespectful comments. Please respect the setter. For me C was good problem, and although I couldn't solve, E was also interesting. Thanks for the contest.
one of the most balanced div 2s ever. Kudos to the authors !!
I thought constraints to be different for C, so I solved it for $$$T <= 10^5$$$.
$$$ans = 2 ^ {N*K} - loss * {(L ^ K - 1) / ({L - 1})} * draw ^ {K - 1} $$$
Where
$$$L = 2 ^ n / draw$$$
Draw is the number of ways in which $$$N$$$ bits can be set such that $$$cumulative and = cumulative xor.$$$
Loss is the number of ways in which $$$N$$$ bits can be set such that $$$cumulative and < cumulative xor.$$$
Code: 125392751
I wrote a solution of C but it was giving wrong answer on test case 2. Can someone explain what is wrong with the logic. I used 1-d dp. dp[0]=1 and for i from 1 to k - When n is even, dp[i]=2^(n*(k-1))+(2^(n-1)-1)*dp[i-1] - when n is odd, dp[i]=(2^(n-1)+1)*dp[i-1]. here is the link to my code
Here's my code full code: https://codeforces.net/contest/1557/submission/125410342
wth man. I think my code is exactly same as yours. You just used recursion and I used loop then why on earth it is giving me wrong answer!!!!
When n is odd:
Because there won't be any case such that a1&a2&a3.... > a1^a1^a3
Max, they can be equal.
Proof:
For a1&a1&a3 to be greater it needs to be all 1 at some ith bit (1&1&1) but at the same time, 1^1^1 will also be 1 therefore we conclude a1&a1&a3 can never be greater than a1^a2^a3
Ya I get it sorry I changed the comment I think both the codes are same!!!
here's using loop :
https://codeforces.net/contest/1557/submission/125409932
Ohh man I wrote k in place of i in the even case (2^(n*(k-1)) that should be (2^(n*(i-1)). Really disappointed by this type of typo :( otherwise, code was correct:( By the way thanks for helping buddy :)
Could you elaborate on your logic?
You need to consider 2 cases.
if n is even:
if we are the kth bit we have 2 options
Either we put bits in such order that 'and of the kth bit =1 and xor=0. For this bits at the kth position of all numbers needs to be 1 and the rest for (0- k-1) bits we can put any sequence of bits that will be equal to modpow(modpow(2,k-1),n).
or, we put bits such that 'and' and 'xor' both are equal for that (number of 1 bit == no of 0 bits) or all bits ==0 and then recursively call for (n,k-1)
if n is odd:
Nice round and keep going, guys :) It is sad to tell nowadays that many CF members don't like any problems, neither easy nor hard. They only like complaining and staying in comfort zone.
I just want to know HOW MUCH dollars did you get from these writes？
I don't think a man can say these words after participating. How dare you to comment these f...ing words without your brain. ：）
If I can earn dollars by posting comments like you，please tell me. ：）
Finally, I wish the author and you a long life, a happy family and good health. Thanks a lot :) :) :)
May you get the most downvotes anyone has ever received!
Thank you :) I just want to earn money like you guys :(
If they aren't able to write a contest,please go to problemset and practise more,rather than giving us five naive problems. :)
you are a div1 alt....go and participate in div1 if u have balls
I have participated in div1.... But it has nothing to do with "div1". Anyway,this round is awful.
Having participated myself I want to say that this round’s truly not-so-good. Have myself puzzled throughout the contest.
Had,not have. Sorry:)
Tell me,why do you think this round is nice？Say a reason rather than hurrying downvoting me.
Or you guys just want a interesting problem that you can accpet by printf("rand()") ，or four problem that has been written years ago？
Why do you lovely guys participate a codefoces round？To solve five cute naive problems and get nothing？:)
at least we dont have the server down this time so calm down
One good thing about this contest is that I didn't face any lag today. The system was pretty smooth for me. The difficulty level of problem D was a bit on the hard side than a regular Div-2 D, to be honest. Overall, had a good time brainstorming. Thanks Mo2men & AhmedEzzatG for the contest.
What is the answer for this input in problem C: n= 1, k = 0. In my Accepted submission, it is 1. But I saw an accepted submission where it is 0.
https://codeforces.net/contest/1557/submission/125390194
I guess the setter didn't include this test in the system test.
1
https://codeforces.net/contest/1557/submission/125390194
This accepted code gives 0.
Weak system tests ig
K>=1
UPD: K>=0 Looked at the wrong problem. My bad.
No it clearly says $$$0 \leq k \leq 2\cdot10^5$$$
https://codeforces.net/contest/1557/problem/C
And the third sample case even has $$$k=0$$$, so idk what you're talking about.
Mo2men MikeMirzayanov Sorry for tagging.
Why the verdict of my submission is still Pretests passed? Problem B
Lol
I have the same problem too, please rejudge!
why do tled guys not retested? seems like some correct solns for problem A got TL
They got TLE as they used double/long double to take input
if they take int/long long to take input they will pass
https://codeforces.net/contest/1557/submission/125409517 (77 ms with int)
https://codeforces.net/contest/1557/submission/125406647 (998 ms because of long double)
998ms still passes, but on systests it wouldn't pass
A bad round:((((((
Yes I agree.
Feedback for authors -
Personally, I didn't like "Left", "Right" etc as King's movement. Giving dx,dy would have been nice.
I did spend a good amount of time hardcoding direction to dx,dy twice. After hardcoding once I realised
switch(s)in C++ only accepts integers. Then I had change switch to map.I completed the code in the last 5 mins and even after that it had a bug with one specific direction and would have costed an AC.
Authors have just detected if you are able to write easy-to-debug/support code
Trying hard to learn/write easy-to-debug/support code. Thanks for the tip.
I agree that it's important to make the problem statements in such a way that people can focus on the problem solving aspect, without getting too caught up in the coding "boilerplate".
But this is competitive "programming" after all. Maybe it's just me, but I don't think it's bad to focus on the "programming" aspects from time to time ¯\_(ツ)_/¯
From HTI thanks Assiut university for the great ICPC community you made :)
I know I have poor abilities, but
How CRAZY the weak examples are!
Gave this round could only solve 2, but expected I would at least not be unrated anymore. Why am I still unrated?
wait for a few hours
My solution for problem B remains the verdict "pretest passed". What's happening?
My solution for problem A got TLE on test case 2 on system tests (https://codeforces.net/contest/1557/submission/125328000)
After submitting the same code after system tests, it got AC (https://codeforces.net/contest/1557/submission/125407093)
If its possible to rejudge my submission, please do so.
UPD : Submission got rejudged and got AC!
Your code passed with 998ms / 1s, so it is very risky to submit the soln. Though I don't know what caused the TLE in you code... I see no issue.
Maybe sorting the vector with 300,000 elements caused the TLE?
reading long doubles is slow, also it's common practice to retest some tled submissions after the contest, because of server load
Printing floats with 20 precision. Just reduce it to 8. I too sorted but ACed in less than 100 ms.
What if it continues to get tle
I think I had a similar situation during the contest.
TLE2: 125363145 (reading long double), AC: 125364892 (reading long long), AC after the contest: 125409423 (reading double using scanf).
They are all the same solution, but it cost me $$$-50$$$. I can't figure out why :(
I don't understand why my solution to question B is still showing me a pretest passed . I think it was not evaluated by the system . please tell me what to do.
??? I wonder how this can be accepted 125408147
It just move like this ↓
And this worth 3000 points, the sum of Problem A, B, C.
Just realised it's an interactive problem that supports hacking and there is no "Hacking format" section.
Also, the problem statement doesn't mention if this problem is adaptive or not. It would be interesting if someone comments one can't hack this submission as well.
Guessing hacking format from "Input" section in test cases and making one unsuccessful hack to validate hacking format I'm even sure one cant even hack any submissions because hacker cannot even control king's movement.
The ideal format would have been hacker printing 131 king position with which interactor would have used to move king instead of hacker just supplying initial position and checker making decisions on rest 130 positions.
Reasonable. It's more ideal if we can use custom interactor to hack in adaptive problems. Although no one can finish writing it during the contest lol.
just realized this picture is from an earlier comment lul
I'd say that the problems are not too bad,because for me the first 3 problems are pretty ok for Div2 ABC problems,and E seems interesting.
The examples are kinda weak but i blame myself for not double checking. Also the tests in C and the interactor in E is weak,letting some incorrect solutions to pass.
This is the best round I have ever seen, I can hardly imagine a round with a perfect balance and difficulty, the level of the authors is quite high, all levels of coders were able to get a perfect round, I felt physically and mentally happy when I played this game.
The questions in this cf were very interesting and I learned very many meaningful tricks from them, the difficulty slope was very reasonable, the sample coverage was very wide, and I even got a pass on the sample that only made the code pass.
What I admire about the author is that he has the courage to submit this kind of contest for review. If I had come up with such a topic, I would have been ashamed, but the author is open and honest, a real gentleman, he is the best courageous person I have ever met, bar none.
When I clicked on the leaderboard of the contest, I even wondered if I had clicked on the rating list. other low quality contests had purple and grey in the leaderboard, but in this contest, purple, blue, cyan and green were clearly defined, which made me admire the author from the bottom of my heart.
Finally, I wish the problem setter a long life, a happy family, good health and a speedy recovery from the loss of his mother.
Although I haven't been online for a long time, I still heard about this f**king round. This article is very 'left', but I like it
Yes commonly I'm a gentle girl but this round really annoy me.
Can’t agree more :) The contest is so perfect that I even used my rating drop to gain contribution :)
I've seen a lot of words spouted about the rounds, but I haven't seen such euphemisms.
Solution to E that passes tests with a limit of 21 queries per test case. 125414030
Deleted
Hey. Your code is correct but somehow taking lot of "doubles" as input is affecting time and hence TLE.
Take int as input (very fast) and cast them to double, still your code works.
i.e int x; cin>>x a[i] = x where a is "double array" it will pass.
proof:
include <bits/stdc++.h>
using namespace std;
int main(){ long long tt; cin>>tt; bool show = tt==3; while(tt--){ long long n; cin>>n; double a[n] = {0.0}; for(int i=0;i<n;i++) {
//3 "show" int c; cin>>c; a[i]=c;
/* only 2 "show" cin>>a[i] */ }
if(show) cout<<"show\n";
sort(a, a+n, greater()); double ans=0; for(int i=1;i<n;i++) ans+=a[i];
int temp=n-1; ans/=temp; ans+=a[0]; printf("%.6f\n", ans); } }
Above prints only 2 "show" for 2 test cases, indicating that TLE happened while taking input od 3rd test case.
replace
Thanks for the help...understood it...taking input a double value takes longer time than int...so we should avoid it if possible :)
It seems, you are using cin, cout which is pretty slower. And your execution time is significantly depending on I/O. If you use faster I/O (like scanf, printf), I think it will pass with double. FYI, Please just don't paste codes here, just link the submissions next time. :D
nice problemset, hard and interesting
Out of curiosity, how did problemsetters create interactor for problem E? Seems hard.
Not very well clearly, looking at the amount of wrong solutions that passed. The absence of a note on whether the interactor is adaptive, and the even more egregious absence of an explanation on how hacks work on the problem were red flags suggesting that the preparation of E was somewhat sloppy IMO...
To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
Mike how can someone tell the authors Fu** you and his comment doesn't get deleted and he doesn't get penalty is everyone on codeforces on a vacation
Everyone in codeforces doesn't have time to read every comment in every blog, unlike some people.
Lol that's the contest blog such a comments always gets deleted
Good conpetition.But it's a pity that I miss it.
i don't think that this is a good round, and i don't even understand why you think it's good round.
I was hopeful about this race before it even started, but after the race, I thought this race was not a good contest.
I am curious why you think the contest was bad?
One of the few problems I have seen was that the checker of E was not very solid, allowing lots of random solutions to pass, luckily, it didn't impact the official standings that much since only 6 people in the official standings solved E and I doubt that reason was the primary cause of complaints by DIV2 participants.
Another reason that comes to my mind is that the samples for C weren't very strong, but otherwise I found the problems, at least A-C, elegant, in terms of the thought-process. Also, I couldn't find any Failed System Issues in this contest? Neither did I find any issues with the statements
What is the deal with a lot of people complaining? Is it just a lot of people ranting who weren't satisfied with their performance?
Well, B was "simple problem hidden behind complecated statement". I am sure most of the participants who did not solve the problem immediately are upset about it.
well, perhaps my words were too strong, i'm sorry about that.
first, the samples are too weak; second, the 5th problem's data is very bad, allowing lots of random solutions to pass;
i'm sorry to say this without careful analysis, but seriously, i dont like this round.
I think you'd better evaluate the contest after reading the problems!
It's really a GREAT CONTEST!!! especially THE EXCELLENT INTERACTOR of problem E!!! :(
However, strong pretests ≠ weak example... :(
and not equal to weak system test too.
Problem 1 have very obvious samples, some examiner doesn't realy understand it's principle but can accpect very quickly(true, include me ^_^).
In China, OIers have 'cordial greetings' to the people who write the questions
Nice round and Nice music!!! https://www.youtube.com/watch?v=9tIFSo_bEVY
I think the strong present tests $$$\not =$$$ weak samples.
How do we compress intervals in D ?
Can you give me the reason for the weak samples and the weak system tests of problem E?
[deleted comment]
Nice,I failed.I am still a newbie.
Try in the next one.
why am I unable to open the editorial. It's showing that you are not allowed to see the requested page.
Same. What happend?
I just gave the virtual contest
Actually I think this round is not that bad. Problems except E are in normal range of difficulty. Why are many people annoyed? I think there're only a few contestants affected by E for the fake solution. As for the weak samples, there's no obligation for problem setters to provide strong samples.
i dont think so. i think the strong example is an important part of a great contest.
Actually, one important skill for competitive programming is that you need to find the error of your code by yourself, without depending on the samples. Meanwhile, the function of the sample is not to check whether your code is correct or not, but to clearly describe the problem.
Что за хрень такая? Нажимаю на разбор задач, выдает что не достаточно прав для просмотра страницы. Что делать?
What the hell is this? I click on the analysis of tasks, it says that there are not enough rights to view the page. What to do?
"You are not allowed to view the requested page" Why you do this :( ?
I think they want us to solve the problem ourselves.
I am unable to access the tutorial of this contest. Why is this happening can someone please help.
Can someOne please tell me what will be the answer if we slightly change the B problem.
change: you can also reorder the subarray elements & still we have to make exactly K subarray.
I found it so hard for me because it took almost 1 hour for me & I couldn't solve it. after that, I read the actual problem then solved it, but here I am more curious to know the modified problem solution.
I think it becomes a good problem after modification.
can anyone please..? I also want you all to tell your approach.
I would keep adding elements to a subarray till we have a subarray which consists of all elements needed to make the sequence how it would look in the sorted array, then we can see this as a valid sequence and cut it here. Then repeat the process till the end of the array.
The answer is Yes when we have created <= k subarrays, since we can still split an existing subarray
can you please explain it with one example or drive run that example here...?
example
6 23 1 2 6 4 5split it into two arrays:
3 1 2and6 4 5reordering:
1 2 3and4 5 6got sorted array
I assume here your code time complexity is O(n).
so here what example you take is right but what about the below example is it still right to apply the above approach to this code..?
Example :
6 41 4 6 3 5 2remember you have to split it in exactly
4subarray that should be non-empty.well, that's impossible
Why is the tutorial blocked?
Because what's claimed there to be a proof of the statement the solution for problem A is based on is not a proof of that statement by any stretch. :P
why isn't the editorial visible ?
Is it unavailable for you now? I tried an incognito tab and it looks good for me.
Nice Contest :D