Saturday there will be COCI exam in this link: http://hsin.hr/coci/ You can study for the old COCI's here: https://oj.uz/problems/source/122 Also this site has an online judge. The contest will begin at:17.11.2018.14:00 GMT/UTC and it will take three hours.

Auto comment: topic has been updated by A.Kaan37 (previous revision, new revision, compare).Good luck to everyone.

did the registeration begin?

No.

When it will going to begin?

In two days.

Registrations began. you can go to the site with this link: http://hsin.hr/coci/ look at to contest 2

5.00 hours before the exam begins

Thanks dude. I'd miss if I didn't see the topic.

No problem!

Will it take five hours or three hours (same as the previous one)?

it will take 3 hours

Where did your get that information? Here it says

threehours andfiveproblems.Yes

lol so is it 3 or 5?

As far as I know, 3 hours, 5 problems.

thank you

Last 1 hour to the contest

Is the site down ?

Auto comment: topic has been updated by A.Kaan37 (previous revision, new revision, compare).How to solve second? I solved the third but not that one.

Thank you, I got the idea.

How to solve the third?

Main idea: We find the answer by counting the number of the ranges for each bit. For that, root tree at one and calculate top to bottom xor's. Now, traverse the tree and you can count the number of the ranges by counting {(0,0) and (1,1)} or {(0,1) and (0,1)} pairs.

Code: https://pastebin.com/Sr9EskiG

UPD: I got AC.We keep 2 arrays, row[] and column[] which store 2 values; 1 if someone at some point has seen a square that was blocked and -1 if nobody saw it just yet. First we go from left side through all rows, if input at the current row is -1 we set row[current_row] to -1 and continue, otherwise we set both row[current_row] and column[input] to 1. Then we continue to other three sides and we will have 2 cases: 1. if input is -1 then we ask if someone before has seen a value in that row/column before (i.e if element in array row/column is 1), if someone did see it then we print "NE", otherwise continue 2. if input is 1 then we ask if someone before hasnt seen a value in that row/column before (i.e if element in array row/column is -1), if someone didnt see it then we print "NE", otherwise continue

Code: https://pastebin.com/KNqzESdU

See also Noam's notes below.

We iterate over the row number/column number. Consider the

i-th value in theLarray,L_{ i}. Since the firstL_{ i}fields in rowimust be empty, we must have thatU_{ j}≠i- 1 andD_{ j}≠N-ifor all 1 ≤j≤L_{ i}. Also the (L_{ i}+ 1) th field in this row must be a blocked soU_{ L i + 1}≤i- 1 andD_{ L i + 1}≤N-isince otherwise this blocked area would have to be empty. Both of these conditions can be checked inO(1) by pre-constructing various arrays.Then just do this for

U,RandD.When standings will be avaliable?

Commonly within an hour

Results are out!

Link for the lazy: https://evaluator.hsin.hr/results.php

Brief solutions/hints for the problems (except A because there's no reason to):

BFor both rows and columns, you get 2 ends

X,Ysuch that beforeXand afterYthere must be white,XandYmust be black and between them it's unknown.For each row find these endpoints, and then iterate over all columns and check whether some cell that needs to be black according to a column, has to be white according to a row (this can be checked in constant time). After all these checks, swap between the rows and columns and check again.

CHint: solve separatedly for each bit (so each node has a value 0 or 1). You can solve it using a dfs run on the tree.

DIf

Kis large enough, then at some point you will jump between 2 adjacent cells.Kshould be at least (approximately) . IfKis smaller than twice this limit, you solve by doing dp in . Otherwise you solve upto the limit, and find the best pair of points you should jump between (It's probably one with the maximal sum but there's no need to solve further).EBrief explanation/hint of :

We first reverse the order of rectangles (and also do coordinate compression). A rectangle is good now, if none of the previous rectangles took any space of the current rectangle. We split the rectangles to blocks of size

K, within each block we check all pairs of rectangles for intersections in (total). For each block we also compare it with all previous blocks in (per block) using sweepline and a segtree: past rectangles represent updates, current rectangles represent queries. The (lazy)segtree I made supports setting each valueVin a range tomax(V,C) for some constantC, and range query for max.Kshould be .Edit: Looking at the results, I think my solution to D takes a little too much time. Can anybody else explain their solution? Also for E I'm not sure if my solution can pass in time, I didn't submit it, will check soon.

Edit2: This solution for E recieves TLE on the last 2 testcases when

Kis 1000, but it passes with 1500. Anyway, did anybody have a better solution?I spent last couple of hours trying to solve D.

I'm not quite sure I understand some of your points.

Do you mean that, if

K<NMthen we run the DP?I also thought about this, but don't know how to prove it. Do you have some insights?

This is the part I am most confused about. Let's say we pick some pair of adjacent cells (

x_{1},y_{1}) and (x_{2},y_{2}). How do we choose the number of times we'll jump between them and the lengths of the paths from (A,B) to (x_{1},y_{1}) and from (x_{2},y_{2}) to (A,B)?I was thinking about choosing some lengths

k_{1}andk_{2}, then using DP to findf(k_{1},x_{1},y_{1}) — maximum weight of the path from (A,B) to (x_{1},y_{1}) usingk_{1}steps, same withf(k_{2},x_{2},y_{2}). So we are left withK-k_{1}-k_{2}jumps that we can do between (x_{1},y_{1}) and (x_{2},y_{2}). But what are the limits onk_{1}andk_{2}in this case? If we choose someLas the limit (i.e.k_{1},k_{2}≤L), then the complexity will be , soLcannot be very big. But choosing smallLwill lead to nonoptimal answer.Here's what finally worked for me:

If we assume that when

Kis large, we'll be jumping between two cells at some point. Then after someksteps, wherek<K, the weight of the optimal path will be increasing by the same amount each 2 steps. In other words for some large enoughk, it should be true thatSo we can use this difference for the rest

K-ksteps and the result will look something likeBut how do we choose large enough

k? I don't know :) Maybe someone can help with this?Here are some values that I tried:

k=NMandk= 2NM, was not enough, giving WA for some test cases.k= 4NM, passes all test cases, but very close to time limit in some.k= 15000, also passes all test cases with run-time <1s, but I think it might not always be optimal whenN=M= 100, since for some smaller casesk= 2NMwas not enough.