Choose the way, five paths there for you to find

Turn the page, the question lies between the lines...

Hello, Codeforces!

I hoped that once there will be my second round, and finally, here it is!

I am very glad to invite you to the Codeforces Round #741 (Div. 2), which will take place in Aug/26/2021 17:35 (Moscow time). **This round will be rated for the participants with rating lower than 100000110100 (2100).**

My thanks to:

antontrygubO_o

~~for rejecting problems A~~his great coordination of this round! Thanks!gepardo made a lot. There wouldn't have been this contest if he didn't help me. Thanks!

EIK this is the person who taught me competitive programming — my Informatics teacher. Thanks!

MikeMirzayanov for Codeforces and Polygon platforms. Thanks!

You for participating in this round. Thanks!

You will have 2 hours and 15 minutes for solving 6 tasks, **one of which will be divided into easy and hard verions.**

**One of the problems will be interactive.** So, it is recommended to read the ultimate guide on *your favourite type of problems* before the round.

I hope you will enjoy the round!

**Round testers:** 244mhq, BigBag, Snow-Flower, Kuroni, programmer228, MagentaCobra, Vladik, bWayne, kassutta, asrinivasan007.

**Score distribution: 500-1000-1250-(1250+1250)-2750-3500**.

**UPD: It was decided to add a sixth task to the round to balance the difficulty.**

**UPD2: Editorial is here!**

**UPD3: Congratulations to the winners!**

**Winners**

**Some other people who deserve congratulations**

good luck every one :)

do you know why you got so many downvotes?

i think it's because he copied the comment of upsolving from the deltix round blog and people at cf don't like cheating or copying either in contest or in blogs:)

CF comment voting is so weird and unpredictable. See?

Yes, never write comments if you aren't red

So, why did you write the comment with the advice not to write comments? :)

Because I want negative contribution, but I didn't make it this time :)

And if you are red then any trash you comment will get upvotes.

Now I know 1-gon comment can also get downvotes.

Exactly, if you are not 1-gon

it seems the rules of getting upvotes or downvotes are continuously changing ... lol

hi

Please, Update Score distribution.

I am not the author you should say this to Wind_Eagle

I wanted to give haha in this comment.Should codeforces introduce reactions like haha??(Asking Everyone)

Ready for a binary problem :')

SpoilerThis round will be rated for the participants with rating lower than 100000110100 (2100).

`for rejecting problems A`

Lol.

If I could say..

"100000110100(2100) = 2100**11 + 2100**5 + 2100**4 + 2100**2 ~= 3.5e36. Now we are all rated, so yay!"

Hope to see you GM post this round, Best of luck :P

Your rating graph even after refreshing 3-4 times :|PS : Not my first time seeing something like this

You just zoomed in on the graph.

Nope, zoomed in/out won't produce such graph. Additionally, u can see highlighted highest rating at left corner :P

Just check the timeline it is starting from jan 1970 . and Yes, zoomed in/out produce such types of graphs.

Give a try on another profile & show pic

Better luck next time!your last round had a problem related to Bit manipulation , i am guessing this round has one too ^_^

Well lots of bit manipulation is already going on in comment section.. damn they are already practicing for the problem..

BitForcespikachu theme? sounds interesting :))

bad round, no pikachu theme...

What is full form of P.S.??

Post Script.

Play Station of course, do not disinform people

I thought it was Play Safe

Nice! P.P.P.S. Very nice.

Ah! the poetic side of the author, the P.S.(Pre-Script) is noice!

Useful Resource to watch before this round.!

Best of Luck Everyone!

So, this is a Div. 10 round where we have 10 hours to solve 101 tasks ?

Yes, exactly.

Who is the VIP tester this time? The suspense is killing me.

I thought it is always you :)

gepardo

Umm... Not you this time?

NOTED

Should be taught lol

Really looking forward to this round!

I wonder if I get negative contribution, will it balance out and give me positive delta

Unfortunately real world is not like this

Really kind of yours to thank your CP teacher EIK. Looking forward to participate in your contest!

i guess next time is: PSPSPSPS congratulations to the winners

~~teached~~taughtThank you for teaching me English! You have taught me how to write the verb

taught!https://codeforces.com/blog/entry/94218?#comment-832737

sad violin musicSPELLFORCES!!!!!

Everybody here talking about Wind_Eagle's typo mistake of taught ,but nobody noticing the beautiful 2 liner poem at the top right corner of blog.

Actually, it is not mine, just google it.

Good luck to everyone, and i hope i can be cm after the contest.

So this round is about pikachu?

SpoilerI think it should be

availableand notavailible. Wind_EagleHoping interactive problem to be D or E. I don't like interactive problems but still, will participate in this contest.

