Recent actions

Now it comes true.

Created or updated the text

Oh right! That's quite tricky to see. Thanks for your answer!

I think in one of the first blog posts introducing ordered_set to codeforces, they concluded that it was twice as slow as recursive segtree. My recursive segtree solution takes 1400ms on the problem, so it kind of makes sense that it could TLE.

I honestly dont know much about hacks. That is why I asked. If I knew it, I wouldn't ask.

I have a similar solution but it is giving TLE on test case 3. Can you help me out? code

Why is my solution for problem E giving TLE. I used line sweep algorithm with ordered_set. Time complexity: n^2 log(n)

Was a very convincing explaination. Thanks


Without loss of generality, assume that there are more vertical segments, than horizontal one. Now number of horizontal segments is no more than N / 2. Let's iterate over all unordered pairs of horizontal segments (there is no more than (N / 2) * (N / 4) such pairs) and AND their bitsets, which is N / 32.

Could you explain how you got the complexity as N/2*N/4*N/32. Thanks in advance.

It's maybe because of the fact that 'Isn't it illegal?' is a stupid question?!

Thx , that worked

Thank you

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

Problem D

How to find pattern using generated ans sequence for several n,k??

It's not my pragma, I heard about it here

With your pragma my 576ms solution now works in only 156ms.

You're right. But this is kind of the same mistake I made (I had 16 wrong submissions): "On every horizontal-segment-end you update the segment tree (i.e. decrease the corresponding y value by 1)"

The thing is, you have to store the start point of the horizontal-segment-end, because if you decrease by one and the segment has started after your left segment, then you'll end up undercounting the number of segments.

Can anyone please tell when will the editorial be out ??

Wow, cool, must learn about it.

Who wrote solution for E with fenwick tree and complexity O(n^2logn)?

Your TLE-4 code runs in 1231ms using pragmas 57094459

My bitset solution gave TLE-5 but using pragmas it passes in 1965ms. To optimize it should we make bitset matrix based on smaller count of horizontal or vertical segments?

LOL, I've pushed N^3/64 in E, really want to know the right solution. At first I've used bitset, which gave TL 4. After rewriting bitset myself, it gave AC in less than 600ms, that's amazing.

I thought of that during the contest but i thought that would get TLE much easier than the log n solution since it's essentially O(N^3). Interesting to know that works too.


I'm also hoping to read it and check my opinion and code...

Let's fix two vertices on the left side (A and B). Let's call vertex C on the right side common if C is connected to both A and B.

This will be too slow, isn't it?

Could you explain what do you mean by this "__Lets there are K common vertices on the right_," Thanks in advance.

You can find a number of common vertices K by taking a square of an adjacency matrix. And taking square of a matrix can be done in O(n^2.8)

I didnt solve it so maybe I am not objective, but its nothing special. Still, of course its better than theoretical game theory problems which involve grundy numbers or something. I dont think anyone loves that.

When I was reading your answer I wondered what exactly "update the segment tree accordingly" means. If I understand correctly then you do the following: Once you fixed a vertical segment as left side of a rectangle you loop over all segments to the right of it: On every horizontal-segment-end you update the segment tree (i.e. decrease the corresponding y value by 1). On every horizontal-segment-start you do nothing. On every vertical segment you add some number of new rectangles to the result (as you described it). The reason that no operation is done on horizontal-segment-start is that the horizontal segments that start after our fixed vertical segment do not intersect with our fixed vertical segment and thus should not be considered. Did I understand this correctly or am I missing something?

Just ACed it. Thanks

editorial please??

Does cf has a YouTube channel. I guess if there is one on which veduo solutions to the contests can be provided , it will be of great help to beginners atleast .

A bad selection of words.
What I meant was that this is rather known. And would have got faster submissions that B/C.
I read about it (simply checking value of modulo K+1). When I read some introductory level game theory blogs. Thats the reason I used "standard Nim".

How is "up to $$$K$$$" standard Nim? I think "up to $$$K$$$" can be done by simply checking value modulo $$$K + 1$$$?

