<almost-copy-pasted-part>

Hello! Codeforces Round #605 (Div. 3) will start at Dec/12/2019 16:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

Remember that only the *trusted participants of the third division* will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participants of the third division*, you must:

- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

**UPD**: Great thanks to Artem rox Plotkin and Dmitrii opukittpceno_hhr Umnov for testing the round and help with bugs fixing! Artem is also proposed one of the problems for today's round!

**UPD**: Editorial is published!

Hope to see non-black IDs win this contest(for whom this isn't first contest)

Winner is a pupil ;)

Oh yeaaa great lol

Anyways I hope high ratings to all the non-black handles

The only real black handle is MikeMirzayanov :)

Oh actually bro had said that for top reds who make new handles in each contest just to win in lower divisions and absorb the ratings of others

Agnimandur Whats about Una_Shem ? if MikeMirzayanov only Black !

vovuh one love

Orange Vovuh

I think it is the first round made by Vovuh as a Master . Good Luck and I hope the contest will be nice .

Add the information to the right to capture the audience.e.

will 15 december held two contest?

After a long time Codeforces arranged a contest. I am waiting for this contest. I think, the contest will be nice and interesting for me and also for others. Thanks to MikeMirzayanov and Vovuh for arranging the [Codeforces Round #605 (Div. 3)] contest.

hoping to qualify for Codeforces platinum!

What is Codeforces Platinum?

I think he means Usaco Platinum xD

Do you have a crush on Nightmare05 or what? dreamr

Not that lucky bro xD

Is the scoring (points per problem) known?

"The round will be hosted by rules of educational rounds (extended ACM-ICPC)"

Thank you for the answer.

perticipantes are ranked based on the number of problems they solved and the time.

So, importance of all problem is same.

codeforces server seems to be broken same code giving diffrent output on my macinhe and server on my machine my code passes the same code while on server produces wrong ans i got 3 penalities due to that still not able to submit ..

Use custom invocation on cases like that, and then debug.

+1 the main website was broken and I wasnot able to open it until the contest was over.

Same here. I solved 1st and 3rd question on paper within few minutes and when I clicked submit button after writing the code on their editor, connection failed and page could not reload for about an hour. After some time the issue resolved but after submitting solution of 1st question, same thing happened again

Yup site was broken for me too. Took part from m1.codeforces.com.

Yes me too

Can anyone hack this solution 66706230?

UPD:Hacked, thx dead_blue!How to solve D? I kept going in circles thinking about stack and non-positive difference...:(

I can't tell you how to solve it in English, but you can check my solution, maybe it will help you. https://codeforces.com/contest/1272/submission/66702493

Maintain 2 arrays, Increasing and Decreasing. Increasing[i] will store maximum increasing subarray till ith element, similarly Decreasing[i]. For each element check if (i+1)th element is greater than (i-1)th element, If true, then we can delete this element and updated ans=max(ans, Inc[i-1] + Dec[i+1]).

Elegant Solution, can you explain why this holds?

I didn't use this dp approach. The following is the algorithm I came up with. First find all strictly increasing continuous subarray and store each such subarray's start and end index as an interval. Update the max length for each interval.

Then iterate through all intervals and check every two adjacent intervals and do the following. 1. if the current interval only has 1 element, remove it, get the next interval if possible and check if the previous interval and this next interval can form a longer strictly increasing subarray. Update max length if necessary.

The above solution fails on test 14 by a difference of 1. Can you help explain why this solution is incorrect? My submission is 66729847. Thanks!

Your idea is almost same as me.

I stored all strictly increasing sub_sequence block.

Then updated result by comparing all block size.

After that i took 2 consecutive block each time. If 1st block has size > 1, then we compare the 2nd element from last of 1st block with 1st element of 2nd block. if a < b then we have a length of block1+block2-1. Similarly i checked by ignoring 1st element of 2nd block.

https://codeforces.com/contest/1272/submission/66754733

Yeah, I think our idea are similar in general, except that I made the mistake of comparing value with index in one of the if statement, if only I could realize that during contest :(

Thanks for replying though, without comparing your code I probably wouldn't even realize that bug in my code.

do dp. dp1[i] = maximum length of increasing contigous subarray having the element of i from 0 to n. dp2[i] = maximum length of increasing contigous subarray having the element of i from n — 1 to i. Find out max length of subarray without removing element.Initially, this is the ans. And then, for every i from 1 to n — 2, check if(dp1[i — 1] + dp2[i + 1] > ans && v[i — 1] < v[i + 1]), if yes, then ans = dp1[i — 1] + dp2[i + 1]. That's it.

Let pre[i] be the maximum possible length of strictly increasing contiguous subarray of array a from index 0 to index i

Let suf[i] be the maximum possible length of strictly increasing contiguous subarray of array a from index n — 1 to index i

Loop from i = 1 to n — 2, if a[i — 1] < a[i + 1], then ans = max(ans, pre[i — 1] + suf[i + 1]).

very similar to this problem: PIBRO

This AtCoder Problem is also an interesting one that you can solve using the above technique:

GCD On Blackboard https://atcoder.jp/contests/abc125/tasks/abc125_c

I've made a string of

`0`

and`1`

of length N-1, where`1`

means $$$a_i < a_{i+1}$$$.Then applied a regex

`/ 1+ 0 1+ /x`

, and checked elements near matched`0`

if they increase after one deletion (i.e. if exists $$$j$$$ that $$$a_j < a_{j+2}$$$, where $$$j$$$ is near`0`

). Perl code 66779749.How to solve F? LCS and some post-processing?

No, it is dp.

I tried dp, but tbh, backtracking in dp made it quite implementation heavy.

I feel you man.

Same feels. I coded a dp solution with backtracking for around 240 lines. Couldn't fix the bugs within the contest time. Got it accepted after contest.

You can find my submission here.

Simple DP in $$$O(n^3)$$$. Notice that the answer's length cannot exceed $$$400$$$ and do dynamic programming. $$$dp_{i, j, bal} = $$$ minimum total length of the string with the first $$$i$$$ characters processed in the first string, $$$j$$$ first characters processed in the second string and the current balance is $$$bal$$$. Transitions can be made in a straight-forward way (nested loops) but you should do them carefully or by bfs/recursion.

Out of curiosity, is there a solution faster than cubic, or is the n^3 solution the fastest intended solution?

I tried to come up with some faster solution but failed :( Maybe some cooler guys found something interesting.

You are the coolest! :D

Actually, because problem limits were low, I just used dynamic programming.

My state was (current unincluded character from S, current unincluded character from T, current bracket prefix). For some reason that I do not quite understand, the bracket prefix will not go above 200 and thus my state is 200^3=8000000 which is good.

My transition is "add open bracket/add close bracket" depending on whether they are possible operations. I store which transition is better so that I can backtrack later to construct the bracket sequence.

It passed the tests, so I think it's probably correct, but that was one of the ugliest case-check DP I have ever coded. Very unlikely to be official solution.

In my solution, there is no case-checking: pastebin

Any hints for E?

Multi-source bfs on the transposed graph.

with odd distance: 0) and even numbers to the second(with even distance: 0)bfsusing first & second queue respectivelysample code: 66742609What is the need for the transpose of the graph ? why a normal graph ( edje from i to a[i]+1,a[i]-1 ) will not work ?

Read this to understand

Yes I read it after posting the comment. Nice question.

Take 2 additional nodes, and reverse the graph...Think about it afterwards.

Form a graph from a[i]-i to i and a[i]+i to i.(a[i] -i >=1 , a[i]+i<=n) traverse the adjacency list and insert points on the other side of the edge in the queue if parity of both points are diffrent. (these points will have minimum distance which is 1). perform bfs.

Hello ; I constructed the graph in the same way ; but then I was doing DP on this graph...What I did was that let say node u has immediate child 'v'. Now if parity(arr[u]) != parity(arr[v]) ; then ans[u] = 1 ( This means that we may reach from u to v using only 1 step ).Else ; from all children of node u ( Which will be all v ) ; we may find the answer to node 'u' as ans[u] = min ( ans[u] , ans[v] + 1 ).But this gives me WA.Do you know what might go wrong in this approach ?CODE

There may be a cycle. So it might possible that you are not updated the current node and it calls again from its child.

Could you please elaborate a bit..

I understand that there are cylces. I understand the the child might have an edge that is directed back from child to parent ( Or in general from child to some ancestor ).

Doubt : When we came to that child ; we will come only after visiting the parent ( ancestor ).

So even if there is an edge from child back to the parent ; we won't go over there again as the parent is visited ; and we don't re-visit the nodes in dfs.

Clearly I have not understood something ; can you please elaborate a bit more...

Thanks !

Let take a node having three children{p, n1, n2, n3}, and there is a cycle b/w p and n2. Now your value of p = min(n1, n2, n3}, but when you go to n2, p is already visited but its value is not updated as it depends on value returned by n2.

Ah I see... So you mean that by this we will never update the value of n2 as it's value would have been updated via p ; but P is itself not updated yet as it will get updated in the backtrack move of dfs.

Have I followed?

correct. check this, it is easy to understand

Thanks a lot for the help :)

How to solve E. I thought of bfs + dp but couldn't implement.

Check this comment.

That comment answers F.

There is no constrain in problem B that length of string cannot be zero. Empty space should also be taken as correct input. Attempting to use this testcase for hacking shows invalid input. Is this intended?

There are no empty strings in every test and empty strings are not allowed to input at all. Seems like it would be better to mark this in the problem statement more clearly.

Am I the only one who accessed CF from http://m1.codeforces.com after solving A ?

The main site did not open for almost 2hr.I thought Round will not be rated but since 2200 users solved d, i think it will be rated.

me also. I can not access codeforces.com after 10 minutes.

Every day I have headache there is got to be a CF round SMH.

and I think I'm the only person who solved E but not D.

https://codefoces.com not working during the contest and I was thinking that my internet stopped working wasted my 10minutes

Yeah mine also, code forces stopped working after solving A .

It is from your side site was running perfectly ok :)

The server was down throughout the contest. Did I only face the issue??

Organizers please make the contest unrated as the site was down during the contest.

Not a valid reason because m1 website was up for the entire contest.

How would I know about it?

General knowledge

this is not at all a valid reason for contest to be unrated .I also face the same problem , but then i shifted to m1 .

I think the internet issue / connectivity was the problem and not codeforces "down"

Need help in E. I thought of the dp solution, i.e let's start visiting every element and finding whether the given conditions satisfy or not. 66716159

MikeMirzayanov it is a request. I wasn't able to access the codeforces website after 9 minutes and hence wasn't able to continue with the contest after a wrong submission of A. This is leading a drastic rating drop for me. It is hence my humble request that if it be possible then please do not allow for my rating to change. As a proof that I could have done it, I have submitted another solution of A with a minor tweak. It works just fine and I was ready with it after a minute of my wrong submission but wasn't able to access codeforces due to unavoidable circumstances. I hope you'll help me in any way if possible.

Why you did not continue with any of the other options the management has given ( m1 , m2 , m3 websites ) ?

bro m2.codeforces.com and codeforces.com were simultaneously down and not only for me but for many candidates. As a result, I left the contest as I was unable to access it. Many times this has happened but every time the contest is unrated then. After one hour when I again checked codeforces.com it was still down but m1.codeforces.com was working. This is wrong I mean why 2 sites are down while the other two were working. The site was completely down for 2 hours. As soon as the contest got over, it was active again. It will appear as a case of partiality with many of the contestants if the round is kept rated. I request MikeMirzayanov sir to please look into the matter as it is not only me complaining but many other users doing the same. There is a reason behind this complaint.

i got a small problem in my code in problem F if someone can help me i just did dp[curr positions in s1][curr position is s2][diff between open and closed brackets] i will represent it as dp[curr1][curr2][val] i can made transitions just if after the transition the val will stay non-negative and then i know the length of the answer is less than or equal to 400 so if length > 400 or the val is > 200 i will just return inf that is my first submission 66726623 which just returned inf and that is my other submission 66727771 which i just return when siz > 1000 and it got accepted can someone explain the what is the problem please ?

Thank You Vovuh I Loved this contest and I Love Div Three <3

Still after being hacked ?? :))

