Starts in less than 3 hours

Top 200 from round 2 are allowed to participate and top 25 (aged 18+) will advance to onsite finals

Let's discuss problems here.

# | User | Rating |
---|---|---|

1 | Radewoosh | 3707 |

2 | Benq | 3691 |

3 | tourist | 3669 |

4 | ecnerwala | 3565 |

5 | Um_nik | 3533 |

6 | ksun48 | 3489 |

7 | maroonrk | 3457 |

7 | jiangly | 3457 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 187 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 178 |

6 | maroonrk | 176 |

6 | Radewoosh | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Starts in less than 3 hours

Top 200 from round 2 are allowed to participate and top 25 (aged 18+) will advance to onsite finals

Let's discuss problems here.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/13/2021 23:43:57 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

https://www.facebook.com/hackercup/round

How to solve the third problem?

Shortest path between any two cities is either shortest path around the circle or shortest path from

Ato the center plus shortest path fromBto the center. Shortest paths to/from the center can be calculated with Dijkstra's algorithm.Then — bunch of binary searches. For each starting city

Aremaining cities are separated in three groups based on what is the best way to reach them: go right, go left, go to the center. I find three borders for each starting city: when it becomes better to go through the center than go left, similar for right, and when it becomes better to go right than to go left. Turns out that all these functions are monotonous and we can use binary search. After that — a bunch of prefix sums.First of all, run dijkstra from center and relax r_i. Now we may notice, that we either go throught center or without going to center. From vertex i, we always go clockwise to some range of vertices [i + 1, i + r], counterclockwise for some range [i — l, i + r] and otherwise throught center. Now use 2 bin.searches in each vertex

Edit: I was too slow :|

First, set

R[i] = min cost from i to center (also take into consideration of going around the circle).For each i, find

left[i] = farthest point on the left where you should go around the circle fromleft[i] to i.Find

right[i] which has similar meaning but to the right.Array

left[i] andright[i] can be calculated inO(N) using 2 pointers.Then for each i, there are 3 types of vertices:

left[i] to iright[i]Each type can be calculated in

O(1).Damn! I copy-pasted the sample from the third problem without the last line, and obviously the answer didn't match. I wasted about 15 minutes trying to find the bug in the code — almost missed the final because of that.

So there is no runtime error or anything in your code when you try and read an integer that is not there?

Of course not when you're using C++.

Well this is not trivially obvious to me, particularly as Al.Cash uses his own custom input parsing library, I don't think there is anything that stops him from throwing in some assert statements to check for this, although in this cases I suppose he does not.

I see why you asked the question now :). I think he kept same behavior as scanf: returns number of arguments successfully read, and not throw error.

Currently not, as I mimic scanf behavior. This incident suggests changing it.

How to solve the second problem?

Let's call a pair "splitting" if the friends are in different queues. Let's find the first splitting pair (in lexicographical order). If something "crosses" it, we need to delete these two pairs, solve the problem recursively (for everything before and after it) and returned the doubled product (we can choose the order of deletion of these 2 pairs). Otherwise, we have to delete this pair alone and solve two smaller subproblems again. The base case is when there're no "splitting" pairs (the answer is some binomial coefficient).

Some sketch:

We can see that not too many different configuratons of pair is allowed. So call group in one line "good" if it's of form "aa" or "abab" — it may be processed without going to other line.

Now, while we not finished, calculate and skip good groups. Now in the start you see one of not-so-many configuration of two-line divided groups (or answer is zero). So we can process good groups in any order (it is binomial coefficient) and multiply answer by that number and maybe by 2 if we can process "bad group" in two ways.

Let's try to model the process described in the problem statement.

Suppose, we've already processed first p1 items from the first queue and first p2 items from the second queue. We may either proceed with the operation that depends only on one of the queues or with the operation that depends on both of queues.

Operations that depend only on one queue look as following (operations of the first type):

`aa`

`abab`

Operations that depend on both of the queues(operations of the second type):

1 way to perform:

`a`

`a`

2 ways to perform:

`ab`

`ba`

`aba`

`b`

Consider, that we made c1 operations of the first type with the first queue and c2 operations of the first type with the second queue before we have to make the operation of the second type. We can arrange them in C(c1 + c2, c1) ways (C is a binomial coefficient), so we should multiply the result by this value. Then we have to perform the operation of the second type (and possibly multiply the result by 2).

If in any step we are unable to perform any of the operations — the answer is 0

Ah... First task is almost same with this task I wrote about 3 years ago..

Somehow I failed on this task (by mistype 'n' into '1000') otherwise I could advance. :(

http://cepc08.ii.uni.wroc.pl/problems.html G

Providing the inverse suffix array as an input instead of a suffix array in the first problem was the evilest possible thing :(

Why? You note that at a glance when you look at the first sample. Anyway, there was no reason to do so, I don't justify the authors.

Well, I always have both these arrays in suffix array, so it's weird to call "usual suffix array" only one of the permutations.

Still, suffix array is well-defined, so it makes sense.

what's the difference considering you need both of them?

It seems I had small implementation bug in last task, good thing tests had not caught it

Will you release screencast of your win, or are you not doing those anymore? It has been nearly a year now :(

I think about some new formats for this. I do not do screencasts for now unfortunately

(pity post warning)

I solved A, D, and submitted for problem B. However my problem B fails due to overflow error, passes with one extra line of "ans %= MOD;"

Sad orange coder ksun48 would have qualified

One of the reasons I wrote a wrapper class that handles modulus for me. It's used for example in this submission 24049890