is it really completed ? i see very few testcases

I love contest too !!

Quickest system testing seen on codeforces :D

System testing start

Make an events array of three types of events: vertical segment, horizontal segment left point, horizontal segment right point plus one. Sweep from left to right. At every coordinate first process all horizontal segment updates in a segment tree (update the y-value with plus or minus one). If you reach a vertical segment, consider it as the left side segment. Then for each fixed segment loop over all events to the right of it and update the segment tree accordingly. If you encounter another vertical segment, then add (number of horizontal segments intersecting both segments) choose 2 to the answer.

When system testing will start??

Probably not published yet.

will fail on 4 3 * . . * . . . . * . * * Your submission gives output as 3 but the answer should be 2 if u select 4th row and 1st column

May you tell me where the Editorial is :>

How to solve E

You can solve it in O(K*(K-1)/2) bitset operations, where K = min(horizontal, vertical) so in the worst case, K = N/2. Considering each AND operation runs in N/64 more or less, it's a good complexity ~ 250.000.000 operations which run in aprox 1600 ms

Fix a vertical line as the left side, add horizontal lines that start before it and finish after it. Now, sweep to right to see other vertical lines (as the right side of rectangle). Just keep track of horizontal lines (erase a horizontal line when you reached the endpoint of that). My code is easy to understand.

sir when editorial is going to be released?? need it .

i don't think that there will be much system failures . Pretest almost cover the test cases set.

We can move up in standings if we hack someone above us, right?

The problem is no one needs your solution .

Whoops, my mistake.

I am not able to understand why you people are downvoting. Is the solution not clear to you/ Is there mistake somewhere??

You can point it out if there is any.

Can you please explain your approach?

bu, you don't like.

No you're wrong, check his submission above !

ans1 will select first row yes, BUT ans2 will select the 3rd column and 3rd row which = 2. then, he output the min(ans1,ans2). so, according to your test case he still correct.

Yes , that's why i am considering both ways . What i mean to say that

1 . Find minimum row and it's respective minimum column and save it's ans . Let's say ans1

2 . Find minimum column and find it's respective minimum row and save it's ans in ans2.

Output minimum of 2.

For eg let's consider this case (s means '*' )

5 5






1 . selecting minimum row with least white tile . In this case there are four rows with 3 white tiles. (1,3,4,5) . Select any of them . Let's select 1'st row . Then for this row select minimum column keeping in mind of double counting of same white tile . we get (2,3,4,2,2) for respective columns (1,2,3,4.5) . Select minimum of them . We get ans1 = 3+2 = 5 .

  1. Now this time select minimum column first and find it's respective minimum row . Let select column 1 with 2 white tile and row 4 with 2 white tiles ans is 4.

Optimal answer is min(ans1,ans2) =(5,4) = 4.

I will be saved from NEWBIE!! [user:_seyed37_][user:Jefri_007]

Keep downvoating me. Go ahead.

Sorry guys, I dont understand why you are downvoting me. Is it a lot of bots from HubyBee?

Hey, Guys I just did question A checkout its solution: link

LOL,I forgot about that.

what do you mean ? don't you want to input the grid that's o(nm)

They are official participants for educational rounds. It is just that, the educational contests are unrated for them.

Is there a better soultion for B than O(n*m).

3 4 . . * * . . . * * * . .

1st and 3rd row have 2 white tiles each which is minimum. If we select first row we'll get 3 as an answer but if we select 3rd row and 4th column we will get 2 as an answer.

Fix $$$k$$$, and for each $$$m<=n$$$, $$$f(m)=A$$$ if Alice will win if the strip were to begin at $$$m$$$, and $$$B$$$ otherwise. Obviously $$$f(0)=B$$$ and for the rest, $$$f(m)=A$$$ if and only if exactly one of $$$f(m-1), f(m-2), f(m-k)$$$ is equal to $$$B$$$. (For the rest of the proof we will not deal with the size of $$$m$$$ with respect to 1, 2, $$$k$$$, the proof will still be the same with all those constraints added, just a bit messy).

