<almost-copy-pasted-part>

Hello! Codeforces Round #575 (Div. 3) will start at Jul/24/2019 17: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 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**: I also would like to thank Ivan BledDest Androsov for help with problems preparation, and also danya.smelskiy, greencis, chenjb and STommydx for testing the round!

**UPD2**: Editorial is published!

**UPD3**: I also would like to thank my friend Maksim Ne0n25 Mescheryakov for improving tests of the problem F! :D

Sofa!

Vovuh makes a lot of div3 rounds!

If you are to say

"You will be given 6 or 7 (or 8) problems"to the notice, why don't you announce exact number of problems later?Nice! A round just for us newbies.

How can a normal round be ICPC rules!

Hope the statements are easy to understand.(I understand the problem wrong for too many times!)

Vovuh: Announces a new Div. 3 round

Me: Aw shit, here we go again...

Thanks to Mikemirzayanov for this great platform. You are doing a tremendous job. making 2 or 3 Contests almost in every week.. :)

MikeMirzayanov, after some updates on Codeforces when I copy my code into IDE on every empty line there is a strange symbol which brokes my compilation. Is it going to be fixed?

Maybe anybody had such problem, how did you fix this? I use Codeblocks. Few time ago there wasn't such problem :(

It is not an error.It is a common thing,but yeah it causes problems for most of the users. In sublime-text i paste the code with Ctrl+Shift+V and it works for me

I'm also facing the same problem. Whenever i try to copy my code from CF using

copybutton and paste it on by IDE , the code doesn't compile. However , when i copy my code manually using cursor the code does compile. Strange.MikeMirzayanov , please fix this.

I'll fix it.

Thanks a lot!!!

I ran into the same issue. If you're on Linux/Mac you can use

`perl -pi -e 's/[^[:ascii:]]//g'`

to strip all non-ASCII characters from a file.Hope the statements are easy to understand and very short.

i wish this round will be a real div3 not a hidden div2

why the hell it's called div3? obviously this is another div2 round

foul blog. It's obviously a div2 round.

bro i unexpectedly solved 5 problems..i am sure this is div3 :)))

then u have to practice more buddy..!! this was a very balanced div.3 round.

I wanna be blue.

For blue you need 185 point it means you must solve 4 or 5 problems in div 3

Certenly,solved only four or five problems in div.3 is not enough to became a Expert.At least six(or AK!) problems is enough.

I don't want to become pupil

Serouisly!!!! This is supposed to be a Div3 Round?

Queryforces!

wtf this is harder than a div2 contest

lolololol

How to solve problem C?

Make a variable to store the area where any robot can get. This area whould be a rectangle, so just store x and y of left bottom angle and x and y of the right top angle. Next for the first robot get the area where it can get. In python it would be like this:

where r is the array of all robots an pos is an array in shape of [[x0, y0],[x1, y1]]. Set all robots reachable area as first robot's, because we've checked only one so far. Now get the same area for all of the other robots and compare it with all robot's area:

This huge line can't even fit the screen, but it checks if current robot's area intersects with all robot's area somewhere. And if it does, then set all robot's reacheble area to this intersection area:

And then if our loop through all robots didn't break, then it's possible for all robots to reach a single point. It's any point in their area. 57687425

Keep the four variants: min_left, max_right, min_bottom, max_top

if f1_i = 0, min_left is not less than x_i

if f2_i = 0, max_top is not greater than y_i

if f3_i = 0, max_right is not greater than x_i

if f4_i = 0, min_bottom is not less than y_i

if on i'th iteration current value of some of four variants don't meets this conditions, update this variant

My thanks to Vovkaez and to kazak. I almost got it during contest, I changed some conditions. FeelsBadMan

Good problems, have to sweat in each problem but it was nice. The round more resembles div2.

So, how to solve D2?

Use prefix sum to count the number of incorrect positions in string from pos 0 to pos i, and do it for the 3 ways: RGB, GBR and BRG. Then iterate over al possible k substrings and get the minimun answer by doing: pref[i]-pref[i-k] for all 3 different prefixes.

You can also use sliding window/two pointers technique to solve in O(n) My code: https://codeforces.com/contest/1196/submission/57674284

Hi guys,

In Problem C, even O(n) complexity algo is getting time limit exceeded. Can someoone help here, please ? http://codeforces.com/contest/1196/submission/57694392