Just VCed your last round, problems were super cool!!, Looking forward to this round

As a tester, you don't know if I tested or not

give the scoring distribution in binary form too along with the decimal scoring distribution Wind_Eagle

D1,d2 require 1 correct soln

Well, you are kind of correct: tasks D1 and D2 require a correct solution.

Where is the announcement of the testing round I just participated in?

Any astrologer out there, Will i become blue today .....?

Why is rating updation being done right now, in last round I went back to below 2100, but due to rating changes being updated it shows I am above 2100 right now which creates confusion whether this round will be rated for me or not ?

Can I expect a Easy A??

Why not?Every A of CF is easy!Sometimes it looks harder but has an easy solution.Like last round's A was pretty easy.But most of us thought that bruteforce wouldnt work :(

Ahh let's Be honest this time...Implementing A took me 2-3 mins but understanding A took me 20-22 mins last round!

Yeah, the implementation of A just involves a few if else and for loops, but still it takes time to figure out what exactly we need to do in the question :(

## When my Brute Force Solution passes all the TCs.

By this line

rating lower than 100000110100 (2100), I think there will be good concepts of bits in the problemsCould you please provide the editorials in JAVA as well.

Editorials will be provided only on English and Russian, I think :)

when will the tutorial be released

Right after the system testing I guess.

How to solve D2?

Is it somehow related to finding the K-th one in the segment tree?

I didn't submit anything for the contest, but I think you might be able to keep the indices of positive/negative in a set, get the lower and upper bound for each query in logn, and just greedily pick from there.

Much easier :)

From D1 you should already know, that answer is always $$$1$$$ for odd segments and $$$2$$$ for even, if sum inside is not equal $$$0$$$. So, firstly we will reduce problem to odd segments by taking first element of even segment to answer, for example. Then, you need to find such element, that sums before it and after in segment the same. Suppose we have query $$$[l, r]$$$ and we want to delete element $$$x$$$. In terms of prefix sums we will get $$$pref[r] - pref[x] = pref[x- 1] - pref[l - 1]$$$, that equals to $$$pref[x - 1] + pref[x] = pref[l - 1] + pref[r]$$$. And all you need — is to count $$$pref[x] + pref[x - 1]$$$ for all elements and add to some associative container such indexes, let's call it $$$C$$$. The answer- lower_bound in $$$C[pref[l - 1] + pref[r]]$$$ by $$$l$$$. 127111849

I did the exact same thing just that I am trying to find the element that divides the segment into two equal sums. so if for an odd segment the sum is 2*a+1. I am trying to find the element responsible for making the sum a+1. So that on the removal of that element the two segment right and left of it will have the same sum. But for some reason, I m getting wrong answer on test 2. Submission: 127143195 Can u help?

Very balanced and cool contest! Thank you very much <3

GuessForces

fr

Broo exactly!

How to solve E?

I can think of O(n^2 logn). But I don't think that's meant to pass.

My solution was O(n^2 logn logn) I guess, I got tle, what's your o(n^2 logn)?

https://codeforces.com/blog/entry/94218?#comment-833236

Wait for editorial :)

Wind_Eagle I generated all the substrings pairs (l, r) and sorted it using binary search + hashing in my compare function, so there is an extra log factor in the binary search, then I get the LIS, but this gets TLE, any tweaks for (binary search + hashing) idea to work or that didn't meant to pass?

https://codeforces.com/contest/1562/submission/127137681

I used suffix array with an O(N^2) dp, got the pattern when writing out the suffix array of the first sample test and try to get the result from that.

Actually you can precompute LCP in $$$O(N^2)$$$ with something like this:

$$$lcp[i][j] = s[i] == s[j] ? 1 + lcp[i + 1][j + 1] : 0$$$

That makes the code really clean.

I tried an O(n^2) dp approach. solution

I utilised the fact that

the answer for the reverse of the expansion will be the longest decreasing subsequence.By reversing the string, we can enumerate all the substrings that end at any particular character such that they are in the same order as in the original expansion.Now let dp[i] be the LDS such that we necessarily took the substring ending with char s[i].

So for calculating dp[i], the answer will be