We shall proceed by inducing on $$$m$$$ in each case of whether $$$3\mid k$$$ or otherwise. In either case, we observe that $$$f(m)=B$$$ means $$$f(m+1)=f(m+2)=A$$$ (reason being explained above). We claim that for the first case, $$$f(m)=B$$$ iff $$$3\mid m$$$, with base case $$$m=0$$$ explained. Now for inductive step, if $$$3\nmid m$$$ then either $$$3\mid m-1$$$ or $$$3\mid m-2$$$ and therefore $$$f(m-1)=B$$$ or $$$f(m-2)=B$$$, which follows $$$f(m)=A$$$. Otherwise $$$3\mid m$$$ and we notice that neither of $$$m-1, m-2, m-k$$$ are divisible by 3, and therefore by induction hypothesis $$$f(m-1), f(m-2), f(m-k)$$$ are all $$$A$$$, so $$$f(m)$$$ must be $$$B$$$.

Now $$$3\mid k$$$ is tricky: the first $$$k-1$$$ values follow from the previous case, but $$$f(k)=A$$$. We, instead, consider modulo $$$k+1$$$ and the first $$$k+1$$$ values (0, 1, ..., $$$k$$$) should be clear. Now let $$$m\ge k + 1$$$, which means we should consider $$$f(m-1), f(m-2), f(m-k)$$$. For clarity, consider $$$m_0$$$ as the remainder of $$$m$$$ when divided by $$$k$$$. The induction claim, as suggested by others, is that $$$f(m)=B$$$ if and only if $$$m_0=0, 3, \cdots , k - 3$$$. We have the following cases:

$$$m_0=0$$$, and $$$m-1, m-2, m-k$$$ are congruent to $$$k, k-1, 1$$$ modulo $$$k+1$$$, and by induction hypothesis it follows that all $$$f(m-1), f(m-2), f(m-k)$$$ are all $$$A$$$ so $$$f(m)=B$$$.

$$$m_0=1, 2, k$$$: obvious from the previous case.

The rest of the cases: since $$$3\le m_0 < k$$$, $$$m-1, m-2, m-k$$$ are congruent to $$$m_0-1, m_0-2, m_0+1$$$ modulo $$$k+1$$$. If $$$3\nmid m_0$$$ then either $$$m_0-1$$$ or $$$m_0-2$$$ is divisible by 3 and less than $$$k$$$, so either $$$f(m_0-1), f(m_0-2)$$$ is $$$B$$$ and this case is done. Otherwise, $$$f(m_0-1)$$$ and $$$f(m_0-2)$$$ are both $$$A$$$ so we only consider the last one, $$$f(m_0+1)$$$, which is also equal to $$$A$$$ since $$$3\nmid m_0+1$$$. This concludes the proof.