it's ok :(

Please give hint for F.

Think of a dp with transitions similar to LCS and more state parameters.

You can find my submission here. :)

I felt

Fwas implementation heavy for those who are comfortable with top-down dp, especially the backtracking part.If you can't wait to see the official editorial, come to see My Unofficial Editorial :)

Like to see comments and responses from you guys!

I think A can be solved on much easier way.

just calculate sum of current distance from given input. Let say it d. Then max(0,d-4) is answer.

Wow... you are genius!!!

Movement for friend who is in the middle doesn't make any change. Moving left one right will reduce distance by 2 similar for right one. You can reduce at most 4. Finally check reducing making it negative or not.

Can anyone explain how to approach problem B?

Hint: Try the move in a rectangular path.

First count each occurrence of letters.

To be able to return to initial position you need R = L and U = D so you can pick the min.

Then If one of the directions is equal to 0 you can only move at most one in other directions.

Finally you can construct result by moving in a rectangular path (ex: URDL)

Why if one side is equal to zero then it can move at most in one direction Ex: UUUDDDDD There is R and L is equal to zero. 3 U's and 5 D's. So answer must be 3 — UUUDDD But answer is 2. Why?

OK i got it!

If you go one step right then you also need one step left to come back ,similarly for up and down ...another case is if you can't move up of down then you can't move left and right more than 1 ..hope its enough for this problem