at least i+1as we can take all the substrings ending at s[i]. Now we can iterate and check if we can add all these substrings to any previous answer only if those answers are greater than all substrings ending at s[i] (as it's always best to include these substrings).SO to check two substring families ending at s[j] and s[i] (j < i), I pre-calculated g[j][i] which tells me after which length of a substring starting from j towards 0, it becomes greater than the substring family s[i] and use this value to subtract the initial substrings starting at j which are smaller than substring family s[i].

Now final answer is max of all dp[i]

PS:- sorry for my bad explanation.

How to solve C?

Greedy .... lets say you have a string 1101 which is x (let's say) then to get a number that dividides it is simply 11010 which is 2 * x

So basically all we need is a 0 to find a multiple .... let place = index of last 0 (from 1 to n)

Case 1 — 0 exist in 1 to n/2 then just print from that place where 0 is to n and place+1 to n

Case 2- 0 exist after n/2 then print 1 to place , 1 to place -1

case 3- 0 is at n/2 ... print from n/2 to n and n/2+1 to n

Case 4 — all numbers are 1 ... then print 1 to n/2 and n/2 to n or 1 to n/2 , 2 to n/2+1

I the case that all the numbers are 1 i took 1 to n/2 and 1 to 2*n /2 but that did not work

I made a dummy mistake in the case that every thing is one , i output the interval in the wrong order.It's 1 to 2 *n/2 and 1 to n/2

A bit difficult for me. Is answer for D <= 2?

Yes

Problem name of this problem is a big hint to reveal the same.

Today I'll loose my "newbie" virginity

NOTED

Lol, guessed the solution for D1 but tried implementing with sparse tables instead of prefix sums for some reason...

How to prove D?

actually if alternative sum is 0 -> ok,

if it's odd then of course there exists 1 rod which divides interval into 2 intervals with equal alternative sum(total sum / 2) so this will be the rod to be removed(and after it second sum will become: -sum and hence 0 in total).

if sum is even -> just ignore first rod in current interval and sum will become odd, now do the same as above.(p.s. here it can be proved that in 1 deletions it's impossible to make things good(of course even in 0 deletions) the reason is simple: making alternative sum in 1 deletions simply means that there should be 1 rod without which the remaining sum should be split into 2 equal alternative sums which is impossible(odd isn't divisible by 2))

These two observations must be enough to get to a solution.

Observation 1:If rod at Indexiis removed,the subarray [i+1,N] gets multiplied by -1.Observation 2:If Sum is odd (of the form 2*a+1), we can find the index at whichsum[ l ,i-1 ] == a && sum [ i+1, r ] == aand remove the rod at indexi.Observe that once you remove a character the net value of the sequence following it till the end gets multiplied by -1. Now coming to the question There are 2 cases, either the sequence length is odd or it is even

Case odd: When the length of the sequence is odd then the total sign-variable summustbe odd. Now every odd number x can be written as`odd = even + [+/-] + even`

. Now if you strategically remove the [+/-] then the net value becomes even — even = 0. Hence the answer for odd length is always 1.Case even: When the length of the sequence is even then the total sign-variable summustbe even. If the total sign-variable sum is already equal to 0, then no rods need to be removed hence answer is 0. Otherwise, we can write`even = [+/-] + odd`

. Now to you have to remove one rod to get the net value odd and we saw that every odd value can be made 0 by Furthur removing one rod. Hence the net answer for this case becomes 2.Respect + notshivam

In B, the highest left digits is 2 right?

Yes.

Applied the same logic but what is wrong with this solution for B? 127124498

Your code is giving wrong answer for n = 233

Expected output : 2, 33

Your o/p : 1, 2

i got this approach when i was done with coding by taking so many cases.

Balanced an implementation heavy contest. B and C could be solved easily if you have pen, paper and time.

Some relevant meme.

I've prooved all the solutions :)

I'd be waiting for the editorial then :D. And memes apart, themks for an amazing contest! The problems were very interesting!

D1 I only saw sample test and guess :)) then I pass pretest :V cool :)

The keyword for today's contest is "answer <= 2".

how to solve C?

Just search for one zero For example you have 10111 then ans is 0111 111 k=1 and if the zero is after half the string like 11101 then ans is 1110 111 k=2

Did the first thing but missed the second one during contest,couldn't catch the left shifting observation...I am gonna kill myself

I got the second one but failed to understand the first one, and got stuck in this problem.

Why can't I see any of your submissions of the contest?

Every other problem is casework lol. Nothing to learn from the first 4 problems.

Finding out the cases is problem solving too, no?

Sure it is, but so are puzzles. None of these problems involved programming or designing a data structure or an algorithm I'd say.

I'm not saying these problems are bad, but it's nice to have a variety in contest problems. There is so much possible with graph/tree, DP, DataStructures, geometry, string algos. So it's a little disheartening to see the first 4 problems just being ad-hoc.

Task E? It involved algorithms lol.

Yeah, I can barely make it to the 5th or 6th problem with enough time in a 2hr contest.

