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 copy button 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 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.

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

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

I don't want to become pupil

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:

    if r[0][2]:
        pos[0][0] = -100000
    if r[0][4]:
        pos[1][0] = 100000
    if r[0][3]:
        pos[1][1] = 100000
    if r[0][5]:
        pos[0][1] = -100000

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:

        if robot_pos[1][0] < pos[0][0] or robot_pos[0][0] > pos[1][0] or robot_pos[1][1] < pos[0][1] or robot_pos[0][1] > pos[1][1]:
            print(0)
            break

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:

pos[0][0] = max(robot_pos[0][0], pos[0][0])
pos[0][1] = max(robot_pos[0][1], pos[0][1])
pos[1][0] = min(robot_pos[1][0], pos[1][0])
pos[1][1] = min(robot_pos[1][1], pos[1][1])

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 Guslix. I almost got it during contest, I changed some conditions. FeelsBadMan

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

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.

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

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 D2 we 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 57672041

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

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

import sys
input = sys.stdin.readline

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

how to slove it ?

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.

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

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

can you please explain your approach?

5 3

2 4 6 8 10

1 4 2 1 3 5 4

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.

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!

Implementation, implementation i esche raz implementation!

Sometimes such shit happens. But do not be upset.

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

No d1 solutions are very close

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

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

me too :(

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

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

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

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

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.

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"