How would you do E? I tried BFS with adjacency vector, but no avail :(. It gives TLE on test 8.

UPD 1: I tried again this time with an array that stores the closest node with opposite parity to make my code faster. Also TLE on test case 8.

66742260

After moving to position 10, you can make 1 more move to position 6 (10 — 4 = 6), position 6 has value 5 which is odd. So that is why the answer is 3.

the answer for 10th position is 1. the answer for 8th position is 3 because : first you move to (8-4)=4th position which has value 6 which is also even (val(8)==4) so you have to move again to pos (4+6)=10 which has value 4 . then you move to pos 6 which has value 5 that is odd . 3 moves

"Can't read or parse problem descriptor"-Anybody else having this problem?

Same

The error is gone ^_^

what is the idea for problem D

See https://codeforces.com/blog/entry/72086?#comment-563624

For each element, remove it and then maximize the ans. For this we try to maintain two arrays(st[n] and ed[n])

st[i] will store the length of contiguous subarray starting from pos i.

ed[i] --------------------------------------------- ending at pos i.

Now if you remove the i-th element check the answer after merging left subarray and right subarray if possible to merge(left element < right element) and maximize the ans.

My solution

Better Implementation

oh ..really it was not hard one ...

thanks

There are only two situations:

So the easiest idea is just to implement this two process, and then take the longer length as the answer.

What is the logic behind problem E

I still can't figure out why this code gives a negative result for problem A.

Somebody help me finding the bug which I can't find. Here's the code 66703687

Changing your array decltype from Long[] to long[] gave AC

I just noticed something like that for my very first time. It works for values to 127. But after that from 128 it doesn't check the equality normally. For example,

1

127 127 127

This test case goes fine. But

1

128 128 128

This doesn't go fine.

Don't compare objects using ==. Use equals().

Java has a cache of numbers in range [-128, 127], that's why small tests work.

Thanx. I noticed that too. I just didn't know "Java has a cache of numbers in range [-128, 127], that's why small tests work."

Already updated the code 66762318 Now it worrks. I submitted this 4 times during contest and lost my precious 1 hour. My bad.

And if you use IDE, you can't make such mistake.

Eclipse didn't notice it!

Seriously dalex you are using android studio!!

I use Long[] instead of long[] when I need to sort the array so that it sorts in guaranteed O(nlogn) time complexity. For primitive array java sometimes give O(n^2) time complexity for almost already sorted array. That gave me TLE in a previous contest problem.

Why are you so worried about time complexity when your array has length only 3.

You can not compare two object Long using != always.

You can look here for details

Can I know why I got skipped

maybe you submit two answer that get accepted?

Actuallly Igot skipped from the whole contest

idk man,that's unfortunate.

My rating should have increased by 9 according to CF Predictor but instead it decreased by 5??

when the editorial will be published...??

Is there some error in rating change? The rating predictor predicted a +102 while I got only +74. How such a huge difference?

According to predictor my rating should have increased +9 but instead I got a -5

No. You might have checked predictor before system testing.

It is showing +102 now too.

You are absolutely right. In my case, it predicted correctly. I believe there might be some issue with the predictor.

Low tests in D problem :( My submission got passed but then failed at test 39.

Auto comment: topic has been updated by Vovuh (previous revision, new revision, compare).The editorial update at the top is looking a little weird and confusing as compared to other contests' blog.

I pinned it at the top because I thought that it would be more visible. If it's weird I'll post it as usual at the bottom. Sorry.

Yeah I think that'll be better of you post it at the bottom. Just that I have been used to looking at it at the bottom, and I believe other people too. That's why I found it weird.

Problem D is very similar to this problem.

Screencast of my testing is available