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 ,DeadlyPillow , 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 , Mohammed_Atef_Hassan , tdpencil , mcdx9524 , EwNacEsirNiaga , _Hosam , Bakry , N4553R , 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++ :)

i am very happy, you are amazing men #keep going ♥♥

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

iam waiting for a great contest

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.

You took the fun out of it mate!

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

If the problem statements are short, i hope it will be fun to solve!

ik this contest is going to be great :-) I'm sure 100%

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

Error_404, joining this contest cause i found that you are my neighbour xD

tdpencil has hacked few of my solutions in the past, so for me he is orZ. yeah!! this orZ has curves.

MiceMirzayanov is giving me rating in spite of me being lgm this round mark my words uwu

keep going!!

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 :D

I am waiting for a great contest by a great author :D

تحيا مصر ❤️

I can't wait for a great contest <3

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

This man's rating curve = "The master has failed more times than the beginner has even tried."

I really relate with this man's rating....

kitne huye?

You can go in my profile-> submissions

We are so proud of you all , keep going :")

CKMKB

This is not twitter.

TMKB

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!

Chill mate! No need to be so dramatic. There will always be another contest if you don’t like this one.

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

Waiting for a good contest!

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

good luck

why?

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 .

We all are ready for this great contest.

Best wishes to allAs 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

waiting for the contest.

تحيا مصر ❤️

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

Exciting for interactive problem

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

Good luck bro ull get to specialist today :)

I hope so.I will try my best.Thanks for your kind words

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.

الله يبلدنا الله ❤️❤️

Good Luck Everyone!

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 :(

I got pretests passed first

then in sys testing I got TLE on test case 2 :|

Because reading doubles is very slow.

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).My approach was correct but sadly I used float. Anyone please check my profile using codeforces visualizer and tell me what I am doing wrong. My rating not increasing.

Why the gap between C and D was a lot ?

toxic:(

check his original commentHow 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:/

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 :(

Egypt ki maa ka bhosda

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.

I wrote a brute-force solution to generate answers for the smaller values. It helped to pass the pretests at least. Let's see whether it passes the system tests or not.

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

is C easy ?

will reply after the contest is over in 2 mins :D

I tried the following but probably got stuck in some ridiculous edge case.

for

`ith`

bit, the no of elements in the array with ith bit set should either be >= 2 or 0.Its decent.... combinatorics and inclusion exclusion.. 1600 I guess

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

Probably not, but I'm pretty sure I'm the only one who submitted with the wrong language settings on two different problems (ugh).

Weak sample for C :(

In div2 B i was rearranging the elements inside subarray for half an hour.

Sad noises.

Me too

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.

Can you share your code pls. Your all submissions are still locked :(

UPD: my bug was that I had to declare the Segment Tree Array with

`8n`

elementsContrary 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`/`

, and`a + b / c`

wouldn't be`(a+b) / c`

now, 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:

HintSay 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).

SolutionLet'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

Solution for DFirst 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.

Soooo weak server System!!!

How to solve C?

SpoilerFor 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.

How to solve problem C?

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.

May I know what the formula is?

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$$$.

Wow How did you come up with that?

Video solution, you can also convert the recurrence into a 1D DP (DP solution).

Wow thanks!

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

`C`

be solved using DP?I tried to implement via a 4-D dp

`dp[i][_and][_xor][eq]`

.At the

`i`

th bit (out of k), I have 4 ways of assigning bit combinations to the`_and`

and`_xor`

values ->`0 0`

,`0 1`

,`1 0`

,`1 1`

, and`eq`

can be0/1/2, denoting whether the`&`

cumulative value until the`i`

th bit islesser,equalorgreaterthan 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:

dpnot sure what I have done dp:

ugly dpCount 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.

Author Mo2men struggles to solve div2 C so he make others to struggle .

He may have won but at what cost.

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$$$.

Solution$$$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

This is why i am against rounds created by specialists/experts or low CMs they only try to make the contest hard.

Overall view -> No original idea.

A -> good for div2 A B -> shitty observation problem/ also you could have made statements clear. C -> shitty Combinatorics problem with simple cases one can do it. D -> No comments E -> No comments

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.com/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!!!

Your inequality is only true when n is odd, right?

yes

here's using loop :

https://codeforces.com/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.com/contest/1557/submission/125390194

I guess the setter didn't include this test in the system test.

1

https://codeforces.com/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

clearlysays $$$0 \leq k \leq 2\cdot10^5$$$https://codeforces.com/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