MikeMirzayanov I believe the time complexity for Java should be increased as i tried fastest possible i/o in java, still i am getting time limit exceeded.

nothingtolose I believe it is a bad idea to allocate

`new int[100005][6]`

on each testcase. Imagine the number of testcases $$$q=10^5$$$.I got 3 of them :(

I just finished 1 of them which makes me so sad,how can i finish as many problems as possible?

You just gotta keep practicing bro. I was in your position a year ago but this time I managed to solve all but the last one. Just keep at it!

Any more details on how you progressed during the year?? Would be helpful to know...

It was similar to D2. How are the questions difficulty supposed to be? Div 3 B = div2 A? Div 3 c = div2 B?

Also how to solve D1 & D2?

Overall good contest..

There is 3 type we can do $$$RGB, BRG, GBR$$$ and for every $$$i$$$ $$$mod$$$ $$$3$$$ position we need to check if this position equal to that $$$3$$$ substrings, because of it we create $$$3$$$ counters which counts all positions where $$$i$$$ $$$mod$$$ $$$3$$$ of string is not equal to the position, and for

D2we just need to find $$$pref[i] - pref[i - k]$$$, because its like we adding one letter by deleting first letter, to understand it you can check my solution 57672041Python don't work for D2, :'(. Got penalty and had to rewrite code in C++.

Same here. Had to rewrite B too, though I optimized it in C++. But D2 was exact translation.

Hey vsinha! Would you like to try my previous comment and submit the python code for D2 and B again to see whether it now satisfies the time limit?

It worked. I resubmitted D2 and it got AC. Thank you very much for the tip. I'm not submitting the python version of B, it perhaps suffers more from a poor algorithm than IO limits.

=) I think for B as long it is an O(n) algorithm, it should work perfectly

Hi islingr! I looked at your D2 python code. Do you want to add the lines

on the top of your code and submit it again to see whether it will now satisfy the time limit?

Using this I could only pass one extra test case and then the it TLE'd on the next test case failed.

However, making a few changes in the code and using this did make it work. Thanks.

Here's the final code which worked.

I really liked problem B, spent ~ 5 attemps to understand that i need change int->ll

how to slove it ?

You can calculate remainder of sum on prefix, if you find some place where remainder is odd, add it to answer and say that now remainder is zero(we calculate remainder of sum on prefix from that position). Now leave first k-1 elements of that array add n to answer and check that all ok. All ok if sums on that subarrays is odd and answer have size equal to k.

you're right,it seems simple,but during the contest,i thought the way,however i couldn't prove it,so i try to dfs it,which got me into trouble. What a sad evening....i can't fall asleep.

Here is my code

I initialized an array of size n; then, for each element, I determined if it was even or odd, and kept track of the total number of odds. If it was odd, I would mark that array with a "1"; if it was even, I would mark it with a "0".

Now, if the number of odds % 2 doesn't equal k % 2, or the number of odds is less than k, I printed NO.

Otherwise, print YES and print every index of an odd number and keep subtracting from k until you have one left; then, just print n as the index.

I'm bad but it worked.

I was also doing the same , don't know what's wrong with my soln

got it . I was failing at test case like this when last element was not odd . 1 10 3 2 3 9 4 6 4 2 5 8 8

For Problem C:

I sorted according to X then according to Y and found intersection point for X and Y.

The intersection point will be a point for which on left side all robots are coming towards it or equal X coordinate and on right of it all robots should be coming towards it or equal X coordinate.

Same thing for finding Y coordinate.

Am I missing some corner case here ? As I was getting WA on test case 5.

Were there any scoring table on the right side, there were not for me.

anyone has a good explanation for problem E before the editorial shows in the next era? :)))

Assume b>=w (you can shift all squares over if needed). Make a line bwbwbw...bwbw until you run out of w's. Then you can place the remaining b's by connected them to the top or bottom or left of this line. If there are still b's left, it is impossible.

i checked your solution and i think i got it..thanks..nice aproach..

amazingly when i submit my d1 code in d2 it worked correctly for the first 15 testcase

i almost thought that it is going to be accepted

