Hello, Codeforces!

74TrAkToR and I are glad to invite you to our Codeforces Round #750 (Div. 2), which will be held at Oct/24/2021 13:05 (Moscow time). Notice the unusual time of the round. **The round will be rated for all the participants with rating strictly less than 2100.** At the time of the round the CheReKOSH olympiad will be held, where the problems from this round will be used!

We would like to thank everyone who helped us a lot with round preparation.

- Our coordinators KAN and isaf27 for excellent coordination of the round.
- Our testers Um_nik, Denisson, TadijaSebez, ijxjdjd, Mr.Robot_28, flamestorm, romanasa, MagentaCobra, QuangBuiCP, wxhtzdy for high-quality testing and helpful notes.
- MikeMirzayanov for amazing Codeforces and Polygon platforms.

On the round you will be asked to help characters from animated series Luntik and his friends. You will be given **7 problems, one of which has two subtasks**. You will have **2 hours 30 minutes** to solve them.

**UPD**: Score distribution: $$$500-750-1500-1750-2500-(2000+1500)-3250$$$.

**UPD2**: Editorial

**UPD3**: Congratulations to the winners!

Div. 2:

Div. 1 + Div. 2:

We wish everyone good luck!

hoping for a good contest :)

You wrote the exact same comment in the announcement of rounds #748 and #749, but didn't participate in both of them. Will you participate in this one? XD

Bro actually i participated in div3 round but my solution of D1 concides with 1 participant , i dont have any idea how this happens to me and in round 749 i did not participated due to issuse on codeforces like site is not opening properly . I am new to codeforces and if u want then i will not post such comment from next contest onwards.sorry for my comment .

I never said there's anything wrong with your comment, I just thought will you participate this time. Chill dude, you can post whatever you want. :)

if he participate he cheats, so better he shouldn't!

will see !!

why are tou skiped?? you cheated again ?!?!?!

The moment I saw 3 compilation errors, I knew something was fishy.

i wonder why many cheaters comments nicely before they attempt to cheat.

SpoilerNo boy, he isn't a cheater! I know him personally, and he is a really hard-working (just see his graph) and honest guy.

As far as skipping is a concern, it's because he didn't knew that we can't use 2 ids during a contest.

a hard-working honest guy who has been skipped twice in a row?

hm.....

As a tester, good luck anyone who participates will have a positive delta!

-QuangBui(YT/CP)

sum of delta = 0 intensifies

Thank you.

Anxious for the contest to arrive

PS:I take this opportunity to leave a link to a blog with a collection of segment tree problems that I hope will be helpful to someone. https://codeforces.com/blog/entry/22616Thanks to AminAnvari

MemeBecause it's not related to the blog. You could have post this in the segment tree section of codeforces edu instead.

Another friendly time for Chinese users! Looking forward to great problems and having fun!

why cf is organising contest at unusual time these day? By the way hoping for big delta +ve

At the time of the round the CheReKOSH olympiad will be held, where the problems from this round will be used!

At this point I dont know which is the usual time anymore :))

This contest is clashing with Codechef's cookoff contest.

no

traktor. Me when I read A

As a tester, GOOD LUCK!

your comment makes me nervous.

Should have seen this coming :PIEEE is coming in 2 days!

nice memeIt's better to put the meme inside a spoiler so it doesn't take so much space :)

How to do it:At the beginning put <$$$spoiler summary = "name for spoiler"$$$>, in another line the information and then close with "<$$$/spoiler$$$>

I put $ because otherwise it becomes recursive XDthanks!

does one subtask means that one problem will be divided to easy and hard versions?

Probably.

Yes, subtask means same problem will have different constrains and one of those can be passed with a easier solution.

Not always. Sometimes problem statements are different.

i wish i could creat a contest like this one day :3

I hope to be a regular contestant from this contest!! And as a newbie i wish to solve at least 1 problem in this contest!

is the score distribution finalized?

Unusual TimeI hope you surprise us with A1 and A2

I hope to become MASTER again through this contest.

Good luck!

Me too lol hood luck

lol i think u will be master nice job ! i had a really bad contest however

My dream comes true!

Thank you!I sincerely hope that you will get a very nice performance next time.

I want greenSpoilerlesgooo

I had achieved

