Codeforces Round #442 (Div. 2). Editorial.

7 years ago, # |

Can you provide a java solution for problem F that passes the time limit? I think this submission is the same as described in the editorial and it gets TLE.

→ Reply

Irina_Rog

7 years ago, # ^ |

← Rev. 2 →

-35

Man, you should have known that java is bit slower than c++. I think usage of inappropriate language is only your problem.

→ Reply

ZiYazIyAZiYazIyAZiYazIyA

7 years ago, # ^ |

← Rev. 2 →

Arrays.sort() can work up to O(n²)

→ Reply

7 years ago, # ^ |

← Rev. 2 →

Never. If the passed array is a primitive array, then the used sorting algorithm is Quick sort which has the worst-case complexity as you just mentioned. If the passed array is an object array, then Merge sort is used which is the case in my submission. You can jump into which Arrays.sort() function called by the code and check yourself.

→ Reply

T.V_N

7 years ago, # ^ |

→ Reply

KAN

7 years ago, # ^ |

+14

When I run this solution on all tests, it gets a lot of REs with the following error:

java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.ComparableTimSort.mergeHi(ComparableTimSort.java:866)
	at java.util.ComparableTimSort.mergeAt(ComparableTimSort.java:483)
	at java.util.ComparableTimSort.mergeCollapse(ComparableTimSort.java:406)
	at java.util.ComparableTimSort.sort(ComparableTimSort.java:213)
	at java.util.Arrays.sort(Arrays.java:1246)
	at F.main(F.java:48)

I believe that is the problem that causes TLs as well. C++ solutions work 200-500ms, I don't think Java solution will work more than 5 times slower.

→ Reply

7 years ago, # ^ |

I got the problem. There was a bug in the implementation of the comparable function. Thanks!

→ Reply

KAN

7 years ago, # ^ |

+35

Well, your sorting is just incorrect for Mo's algorithm. It should sort by block, but it sorts by l.

→ Reply

7 years ago, # ^ |

Yes, exactly

→ Reply

dush1729

7 years ago, # |

+16

Problem D

Test case 31?

→ Reply

Temirulan

7 years ago, # ^ |

5 5 3
..#..
.....
.....
.....
.....
3 3 1 2

invalid function also checks for visited points, but there might be some unvisited reachable points which are farther than first visited point. Do not think that reordering of direction array will help :)

→ Reply

nqs_1

5 years ago, # ^ |

thx

→ Reply

7 years ago, # ^ |

← Rev. 2 →

7 14 14
XXXXXXXX..XXXX
XXXXXXX...XXXX
XXXXXX..X.XXXX
XXXXX.....XXXX
XXXX..X...XXXX
XXXXXXXXX.XXXX
XXXXXXXXX.XXXX
1 9 7 10

the visit order may be the cause. So you need to memorize the direction too, seen[f][c][d] and that should fix it.

→ Reply

7 years ago, # ^ |

Can you please explain why do we need to save direction, too?

→ Reply

7 years ago, # ^ |

Well, one of the reasons is because you can calculate the cost in order and be sure is good calculated. What I mean is, if you keep moving in the same direction, you go with cost 0, but if you change the direction, your cost increases in one. (Now you can use bfs 0-1). Now, note that if you don't do this (only save row and column), it can be possible that you reach a cell with a cost greater than other, and because you reached that cell first (because of bfs) with greater cost, you assume that is the best way to reach that cell, but that might not be the best option.

So basically you need to separate the two kinds of costs, 0 for same direction, 1 for other direction.

I'm thinking maybe if you use a heap instead of queue to process in order, the dimension of the directions may be not needed (Is a thought. You can test it. Because basically the bfs 0-1 is a dijsktra but with special costs.)

Is it clear?

→ Reply

7 years ago, # ^ |

Thank you a lot for such a great response & I'm really sorry for my so long one.

Everything is pretty clear, but I still didn't get the idea why I should save direction.

Because let's assume that we stay in state (x, y), and we'll just brute force some count in range[1; k] and anyway we'll do +1 to our adjacents to which we can go in one step.

→ Reply

7 years ago, # ^ |

Well, Actually it depends on how you implement your solution, can you show me your code?

I remember the first solution I submitted I tried to only save x and y, but I had a mistake about when to stop (check this comment and the response ), because if we do what you say, we will got TLE, right?

→ Reply

7 years ago, # ^ |

here's my submission: 36150483

→ Reply

7 years ago, # ^ |

← Rev. 3 →

I did some modifications to your code (here). The thing is that the stop condition was wrong.