It feels bad man. When I submitted D1, I had only 5 minutes left. And I thought okay now I am done I guess. But It actually worked perfectly fine :(

hhhhh

I think k can be $$$ 10^5 $$$ in problem F and you can see my solution.

https://codeforces.com/contest/1196/submission/57688661

can you please explain your approach?

During the contest, for Div2-B, I thought that the only condition for "NO" answer is

if((k%2==1 && sum%2==0) || (k%2==0 && sum%2==1)) pf("NO");

Here sum is the sum of all numbers in the input.

Now I added another condition for "NO" which is ans.size()!=k and it got accepted. Can someone give me a testcase which can help me understand this behaviour?

5 3

2 4 6 8 10

Even with just the first condition, it's giving correct answer "NO". I want to know a case where this condition is alone not sufficient.

5 2 2 4 6 8 10 rr459595 answer Yes but really answer is NO

Oh, thanks. So it's just a necessary condition and not sufficient :(

there are only two condition of "NO" let n=no of odds 1)if n<k 2)n>k and n-k is odd

1 4 2 1 3 5 4

k%2 ==0 and sum%2=1. So the answer is "NO" and the answer is really "NO" right? How is first condition failing?

1, 4 2, 2 4 6 8

Any hints on how to solve Problem F?

You can see that if you sort all edges by weight, the k+1 edge and another that weight more than k-th aren't in our answer(forger for them). Now you have k edges, up to 2*k vertices have at least one edge, and you can run Floyd–Warshall_algorithm for vertices which have edges and get AC.

You will need to use Floyd-Warshall's algorithm to solve F. Its asymptotic time complexity is O(N^3) and space complexity is O(N^2), so you cannot employ it right away.

However, there is one thing you need to notice: if a path is k-th in the final sorted distance matrix, it will not include any edges that are longer than the k-th shortest edge given. (Agree that the k-th shortest path is obviously not longer than the k-th shortest edge, at least because the set of edges is a subset of all paths and we already know k — 1 one-edge paths shorter than k-th edge).

Now sort all the edges and pick out only k shortest ones. Compress the coordinates and create a graph consisting only of these edges.

Run Floyd-Warshall's, which will have the asymptotic time complexity of O(k^3).

Slice the distance matrix you're running Floyd on across the diagonal. Find the k-th minimum on any of these slices (they're the same). Output the result.

Dafuk is wrong with me Spent 1 hour on C and 17 minutes on D2 and D1

Is there some added advantage on asking query-based test cases? Do they do it so they can test on more cases this way?

From what I understand it's purely for ease of judging

I think questions based on online queries ( and even offline ) pose kind of a challenge to the solver compared to the other type because of vast number of queries to answer in such small amount of time and is more practical i think ? Hope the answer helps!

Are you saying that having several separate test cases is worse than having the same test cases compiled into a single query-based test case?

I'm assuming that the former works by generating a single output file from the code and running it several times. The latter would work by running the same output file only once in this case. But even then I don't see how there would be a significant benefit from doing this.

No, sorry for any misunderstanding, what i meant was that sometimes query based questions require a more algorithmic or cunning approach compared to the ones which doesn't. But i cannot say the same in this contest though(Though i agree that many might disagree with me).

Yes, that makes sense if the tester is expecting an $$$O(1)$$$ or $$$O(log n)$$$ solution. But I suppose for $$$O(n)$$$ and $$$O(n log n)$$$ solutions, it hardly makes a difference.

Someone really wants to get their opinions established in D2

Implementation, implementation i esche raz implementation!

Any suggestion how to solve F, without Floyd–Warshall_algorithm? I solve it by Floyd–Warshall_algorithm, but I belive that exist some quite good idea how to solve without Floyd-Warshall_algorithm, maybe for k<100000

Blin! I don't solved B, where odd subsegments, cos i forgot to write

`0LL`

in`accumulate(a.begin(),a.end(),0LL)`

, i wrote`accumulate(a.begin(),a.end(),0)`

. This is obidno!Sometimes such shit happens. But do not be upset.

What is your most offensive error or stupidness in contests? (My subj is here)

I build segment tree with vector in parameters, get memory limit and I spend a lot time to see that so bad, because vector each time copied.

Please notice these two codes 57693377 and 57690563, (2018030102067 and Mole_Q) i think they are cheating. 57676867 and 57674699 2018030801054 and 2018030401051 are similar, too.

Wow, nice job. But i'm interested about how did you find it that they are cheating

No d1 solutions are very close

57693377 and 57690563 i think they are cheating.

How to solve problem E ?