Good time for Chinese participants!

I wonder why recent contests take place earlier.

Maybe today's contest is early because otherwise it would have clash with CodeChef's Cook-Off !!

I don't know whether it is appropriate to post this comment under this blog.

If I registered for round #751(Div-1) and I lost candidate master after today's contest, will I be able to participate in tomorrow's Div-1?.

No, you won't.

ppl say the unusual time of this round is because its mirroring an olympiad, but we all know the real reason is that it doesn't clash with the T20 World Cup: India vs Pakistan. Thanks Codeforces, appreciate it.

Are you saying it clashes with Sri Lanka vs Bangladesh out of spite?

At least the first question can be easy for newbies!!!

Boruto you are annoying as ever !! First cheating in chunin exams and now this

A new chunin exams starts today (3:30 IST)! Hope you are still in the game Kakashi!

I am Kakashi hatake the copy ninja .. I know a 1000 Jutsu and I will use them all and live up to my name !!

Are you aware that you are under Genjutsu :D

We all are ...

Kakashi, linear diophantine equations?

Kakashi sense(or else I can say stupidgoat) can you teach me the Rasengan! For the

current chuninexams so that I won't cheat, please...Bro I am a copy ninja just stop kidding

I wonder about that because you don't have the dear Sharingan anymore Mr.Copyninja!!

Bro codeforces round at 3.30 ... I have sharingan ... Itachi is alive what do you think is happening .... It's INFINITE TSUKUYOMI !!

Let us kill Madara(code forces round) together.

Those Who Do Not Understand True Pain Can Never Understand True Peace.Interesting !

Mr.Kakashi, I got+84. Anyway, what about you?is there gonna be score distribution?

Hope you won't cheat this time :)

Yay! Perfect Timing for me. Today is IND vs. PAK World T20 from 7:30 pm (UTC+5.5).

Is it rated?

What part of the sentence, "The round will be rated for all the participants with rating strictly less than 2100," do you not get?

he's trolling obviously or testing how many downvotes he will get

What part of sarcasm you don't understand? Oh, all of it.

Eh, I thought he was being deadass lol

Todays Contest is Awesome..... I am only able to solve one question but B and C questions solution i know but there time complexity is way too much........ Today gonna learn something new...... Very nice contest Again!!!

there should be no zeroes in array B

Dang!!! Sum of 2 elements in the input array can be equal to zero ....

Guys does Codeforces really use Adobe Flash Player? I feel like it is a prank, I can't do hacks.

OpenWTF is happening with me I am solving A in more than 1 hr and B,C in 30 mins is it just me or nowadays problem A is becoming trickier. I suck

Not you, todays problem A was tricky af. Not hard, just tricky. Seemed trivial at first but then...

I can't solve anything. I've been staring at the problems for 2 hours and 20 minutes already. This is a good opportunity to upsolve. Nice contest!

i couldn't solve anything too,i was expecting to solve at least the first problem but div 2 is just too hard

Thanks for such a good contest!

WHY THE CONSTRAIN sum <= 1e9 is in D there are solutions that cut because of this what the hell is point? you could make it 2e9

I feel that was the whole point of that qn.. There was a way("we had to think that") to get it within the limits. I couldn't pass my code btw..

I don't think we should think to reach the idea of the problemsetter for specific problem

especially constructive problems like this has many many solutions

this is hole point of creativity

That made it interesting for odd sized array.

How to solve E? I tried a O(n^1.5) dp approach but didn't work.

Most probably you must have taken the limit as sqrt(n) but it should be sqrt(2*n)

No, it took sort(2*n). Got runtime error in pretest 8

I also got RE in pretest 8. After declaring the array globally, my code passed.

Yeah, mine passes when I use vector instead of array. Any idea why?

O(n*sqrt(n)) is well enough.try constant optimization.

dp[k][n], and kmax = 450

please tell me if i have submitted two pretest passed solutions for the same problem, which one will be judged for main tests??? please some one tell meee pleaseeeee

Are pretests for F1 really weak?

Unfortunately, it's true. That problem didn't have a multitest testing so it didn't work out to cut off as much solutions as possible using a little number of pretests. A little number of tests was needed to avoid queuing.