Now, you have good the idea, but the order of checking the cells may be wrong in some cases. Look at my code (here) Basically what I do is use another dimension to do the for-loop that you have, is like doing the for-loop but implicit.

So the problem is some like this:

You can arrive position {x,y} in 2 ways and with the same cost. But depending how many movements of k you had used they are different and you can't break the for-loop.

→ Reply

7 years ago, # ^ |

Wow, thank you so much, I struggled with this problem for a long time!

→ Reply

dush1729

7 years ago, # ^ |

Thanks Temirulan and -osdajigu-. Got AC

→ Reply

RNR

7 years ago, # ^ |

Any implementation as mentioned in Editorial..... Thanks.

→ Reply

T1duS

7 years ago, # |

Does anyone have any idea why this- http://codeforces.net/contest/877/submission/31647784 gave WA on test 49?

→ Reply

dheeraj_1997

7 years ago, # ^ |

← Rev. 4 →

Why didn't it give TLE?? My implementation is almost same but i get TLE on test 48.

http://codeforces.net/contest/877/submission/31654408 If you can point out the mistake that would be really helpful

→ Reply

ujzwt4it

7 years ago, # ^ |

← Rev. 2 →

While you are taking k steps from the current cell(the one currently at the front of the queue), if you come across a cell that is already visited, you break out of the loop. That is incorrect because you are expecting the cells beyond that visited cell to get their distance equal to the distance of visited cell +1. However the distance of visited cell could have been one more that the distance of current cell. Answer for all the unvisited cells beyond the visited cell could end up being one more than it was supposed to. I made the same error. You can check out the codes

Incorrect Correct

→ Reply

all_out

7 years ago, # |

← Rev. 4 →

LOL, For 5 seconds I was waiting to load the tutorial of problem C. :P

→ Reply

Single_Ready_To_Mingle

7 years ago, # |

Proof of optimality for Problem C ?

→ Reply

ludo

7 years ago, # ^ |

+24

The problem is equivalent to finding a string S such that for all 1 < i ≤ n, i - 1 precedes i somewhere in the string and i precedes i - 1 somewhere in the string.

Now observe that for some i, it occurs either 1 or 2 times in the optimal string. If it is more than 2 times, we can erase the middle ones and obtain a better string.

If for some i, the number of times is 1, then i + 1 must occur (at least) 2 times: to the left of this location and to the right. If i occurs 2 times, then i + 1 must occur (at least) once (in between the two occurences).

From this, you can build the string 2,4,6,... 1,3,5,..., 2,4,6, ... which is therefore optimal.

At every step we get some partial string with all the numbers from 1 to i. Inductively you can show that this is optimal at every transition to i + 1.

→ Reply

ash0904

7 years ago, # ^ |

Can you please explain, how did you reduced the given problem to equivalent string problem?

→ Reply

ludo

7 years ago, # ^ |

Suppose there are 2 tanks at every location i. Suppose on first hit, the first tank moves to the left, the other moves to the right. This is the worst case of tank positioning, so if this case is handled by the string, it is handled by every configuration of tanks.

To erase the first tank from location i, we have to bomb location i. After this, the first tank moves to location i - 1 so this one has to be bombed after i is bombed. Likewise, to bomb the second tank, we have to bomb location i at some point, and after that we still have to bomb i + 1. You can substitute i with i - 1 to obtain that i - 1 has to precede i at some point in the string.

The optimal bombing will fix this situation I described here, so it will obey the cosntraints on the string I described. On the other hand, if the constraints are met for a string S, then a bombing plan will be a 'good' bombing plan.

→ Reply

Z8N

7 years ago, # ^ |

It is easy to notice that we have to hit atleast 3 times in each pair of neigbor cells.

That is why answer is atleast 3*n/2 (+1 if n is odd).

→ Reply

Hossam

7 years ago, # |

← Rev. 3 →

Can someone provide the recurrence formula for B with DP?

Never mind, figured it out!

→ Reply

djvdm123

7 years ago, # ^ |

Could you provide the formula? Brute force soln in tutorial is n^2 and gets Timed out.

→ Reply

prakhar17252

7 years ago, # ^ |

The same code when written in C++ passes with a time of 46 ms, but gives TLE in python. From what I have read online, Python is only 5 times slower than C++. Why does this happen? 31662096 31662142

→ Reply

djvdm123

7 years ago, # ^ |