if(B>=W) build such structure bwbwbwbwbwbwbwbw after you can add b to top or to bottom or to left if you add all and you must add more answer is no this is case (B>3*W+1) else same things as B>=W but swap white and black

deleted

I think it can be solved like this : Think of it like a tree , just with this constraint that the tree cannot have more than 3n+1 of the colored nodes which are in majority.By drawing 1 or 2 configurations, you can realize that to get maximum number of nodes of the majority type, one of possible tree is a straight one.So if you select minority nodes = a, then connecting those must be a-1 majority nodes, and the rest can be taken till we fill the required quantity of majority nodes! Hope it helps!

Consider the picture for example( :D) : Link

Mechorca 2018030401093 2018030801054 maybe they are cheating

I am just wondering, what is the purpose of

hackingin a round where the tests are strong ??I'm not saying that I want what happened in Educational Codeforces Round 67 (рейтинговый для Див. 2) to happen again, but won't it be more fun if there was a problem that has a test where everyone forgets about ?

Couldn't solve E due to lack of time during the contest. Now realizing, easiest E ever??

me too :(

Why does a BFS solution of E fail while one with DFS pass?

i think it should solve with Dfs because we need to go deeper in a chain not by level so it make sense to use Dfs not Bfs

if we go by level then maybe there is some cells that have a common cell with white color (if white is the greater one)

i can draw something if you don't understand :)

Can you please give an example?

1 10 3

just trace your code for the previous test

Got it. Thanks

I cant make sure about this, but I wonder if this k shortest path routing can be used to solve problem F or may be Im wrong, let me know your thoughts. Why I know this? Because this was a topic for homework at my uni, and I chose this approach to find k-th shortest path in a weighted graph.

Big day for Codeforces. We set a new record. The total number of registered users on Codeforces Round #575 (Div. 3) is 12619! Our servers are ready for more. Let's see what happens next!

Great! Btw there was a little delay today, between submissions and judging (the 'in queue' period was larger than that in the usual rounds).

it cost me over 1 minute to show problemA

if e can be solved by bfs? help me !! 57713663

It is really frustrating that a O(n) solution written in Python3 (PyPy) can

exceed the time limitfor problem B!It seems that I am only reading in the values of n, k, l, and doing constant time comparisons in case of 200000 queries. Does anyone know any trick of how I can change the syntax to reduce runtime? I am attaching my code. Thank you!!

Python Code for Problem B

Update: It seems that using

`sys.stdin.readline()`

is much better than`input()`

, right?same here. this is my submission in python3 and got hacked https://codeforces.com/contest/1196/submission/57661674

Anyway to optimize the code or should I start to learn c++ again?

Java suffers from it too. Time limits or numbers should be a little easier. Well, now I know that printWriter is 10 times better than System.out.print and tokenizer is twice better than split... But it is just implementation...

For E I had used ideone not knowing that it was public. Somehow it looks like others have managed to submit my own code to E before I submitted it. I don't know what has happened and am very concerned. I do not know how to prove it but perhaps if you look at code style you can see that it is my code?

I apologise for mistake with using ideone, I did not know it was public in this way. Will not use in future.

Specifically, the void sol() function I use in all my submissions for the contest while none of those copying off me have used it in other solutions.

I sincerely apologise for the trouble that my use of ideone caused.

I'm not able to understand problem E properly. I mean if b=1 and w=5 why can't the answer be (2,1),(2,2),(2,3),(2,4),(2,5) since this is also a connected component.In this way answer should always be possible.We can print b & w coordinates in this linear fashion. Please help inspite of trying hard i'm unable to understand the problem.

if b = 1 and w = 5, you need to output 1 black cell and 5 white cells, so in a total of 6 cells. However, you only have 5 cells. In addition, (2,2) and (2,4) are white and (2,1), (2,3), (2,5) are black, so you actually have 2 white and 3 black instead of 5 white and 1 black.

Thank you very much.

For chessboards, adjacent cells should have different color, and it is stated that (1,1) is painted white. Your answer is connected, but (2,1) is black, (2,2) is white, (2,3) is black, (2,4) is white, (2,5) is black, which is 3 black and 2 white. one black cell can have at most 4 adjacent white cells, so the proper answer for b = 1, w = 5 is "NO"

Oh.Now I get it.Thank you so much for taking out your time.

A very truly great contest for rating less than 1600. All problems were of good quality. Enjoyed the problems.Please make Div.3 like this only.