I used to like Topcoder SRMs for this reason because one can actually get to the harder/nicer problems in time since there are only 3 problems. But i guess I'm digressing here, I'll give it a try when i find time to upsolve. Thanks.

Did you changed the checker for B?

Because my code passed sample in contest but failed on the same test case on sys test.

Mentioning Wind_Eagle

My code failed system test:

And it failed on the sample case:

Same for me. I print the wrong length of the string. I always print 1, even when I have to print 2. The code passed pretets but failed systests. In fact, my solution should fail sample test, so it should have failed pretests as well. There's something wrong here.

Yes, this is the same mistake I made.

I think they changed the checker without any announcement.

This is unfair.

gepardo Wind_Eagle Could you look into the situation please? It's as though there are different checkers for pretests and systests. Both of us could easily correct out the code without even losing 50 points for the wrong submission as we fail on the sample test. I understand that it's still our mistake and we should have been more attentive. I cannot prove that I had the AC on B during the round, but do believe me. There could be more casualties.

I have a proof. See my Submission(127073976) for B that gave runtime error on test 2, but actually prints wrong answer for test 1 as well. It was very unfortunate that they had incorrect checker for B, that made my obvious incorrect solution pass.

The previous Codeforces had weak pretests for D1 and D2, that allowed my solution with integer overflow to pass but it failed on system tests.