On other platforms like Codechef, for Python time is 5x of C/C++ Anyway, I see a lot of solution with single loop, but cannot understand the logic :(

→ Reply

prakhar17252

7 years ago, # ^ |

← Rev. 2 →

Still, even without the multiplier, the python code should be roughly 5x slower. And it should easily pass O(n^2) for n=5000

→ Reply

killer_god

7 years ago, # ^ |

Actually no. python is roughly 100 times slower.

→ Reply

Hossam

7 years ago, # ^ |

DP Solution O(N): I hope this is quite clear! 31663633 Simple Bruteforce O(N^2): 31642282

→ Reply

hdn

7 years ago, # ^ |

I know u probably dont care since this contest is 2 months old but thanks for posting your dp solution. I had a tough time trying to come up with the dp solution, i got close tho :( Btw i think dp[2][i] doesnt gives u the max count of (b) unless u make dp[2][i + 1] = max(dp[1][i] + s[i]=='b', dp[2][i]) + (s[i] == 'a')

→ Reply

Hossam

7 years ago, # ^ |

← Rev. 4 →

Actually I had to go through it again to remember what my recurrence were lol xD. My idea was to find the best that ends with prefix (a, ab, aba) in that specific order. That modification you made was already handled in the second line where it was supposed to end with b, it's unnecessary! Thanks for bringing that interesting problem again to my mind :)

→ Reply

monsij

7 years ago, # |

For problem C what if i throw bombs on all cells starting from last to first and then again in the 2nd cell.It gives n+1 as my answer.

→ Reply

dorijanlendvaj

7 years ago, # ^ |

What if the tank is in the cell 2 and moves to cell 3?

→ Reply

monsij

7 years ago, # ^ |

I think it's given in the question that a tank in cell n can move to only cell n-1 except for 1 wherein it moves to 2

→ Reply

7 years ago, # ^ |

A tank in cell n can move to n - 1

A tank in cell 1 can move to 2

A tank in cell 2 ≤ i ≤ n - 1 can move to either i - 1 or i + 1

→ Reply

CaptainDaVinci

7 years ago, # ^ |

← Rev. 2 →

I have the same doubt, for 4 cells shouldn't the optimal placement of bombs be, 2 4 3 1 2 ?

→ Reply

7 years ago, # ^ |

When you hit cell 3, the tank inside it might move to cell 4 and not get hit after that.

→ Reply

Adish_Agarwal

7 years ago, # |

can someone please provide the code for D

→ Reply

egor.okhterov

7 years ago, # |

← Rev. 5 →

I am totally missing the point of how the sets are used.

Now it's easy to find all not visited cell which is reachable from vertex

I don't get it. Isn't the following also easy? (PSEUDOCODE)

int r_cur = queue.top().row;
int c_cur = queue.top().column;
queue.pop();

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
for (int dir = 0; dir < 4; dir++)
{
    for (int len = 1; ; len++)
    {
        int r = r_cur + len * dr[dir];
        int c = c_cur + len * dc[dir];

        if (!empty[r][c] || !valid(r, c))
            break;

        if (dist[r][c] > cur_dist + len)
        {
            dist[r][c] = cur_dist + len;
            queue.push({r, c});
        }
    }
}

It is easy to find all unvisited cells from the current cell (r_i, c_i) in O(n). Right?
It looks like I fundamentally don't understand what we are looking for and why do we need sets for that.
Ultimately we need to fill the matrix dist[N][M] and we can reach every single one of dist[r][c] from adjacent cell in O(1).

I know that dist[r1][c1] = 0 and all of the vertical cells dist[r1 ± i][c1] and horizontal cells dist[r1][c1 ± i] have distance 1 (unless they aren't too far from (r1, c1)). This is the point zero in my current understanding. Could you please, elaborate what do we do starting from that understanding?

→ Reply

lemelisk

7 years ago, # ^ |

← Rev. 2 →

First, simple, but slow BFS solution: just connect each cell to the cells with distance no more, than k, in each direction and simply run BFS on this graph. This will run in O(nmk), because for every n·m node we will check O(k) adjacent nodes.

So for each row and column, let's put all nodes, that are not already reached by our bfs process, into set. Then, when we take node from queue, we look to the nearest not reached neighbour in each direction (can be done with log(set size) via set::lower_bound) and if the distance is no more, than k, extract it from its both sets, put into queue and continue looking for the new nearest neighbour. So in each step we look at 4 + number of extracted in this step nodes. And total sum of extracted nodes is no more, than total nodes count (after we extract node, we will never look at him again).

→ Reply

Arpa

7 years ago, # |

+43

Hi! As a tester, I enjoyed solving the problems. Thanks to the author (Livace), the contest was really good in my thought.

It could be better to swap D and E. Anyway, E and F were technical problems (i.e. E needed fenwick Or segment tree, F needed MO), D was creative, and maybe hard to code, A, B and C were straight-forward.

To summarize, I think it was the best contest I've tested if I remember correctly.

→ Reply

luvk1412

7 years ago, # ^ |

Can you please explain how to flip 1 and 0 using fenwick and then get the count of 1? i solved it using segment tree but would like to know solution using fenwick trees(i know how to do range updates in fenwick like if i wish to add a particular value to a range l to r but cant get any idea of how to flip)

→ Reply

Arpa

7 years ago, # ^ |

Sorry, I wrote fenwick accidentally, I haven't a solution with fenwick for this problem. Sorry again.

→ Reply

luvk1412

7 years ago, # ^ |

Oh, no problem, i thought it could be done using fenwick as in this link also in description it was mentioned it could be done using fenwick.

→ Reply

Zovube

7 years ago, # ^ |

Hi! In D BFS with some breaks passed in 77 ms. Proof. Was this intended? Because I can understand the solution from editorial and why it works, but face some problems trying to estimate complexity of such bfs.

→ Reply

lemelisk

7 years ago, # ^ |

+12

This condition if(ans[ni][nj] < ans[v.fi][v.se] + 1) break; gives you O(nm) complexity. Because consider cell's ans is x, than throught entire algorithm's work you will visit this cell no more than 4 times: one for each of 4 directions from the nearest cell in this direction with ans = x - 1.

→ Reply

ppavic

7 years ago, # |

← Rev. 2 →

My idea for D

UPDATE: My mistake. Seems like I didn't read the problem statement carefully enough.

→ Reply

7 years ago, # ^ |

How do you make sure you won't move more than k steps in one direction?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

I think that you have to save 4 values for each element inserted in the queue, row, column, direction, and movements. So every time you pop an element from the queue, you can make a movement in the same direction iff movements < k, or start a new movement in other direction. And you only memorize the row, col, and direction. If you change direction, it cost 1, but go in the same direction, 0

→ Reply

7 years ago, # ^ |

← Rev. 2 →

Hi, what is necessary you remember the direction, why not simply do a for(loop), for each position up to K in 4 directions and if you get an already visited cell, stop the loop?

UPDATE: I found a case when it is necessary

→ Reply

7 years ago, # ^ |

Actually this is the solution I used in the contest, but you shouldn't stop the loop when you reach a visited cell, you should stop when you reach a visited cell with distance less than or equal to your current distance.

→ Reply

7 years ago, # |

for problem number C. let's assume n = 6. now throw bombs in all even positions now all tanks are in 1 3 and 5 positions. now throw bombs in 1, 3, 5 positions. now the tanks are in 2 and 4 positions, isn't it? cause it's said that tanks in the cell n can be moved only to n-1 position and tanks in cell 1 can be moved only to 2 cell.now throw bombs in 2 and 4 positions. please tell me why I throw a bomb in position 6 again? why I waste a bomb? why is the answer not 8?

→ Reply

7 years ago, # ^ |

5 ≠ n

tank can move from 5 to 6

→ Reply

7 years ago, # ^ |

why? it's said in the problem statement that tanks on position n can be moved only to position n — 1.

→ Reply

7 years ago, # ^ |

(a tank in the cell n can only move to the cell n - 1, a tank in the cell 1 can only move to the cell 2)

→ Reply

7 years ago, # ^ |

in the cell n, not in the cell i

→ Reply

7 years ago, # ^ |

get it. thanks:).

→ Reply

djvdm123

7 years ago, # |

Could someone please explain how B can be solved in Linear time? I get Time Limit exceeded for the editorial solution which is O(n^2)

→ Reply

f1u77y

7 years ago, # ^ |

n_max = 5000, so some languages could be not fast enough for solving this problem.

→ Reply

bazsi700

7 years ago, # |

How could people implement E in 10-15 minutes during the contest? I used segment tree with lazy propagation, and it took like 1 hour to code, and another 1 to debug. The latter could be avoided, but even if I coded faster, 10-15 minutes seems impossible.

I checked fast solvers submissions, but they used one character variable names, and unusual spacing, so I couldn't really understand their solution.

Could someone explain a faster to implement solution? Or did they have pre-implemented lazy prop?

→ Reply

7 years ago, # ^ |

It's a pretty famous problem. click

→ Reply

GreenGrape

7 years ago, # ^ |

Well, this lazy propagation is kinda straightforward :)

Check mine: 31644977

Coded it in 18 mins.

→ Reply

f1u77y

7 years ago, # ^ |

← Rev. 2 →

If you solve some (10+ at least) tasks which require implementing segment tree with slice operations (which require lazy propogation), you'll be able to implement it much faster and much more bugless.

→ Reply

prathmesh_01

7 years ago, # ^ |

Can you list some of them , maybe on SPOJ or somewhere

→ Reply

ioli

7 years ago, # |

BFS is enough for D number. http://codeforces.net/contest/877/submission/31656756

→ Reply

predelnik

7 years ago, # ^ |

For me straightforward bfs passed too, in 1560 ms. Looks like constraints should have been a tad higher if bfs was not an intended solution.

→ Reply

KhZi

7 years ago, # ^ |

Can you give some explanation why it works?

→ Reply

Shudi

7 years ago, # ^ |

BFS nice, but can someone prove that it's enough?

→ Reply

naevis

7 years ago, # |

why i keep getting memory limit exceeded on problem D? is it because too many queue?

→ Reply

suds13

7 years ago, # |

31659292 877B - Nikita and string Hey can somebody help me find out what is wrong with my solution to B — Nikita and String. I got wrong answer in test case 37. Thanks.

→ Reply

7 years ago, # ^ |

You missed the case when the string contains only letter "a"s. You are always trying to take the number of 'b's on a non-empty substring.

→ Reply

RNR

7 years ago, # |

Any implementation of problem D as mentioned in Editorial. Thanks...!

→ Reply

akumar1503

7 years ago, # |

in F how left border can be moved easily??

let current left is l, updating l to l + 1 removes a[l] from all prefixes so all cnt values should be updated which should be O(r — l).

how is this done efficiently?? or i'm missing smthng.

→ Reply

Jakube

7 years ago, # ^ |

No,you don't need to update all content values. Remember, you store the prefixes of the complete array. If your l changes, the prefixes are still all correct. However now you look for indices i>l with presum[i] — presum[l] = k. So you need to add cnt[k + presum[l]] instead of cnt[presum[r] — k] to your result.

→ Reply

akumar1503

7 years ago, # ^ |

thanks got it!!

→ Reply

hungry_fool

7 years ago, # |

Why is my code giving RE for test 5 in [problem:D].

→ Reply

I_love_myself

7 years ago, # ^ |

You can compare with my code http://codeforces.net/contest/877/submission/31849869

→ Reply

M.A.H.M.O.O.D

7 years ago, # |

← Rev. 2 →

I think that E can be solved using sqrt decomposition but I can't do it.

Can someone help me please each time I submit this 31659189 code I get RE on a different test. I don't know what's wrong and the code is working on my mechanic. When I get RE on some test I use the test in costume test and it works. It's really weird.

I found what's wrong now I'm getting WA on 14 if someone could help I would really appreciate it. here's my new submission 31687428.

→ Reply

LoveIsSoFar

7 years ago, # |

I used unorder_map instead of map for F,but I still got TLE.I want to know unorder_map is very slow on codeforces?

→ Reply

daihan

7 years ago, # ^ |

← Rev. 2 →

Sometimes using reserve and max_load_factor can reduce the time of unordered map .

mapname.reserve(1<<16);

mapname.max_load_factor(0.25);

Arpa's blog has a nice tutorial about it .

→ Reply

Jakube

7 years ago, # ^ |

unordered_map has a big overhead. Quite often it will even be slower than map, even though the complexity is better.

→ Reply

Erdenebayar

7 years ago, # |

why did my solution get TLE http://codeforces.net/contest/877/submission/31697709 for F? \n used unordered_map

→ Reply

dash95

7 years ago, # |

In problem E,Can someone guide me on how to form segment tree from given tree ?

→ Reply

7 years ago, # ^ |

Use the dfs order where a subtree will be in a continuous range.

→ Reply

mahim007

7 years ago, # ^ |

Can you elaborate your idea a bit more pls?

→ Reply

7 years ago, # ^ |

Dfs order is a sequence obtained by recording every node when it's searched using dfs. (I am not sure whether people outside China call it dfs order.) Then we find out that all nodes of a subtree are in a continuous range in that sequence. Now it's changed into a sequence problem which can be done with a segment tree.

→ Reply

mahim007

7 years ago, # ^ |

Can you provide me some useful link (english)?

→ Reply

7 years ago, # ^ |

maybe this one can help you.

→ Reply

mahim007

7 years ago, # ^ |

thank you

→ Reply