unfortunately yes :(

Someone solved the problem F2 with a Gaussian basis?

I don't think that it is possible to solve this problem with gaussian basis. The expected solution uses the fact that you have at most 5000 different values for $$$a_i$$$. You just need to solve $$$dp[k][xor] =$$$ minimum position you can reach value xor, using only $$$a_i <= k$$$

Can someone give a hint for A? I was trying it case by case but I felt like there were way too many cases with my method. In the end, I was really short on time and couldn't even enumerate all the cases.

for Problem A : the answer is either 0 or 1 proof : let A , B , C be durations ( 1 min each ) of the 3 musics A + 2B + 3C is the total duration now consider 2 groups : ( B + C ) and ( B + C ) so we remain with A + C duration now if A + C is odd => 1 will be extra or else A + C will be equally distributed

How do you split 2B + 3C into 2 groups of B+C? A 3 minute song cant be split and neither can a 2 minute one.

And for A=1, B=0, C=1 the answer will be 2. Is my understanding of the problem flawed ot something?

B can't be zero

`a,b,c >= 1`

Oh I missed that. I still don't understand the explanation above though :(

Actually by groups I meant in terms of Mathematical expression (B + C) + ( B + C ) + ( A + C ) . since any duration between 0 to A + 2*B + 3*C is feasible such a split is also feasible . ( I am not splitting the physical music discs )

4.Answer is obviously can be 1, because a + 2b + 3c can be odd.

Proof: answer can't be bigger than 1, proved that in 1. — 3. If cannot be divided, then answer is 1, and that means that sum of bigger subset and smaller subset is odd, which contradicts with what we prove. So the answer is (a + 2b + 3c) % 2.

You can check the absolute difference ((a*1+b*2)-(c*3)) , If the answer was even print 0 and if it was odd print 1 .

It was a nice contest , Thank you .

D was nothing but x(+y) + y(-x) = 0 and x(-y) + y(x+z) + z(-y) = 0. One can easily use 1st relation to solve for even arrays but tricky part comes for odd arrays where u need to find x and z such that there sum is not 0.

+1 i didn't generalize the solution on both conditions, any hint ??

the problem guarantees $$$a_i \ne 0$$$ for all $$$i$$$, so

at least one of $$$a_1+a_2$$$, $$$a_1+a_3$$$, $$$a_2+a_3$$$ is not zero. Just find it out and solve $$$a_4$$$ to $$$a_n$$$.How to solve A quickly?

Just guess the solution.

EDIT: Updated URL: https://ideone.com/y10o7M

Can someone check if this will work for D https://ideone.com/y10o7M

Great problems!

I don't understand the answer for A from editorial:

cout << (a + c) % 2 << '\n';

If a=0, b=1, c=0, shouldn't the answer be 2 minutes? (not zero as the editorial suggest)

a,b,c (1≤a,b,c≤10^9) — I didn't see this limitation myself at the beginning and went to solve C.

ah, thanks!

a,b,c >= 1

a and c cannot be 0 from the constraints.

This problem would be much more interesting if 0 <= a, b, c. Writing clean and not bugged solution in this case is a skill. Disrespect to authors or coordinators.

The problem is an A problem for a reason.

The solution was already a guess, adding more corner cases is dumb, specially on the first problem.

It can be solved without any corner cases even if 0 <= a, b, c, you just can't see it

SpoilerWe may have problems only if a, b and c are very small. So if a, b, or c are too big, subtract 2 from them until they become, say, 6 or 7.

Now, then a, b, c <= 7, you can bruteforce with for-for-for. No ifs, no bugs.

Seeing such solutions is a skill for beginners, they should learn it, and authors should encourage it instead of giving stupid 1 <= a, b, c.

Sure, say your solution then. Me and probably many others would just add ifs and get ac faster then trying to think of a way to implement it without corner cases

The question for the experts is, is there really not a single test in A that would reject a solution with an overflow of the int variable? https://codeforces.com/contest/1582/submission/132905404

I spent half an hour looking for a hack, for this solution, for me it became a kind of challenge...

Did anyone else solve F2 with bitset in $$$O(\dfrac{a_i^3+na_i}{w})$$$? I think that I will FST(

I solved by assuming that only the first and last occurrence of a number will matter (Not 100% sure that it is correct)

Upd: Not Correct

$$$O(N + A^2 logN)$$$ passed in 400 ms, god bless g++!

If I am not wrong, your solution is $$$O(N+A^2log(\frac{N}{A}))$$$.

I needed more 5 minutes to fix my bug for D if I just didn't be like a moron in A and waste 20 min on it pfff I hope my solution is WA after fixing that bug that would actually make me feel less worst lol

Edit: Accepted but wasn't gonna make it in time without my stupidity in A anyway that actually feels even more less worst my idea is correct and I wasn't gonna make on time better than the solution is completely wrong or i just needed more 5 min to get Accepted

Problem — B

Left shifthttps://codeforces.com/contest/1582/submission/132910881 -- WA on pretest 3

Logarithimc power methodhttps://codeforces.com/contest/1582/submission/132911508 -- WA on pretest 3

Powhttps://codeforces.com/contest/1582/submission/132911986 -- pretests passed

Is'nt left shift and logarithimic power method better than pow??

anyone can explain why?? thanks in advance.

`(1L<<zc);`

returns an int, so if zc > 30 you will get 0 in the answer. Change it to`ll ans = (1LL<<zc);`

and you should get ac.You are also taking the modulo in the logarithm power, which makes 0 sense in this problem and this is why youre getting wa

Nice problems! If problem A explanation was correct this contest was one of the great contest in cf

Problem D has shaved years off my lifespan.

FSTforces

2 minutes silence for those who got

FSTon F1.I don't understand one thing

Why does xor of empty subsequence equal to zero?

Another interesting thing is that there was no such pretest in the tests.

0 only as empty sequence was in first sample

But there was a subsequence with xor 0

There is no pretest with only empty sequence xor 0

wasn't, only three correct subsequences: {2}, {4} and {2,4}

I think he means that if you consider all non-decreasing subsequences (not just increasing), and you don't consider xor 0 as always possible, you will fail only with a test where there is no non-decreasing subsequence with xor 0.

To get F1 accepted it was more important to keep in mind that xor 0 is always possible than the fact that increasing subsequence is different from non-decreasing.

why the grade of F1 so high????

.

132901810

so you submitted your first code in c++ just by studing that link?????

haha. another shameless indian lying after being caught.

just like the other indians

After the round 750, I received the message:

" Your solution 132867227 for the problem 1582C significantly coincides with solutions vpike/132864849, RefreshedCoder/132867227 "

The two solutions can be found here:

132867227 132864849

It's a simple greedy approach and I wrote every character in my IDE. It's a wrong judgement and may I ask the admin of Codeforces to examine the two submissions manually?

I personally don't know vpike and it's just a coincidence that our solutions are similar in this simple problem. I solved in total 6 problems in the round and there's no motivation for me to cheat in problem C.

Please, could anybody help me to get my rating back?

UPD: Ping MikeMirzayanov here

I'm sure too, it's a rare coincidence. Why two submissions for simple problem with small amount of code cannot be close to each other? Please examine submissions manually.

There is no any feedback on this issue for a long time. Dear AlFlen and 74TrAkToR, could you comment it?

It's not our decision, sorry

Can somebody hack my D? I think my submission is wrong, because I dont check this condition

the sum of their absolute values cannot exceed 10^9. 132943758 upd: it is correctYour solution 132914687 for the problem 1582C significantly coincides with solutions cuckmasteramogus/132914655, pranil_19/132914687, nipple/132915851.

I have used ideone because I don't have idea that someone can see my solution there that's why my solution has been copied by somebody. For the first time I got to know that using ideone code could be copied through your notification. I never uses these kinds of practices in contests. How can you send such notifications without even checking those two ID's that copied my code using ideone. and you should check the profile picture of id nipple which is so disgusting. You can check my previous submission I have used before this contest that contain same format of code. I request you to look into this matter , and bring my score and rating back Please.... 74TrAkToR AlFlen [user:Mike Mirzayanov]

Is F2 solvable with java?

Thanks for fast Editorial!

can anyone help me to find mistake in my code ? C[submission:133037244]

Can anyone tell me why me solution https://codeforces.com/contest/1582/submission/149071151 gives TLE on F2 If I use while loop which I have commented instead of for loop it gives AC.