It is too sad and demotivating to lose rating continuously due to others mistakes. (ofcourse some mistake was mine as well, but in ideal cases I will consider them as other's mistake).

same things happening to me :(

A screenshot from round 738

And my code passed after fixing the size.

I was about to get somewhere around +100

Now its -8

(;﹏;)

I don't know why B asks for outputing the length, it makes no sense, just annoying.

In last Div1 round my rating decrease by over 100 so I become Canditate Master after that; but because ratings are temporarily rollbacked, and when I register the current round I noticed that I'm "out of competition". I will be rated after undoing rollback? or be unrated as my rating is temporarily still > 2100?

Will be rated.

lmao I guess I will be unrated so I give up debuging D2 and start to write E.

I'm also in the same situation, let's see how rating changes after the contest.

I can tell from your picture that you are Chinese.

How to solve D2?

$$$Trickforces.$$$

How sneaky: "such that $$$f(t)=f(w)⋅k.$$$"

It is to make sure you can print f(t)=f(w)=0.

deleted.

In C is f(t) and f(w) both are 0 allowed? that would make k become any integer.

Yes, such case is possible, and $$$k$$$ can be any integer in this case.

OK, Thank you for clearing doubt

Ad-hoc problems nowadays are getting to the next level.

Deleted

Deleted

SpoilerMe trying to become master for the first time.

codeforces:

I am so sleepy today... especially I only sleeped for 20 mins in the afternoon;But the problems are quite challengeable.wu... it is 1:00 now,i gotta sleep;

In C, first testcase, would "2 5 3 5" be a permissible output? We have t="0111" and w="111", hence f(t)=7=f(w)=f(w)⋅1

Yes I guess.

Solid contest

Liked the problems.

I personally like this round,because the problems require a lot of thinking,and some of them need you to process all those tricky corner cases,the difficulty is quite suitable for me.

but I think the Examples in D1 "spoke too much",I guessed a solution via Examples and after checking through some queries having odd length,I submitted and got AC.I would've never guessed it if there weren't so many Examples

Great Problems, Thanks to the authors

it was really a cool contest, thanks Wind_Eagle

Editorial?

Is there any good website conducting contests on DS Algo?

In problem B, checker log says 'wrong answer Number is too big! (test case 101)'. What am i doing wrong? Can anyone help. 127129777

You are doing way too many calculations you should have checked the string in n^2 complexity considering all pairs of two digit number after the one digit number

I have an O(n) idea, you see it in my submisson.

How to solve E?

Note that if we take some subarray, we can take all the suffix which has the prefix as this subarray. compute the prefix array for every suffix using the z algorithm, Then we do normal LIS dp. The comparison will be, let x = z[j][i] for all j < i. Then if s[i + x] > s[j+x], dp[i] = dp[j] + n-i-x+1. Take the max of all dp. Submission

Unfortunately I din have time to implement this during contest even though I copied the code for z algorithm from geeksforgeeks.

I think I will turn to an expert after two huors.

EDIT — Problem solved!

In question B , what is this issue , "Number too big!"? Did we had to perform maximum deletions? Edit:- Never Mind , Got it

My solution 127123174 was rejected during the contest. However after the contest this submission of mine is accepted: 127130827 Now both the submissions are literally same except in line 67 and 68 where I have essentially just printed (l2, r2) before (l1, r1). I think this was allowed. Am I wrong?

You had to print l1 r1 before l2 and r2, that was asked.

Since, f(substr(l1,r1))=K*f(substr(l2,r2)), and K is an positive integer, do it was essential for the decimal representation of the substring formed by l1 and r1 to be >= decimal representation of the substring formed by l2 and r2, so you needed to print l1 and r1 before. And, it was even mentioned in the question itself

For every test case print four integers l1, r1, l2, r2, which denote the beginning of the first substring, the end of the first substring, the beginning of the second substring, and the end of the second substring, respectively.

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

EDIT — Problem solved! (My sieve function was getting out of bounds, which caused undefined behavior, thus resulting in my code getting RTE in competition and got accepted afterwards)

Mike, will the rating after this round be applied after the rating changes in round 740 return? Or there would be a mess? I'm afraid that i won't be rated.

Wind_Eagle Nice Dream Theater references in A&B!

Thanks :)

My other favourite bands include Yes, Rush, Van der Graaf Generator, Pink Floyd, ELP, King Crimson, Magma, Symphony X, Fates Warning and some other progressive bands.

Sorry, misread

Umgh... Where is the Rush reference in D?

I thought it was a reference to the 2112 album after seeing Dream Theater and Oldfield references.

Progressive Rock & Metal <3

You know what, I can understand now that the half of the contest was a bit 'Rush reference' (album 2112): at least in tasks B, C, D there were magic numbers 1 and 2 (most commonly the answer).

Can somebody review this simple code for problem B? I tried brute force for 2 digits solution, if one digit composite couldn't be formed. I am unable to see failed test case in my submission.What does "Number too big" error mean?https://codeforces.com/contest/1562/submission/127124101In the isPrime function, it should be " i*i<=n "

AC submission: https://codeforces.com/contest/1562/submission/127139793

How to solve D?

Motivating everyone for competitive coding.Thank You So much sir It gave me goosebumps

Much needed content here

Thanks sir. Much needed motivation

much needed motivation thanks bro

Thanks buddy

Thanks to the authors for the contest, and to Mike for codeforces.

Thank you for participating!

127114107 Details: answer Number is too big! (test case 289)

Check this case

Case:1

3

573

Correct output is 57 but your code prints 573, which is too big.

You are absolutely right! Thanks!! Can't believe I spent an hour and a half looking at these four numbers and didn't realize 57 wasn't a prime :p Thanks once again!

The questions were really nice. I also appreciate the dream theater references! Wind_Eagle

Apart from the tricky string questions(which are hard for me to solve), it's a very good round and i really had fun.

I think the statement for problem C was way too convoluted/complicated. So many formal, mathematical equations in the text make it really difficult to understand what is even asked. If you said it in text, in some kind of story, the statement could have been 5 times shorter. A good story helps us understand the problem, but the "Frodo and Bilbo" and "gold and silver" were just distractions, the actual task had no story, just a set of 4/5 conditions that had to be satisfied. (And the f(t)=f(w)*k condition is super weird)

Today morning I got this message saying: Attention!

Your solution 127110039 for the problem 1562C - Rings significantly coincides with solutions aman_5311/127096892, all0fme/127110039. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I want to clarify that the match is a pure coincidence. The solution to this problem is so trivial that my code even coincides with the official editorial solution. You can also lookup that I submitted two other attempts to this problem where I made silly errors for the case when all ones occur.Also it does not match entirely the condition used in my code is (i+1)<=n/2 whereas it's i<=n/2 in the other.

My rating has been rolled back. Wind_Eagle MikeMirzayanov sir please look into this.

UPD:No response from codeforces, I lost my rating(74). This is so Unfair.Looking at the way code is written it seems a coincidence. Pls Wind_Eagle MikeMirzayanov sir look in it.

After checking the code and reading out the comment. I also think it was just a coincidence and was not intentional. Please take a look Wind_Eagle MikeMirzayanov .

I got this message from codeforces--> Your solution 127096892 for the problem 1562C significantly coincides with solutions aman_5311/127096892, all0fme/127110039. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I even don't know the other person . And solution of this problem is very basic to think. We just have to output three lines . In thousands of people pattern of two people may match. I haven't sent my solution to anyone also. And I used to write code on Codechef Ide and that can be Accesed by me only. So I don't know how this happened. So Mike sir Please look in to this issue

The other person has posted the same comment above you too. Lol, you guys coincided again.

U can go and read both the code then U will realise that it is just a coincidence. We just have to output 3 fixed lines and if our logic are same then we may write in similar fashion..

Is it a violation if I submit the same code in my mini account?

Of course it is. You agree that you will not use multiple accounts and will take part in the contest using your personal and the single account while you are registering.