Sorry for the poor organization, I am writing in a hurry (though it's fun to do so :P )

Pretests too strong only 30 successful hacks so far

*$$$J_x = J_{x+1}\cdot(x+1)$$$

Had K been of order 10^3, then this could have been tried.

Assume k % 3 == 0. Let's iterate array from start. 0 is lose, 1 is win. So basically without the k jumps its all 011011011 or (011) repeating infinitely — start is losing, and you can get to start with 1 or 2 jumps so next ones are win, and third is always lose cause opponent wins. Now for first k cell we can't do k-jump so its all (011) then we suddenly can, and we jump to 0, so k'th cell gives us a 1 and the sequence ends like ...011011(1) last 1 being k+1'th position, or k'th index.

Next, consider this lemma : k — jump is useful iff it lands us from 0 to 0 without k — jump. In this case, we get a 1 in that position where we are jumping from and jump to losing position. So what does that give us?

At k+1'th index we have 0 again, because we end with three 1 and cannot do usual jumps and k-jump lands us on 1 too. K-jumps are useful only on every third position only, because we had a sequence (011). But every third position is 1 anyways, so we can discard k-jumps and we have repeating sequence of (011) starting from k+1'th index. This holds true until we get to 2*k+1'th index. Because of 111 shift, we have suddenly 0 at index 2*k+1 — k = k + 1 (try doing with k = 3 and 6 to see pattern easily) and we get again 1 at index 2*k + 1 and again there are three 1 there. You can use this reasoning to conclude that structure ((011) + 1) at the end is repeating, first (011) being taken k/3 times. Then knowing that, take remainder of n modulo k + 1 (counting last 1) and check. If we land on last index, return 1. Else divide remaining pattern modulo 3 and return 1 if remainder is 1 or 2.

Imagine you are in Cell(x, y), now you have to make sure all cells in this row and column must be black. This means some white cells need to be painted. Now how many white cells are to painted? For this, just store the count of white cells in each row and column. Now if at (x, y), cells to be painted, X (lets say) =(White Cells in Row 'x' + white cells in Column 'y'); just make sure if current cell is white, you subtract 1 from X because it will be counted in both row as well as column. Just find minimum of 'X' from all cells in O(n*m); Hope it helps.

I was thinking about it too, but I coudln't find any solution.

i have the same idea of yours but i can't come up with a test case that satisfy that.

actually, every time he choose just the first minimum row and this is not always correct, the second answer of the first minimum column got the optimal solution and vice versa.

anyone managed to get that test case guys ?!

I was thinking to model Problem D in terms of recursion in n and k and then try to find out value using matrix exponentiation. Did anyone else tried it this way?


How to solve B ?

Think only about i-1 and i-2. A means Alice wins and B means Bob wins. This is the winning pattern, starting from n==0: BAABAABAABAABAA. Basically, if pos%3==0 the ans is Bob. This happens because you only reach positions that Alice wins form this pos%3==0 positions. When k%3==0, the lowest position that change is pos==k, and it is easy to see the reason why ( you cant go to pos-k because it is < 0). Then, a part of the winning pattern will become: AAApos, id of pos == k+1. So both pos-1 and ipos-2 will reach A, so the ans should be B. And we know that pos-k changed from B to A. So the unique ans to pos is B now. This is the same as restarting the winning pattern, so, this winning pattern in the range [0, k] will be the same as [k+1, 2*k] and so on. I know that this solution is not rigorous mathematical, but I hope it will help you!

how do you do that?

I had been thinking on using segment tree for about hour when found O(n^3) algorithm with bitset. I still do not know/understand how to solve it using segment/fenwick tree. Looks like i blundering something about it...

I think he should be banned.what do you think?

Even just with ordered_set 57040076.

Is there a rigorous mathematical proof to problem D (when k% 3 == 0)

A moment of silence, please. _ / \ _

Why put such a high bound on E when solution is n^2 log n? When n=5000 that is about 3*10^8 operations.My segment tree solution got TLE which cost me a lot of time before i finally stopped thinking about an n^2 solution and optimized my segment tree by a little bit to save those 200-300ms that i needed.

Doing it by program is a lot better in this case, I think the pattern is not obvious at all until you look at maybe the first 30 of the first 10 values of k.

Let $$$s_i = T - \sum_{j \leq i} t_j$$$. If $$$\ell$$$ is the last crossword completed, at most $$$s_\ell$$$ of the crosswords up to $$$\ell$$$ can take an extra second, and at least $$$s_{\ell+1} + 1$$$ of the crosswords up to $$$\ell + 1$$$ must take an extra second.

The number of possibilities to check for any fixed $$$i$$$ is linear (the extra seconds up to $$$\ell$$$ and the extra seconds up to $$$\ell + 1$$$ differ by 0 or 1). Also, since $$$s_i$$$ is decreasing, the number of possibilities for all $$$i$$$ put together is still linear.

I changed just two characters in my first submission(douring contest) and I got AC for problem F after the contest (57059435). I was really unlucky during the contest. :(

Good job to laklouch for some high quality hacks:

How to generate solution for D without observation? Any simple technique and proof?

HubyBee Hacked himself purposely (Problem A). Isn't it illegal? Link:

Thank you!

how to solve E?

D problem is a good type of game theory

everyone is official