**You may print PDF-statements: http://assets.codeforces.com/statements/589.pdf**

Recently 2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest has been finished. On behalf of jury and hosts I congratulate winners and advancers to the semifinals. Prize places are (horray!):

- 1 place: Nizhny Novgorod State University #1 (Vladislav vepifanov Epifanov, Nikolay KAN Kalinin, Mikhail mike_live Krivonosov)
- 2 place: Innopolis University #1 (Evgeniy savinov Savinov, Sergey sokian Kiyan, Alexander map Mashrabov)
- 3 place: Saratov State University #1 (Edvard homo_sapiens Davtyan, Vitaliy kuviman Kudasov, Danil dans Sagunov)

On Saturday (October, 17) в 08:00 (UTC) we will host unofficial online mirror. Interesting problems are waiting for you. Judges tried to prepare problems of wide difficulty range: for newcomers and for expirienced teams. This will be a team/personal contest on Codeforces, with teams consisting of up to three people or individual participants. The contest will not affect Codeforces ratings.

For sure, it will be unrated contest. We recommend you to take part in teams. I think, the contest will be moved to Gym later.

Good luck!

MikeMirzayanov, head of judges.

P.S. We are aware that this mirror will overlap with some other online tournaments, but unfortunately we are unable to change the current time slot, due to the online mirror of the Moscow Subregional of NEERC scheduled on Sunday. All school teams are recommended to pay attention to Online-mirror of the Ural regional team championship.

An hour after this contest ends, COCI contest starts. Tomorrow's gonna be intense! :D

I do not attend any of these. And i was not if there was a t-shirt prize. I will not code anymore. We have been a very good family so far, but i need to leave now. Good bye! ps : im so sorry mahmoudhassan :(

No T-shirts ?

For how many Hours Contest will Run ??

So 5 Hours

May be not.There're ten minutes to prepare.

You can see duration from this link Duration :)

Please provide editorial and codes if you plan on moving it to gym.

For what reason?

I don't know a lot about Gym contests, but I know this much that they don't allow you to look at test cases, as well as others' solutions. Thus, I was asking them to open others' solutions and test cases , and also provide editorials. That's all :)

Did I get so many downvotes because I forgot to mention "after the contest" , as Gym problems don't let you look at others' codes, or test cases?

Please tell me if the reason is something else, because I would like to know. I haven't practiced a lot of Gym problems you see. :)

Will there be youtube editorial after the contest like last year ?

how will be the difficulty level of the problems?? Can we (newbie's) can solve these..

See the last sentence in the blog: there is a contest for low-level teams today: http://acm.timus.ru/contest.aspx?id=304

How do you know it is going to be easier?

Just read the problems from the previous years.

How to solve Problem F ??

Just make binary search by time near each food and then apply a greedy strategy : eat the most needed food, that will be ended soon. (how many this food we need — number of second it will be available). http://pastebin.com/0crsX2yH

How can you prove it? I can't understand.. I used maxflow algorithm and accepted!

can u please explain how did u solve it using max-flow ? and how u model the flow graph ?

will test cases be public later? thanks

is it possible to solve G with square-root decomposition ?

Yes it is. We did that.

got AC after 36 attempts :3

How to solve C?

First trick: we need only first 60 concatenates.

What's the next trick? We have TLE #11, our solution works about 30s on max test. It's quite straightforward, with complexity something like O(queries * log(r) * maxShift).

How to solve it faster?

My complexity

~~the same~~is O(queries * log(r)). Next trick is recursion, if we want to know answer for k-th string on L,R we can use answer for k-1-th string for some new par L' and R'. k-th string can be split into four groups:length of [s] it is t[k] (shift length)

And now, clearly, we have 10 cases of calls in recursion, depending on location L and R.

Next trick — |s| is small (<=100). In my solution i precalculate answers for all suffixes for all strings.

For example, if L in 0th group and R in 2th we can use these values and just change R to R'. I think all 10 cases are easy except case L in 0 and R in 3. But if we built projection D of R

then we can call value for segment [D+1, L-1] and subtract it from all count of symbols. If D>=L we need add it, ofc.

can anyone share his algorithm about prob B? I only think of one with complexity O(n^2logn)

http://pastebin.com/RxdwVtbu

about pro A?

http://pastebin.com/kjWGJRfB

n^2 solution: Save all pairs

`(w, h)`

such that`w > h`

(swap them if needed). Sort in ascending order of`w`

. Save all unique`h`

values.For every unique

`h`

and`i`

`(i <= n)`

remember how many elements with height greater or equal than`h`

there is on suffix from`i`

to`n`

.Then just iterate over

`w`

(in ascending order), inside this iterate over all unique`h`

values, answer how many elements we have with height >`h`

and having width not less than`w`

in constant time.Solution: [submission:13688964]

How to solve problem K?

Problem KThe key observation here is that every time we need to choose a task, we shouldn't look through all of them.

Imagine we have a list of deques q, where q[t] is the deque containing all tasks with t[i] == t, ordered by l[i], then by i. Let's denote the minimal t such that q[t] is not empty, as minT.

We can consider only deques q[minT], ..., q[minT + sqrt(10^5)]. Proof: If t[i] + sqrt(10^5) < t[j], then the function l[i] — (T — t[i])^2 is definitely less than l[j] — (T — t[j])^2, no matter what their l and t values are. So the tasks with t[i] > minT + sqrt(10^5) cannot be minimal.

As all deques contain tasks ordered by l[i], then by i, just as in the statement, iterate over all t in the interval [minT, minT + sqrt(10^5)], and choose the best task from the first elements in deques.

Thanks. AC :)

How to solve D?

O(n^2) . For Each , check others to catch up,This can be done in O(1) or using binary Search in Time.(O(log(n))

what's the 10th test case in problem D ? -_-

Integer overflow probably. For me it failed on checking

`(f[i] - s[i]) * (f[j] - s[j]) > 0`

Could someone post their code for A?

code

http://pastebin.com/GaViDkZg

[submission:13683752]

http://ideone.com/MR9MgN (Perl)

How to solve problem J ? if i can't move forward should I stop the robot ?

my solution for problem J(cleaner robot) is failing on test 15. Can anyone guess what would be wrong?

mine too ! couldn't pass the test 15. 15 attempts, all failed ! :(

After WA15 I realized that it will be much easier to make more steps than it would ever need and increment answer on every new clean tile.

And test I tried was like

6 6

......

......

R.....

.....*

......

......

can you please tell me the answer for this test?

14

I realized that it will be much easier to make more steps than it would ever need and increment answer on every new clean tile? can you elaborate it?

In my solution I just make

n^{2}*m^{2}steps. It's enough to get AC.If one step is either moving or rotating, it's enough to make 4*n*m steps. Cleaner has only 4*n*m different states — each direction on each cell. We did it bfs-like, though — with vis[row][column][direction].

I agree

It's not like I was trying hard to get this number, chose the one that will be under the limits.

what is the 15th test case of problem j??

my code was failing on case 15 ... until i realized that i was checking for '.' on the next tile that the robot moves on , which is wrong ... because letters 'U' , 'D', 'L' ,'R' are allowed too ... got AC after fixing it :)

Can anyone share his code for problem J ?

Maybe 1 10 .........U

OR 10 10 .........* .......... .......... .......... .......... .......... .......... .......... .......... .........U

what are the correct output of these cases ?

Although my code is very big...i have written it in a very simple manner putting all the different conditions...so you can easily understand the code

http://ideone.com/EuC5xL

thanks. by the way, test cases are public now. so i found my bug. anyway thanks again for sharing your code. :)

can anyone guess what is test 15? question to those who passed the tests. I am curious in knowing where my solution is wrong

Did anyone solve Problem — G using segment tree?

Yep. Sort both the days and applicants (by

d_{i}) in reverse order, process them in parallel. More specifically: when considering candidatei, it suffices to only consider the daysjwitht_{j}>d_{i}(all other days are useless anyway). So we process the candidates by descendingd_{i}, and for each candidate we would like to find the earliest time they could be done. Clearly if we only consider daysjwitht_{j}>d_{i}, then the optimal solution will be some prefix of this sequence of days.You can use a segment tree where leaf

jstarts as (0, 0), and when you 'process' (more on this later) the day you set it to (t_{j}, 1). Here the first value represents the total available time (we haven't considered setup time yet, but since we are going to maintain that for all days in the segment tree we havet_{j}>d_{i}this day will still result in a net gain) and the second value represents the number of days over which this is spread. Combine two leaves with pairwise addition. The idea is now to insert each dayjas soon as we process a candidateiwitht_{j}>d_{i}, because after that, all candidates will have a lowerd_{i}value, and thus they can also use this day (recall that we process all candidates byd_{i}in descending order). You can achieve this quickly by also sorting the days in descending order and maintaining a pointer to the next day that should be inserted.After this, you can use the segment tree to compute whether a certain prefix of the days is sufficient. Query the interval [0,

d) for some d, this will result in a tuple (time,days), the total amount of time and the number of days in this interval, respectively (amongst all days witht_{j}>d_{i}). The candidate can then finish if and only iftime≥r_{i}+d_{i}×days. You can use binary search to find the smallest prefix, since, again, all days in the segment tree will result in a net gain (t_{j}-d_{i}to be precise), so the amount of available time for a prefix [0,d) is increasing ind.After preprocessing my solution was because I was being lazy, but you can drop the binary search and find the optimal prefix in a single traversal in . Details are left as an exercise to the reader :)

Code

TimonKnigge My idea was same as you but did it ascending order of . Couldn't figure out what's wrong :( Code

Are you sure you are processing the candidates/days in the right order? You seem to process them in ascending order, not descending.

You wouldn't believe how stupid I'm. The problem was I take n as m and m as n. :( here is the AC Code

You can do it by ascending order too. For each , remove all and then find the result using segment tree.

I solved using BIT in nLogn complexity. Code

forget it. Everything is alright. :)

i could take it just for about half because of school classes! but i enjoy it !

thanks XD!

No way to see other's code?

How to solve problem H?

Ideas for H?

Assume our graph has one connected component, then we can create roads.

Hint: try to solve for a tree

More detailed explanation

full of implementation

The algorithm for the robot to move and clean the floor in the room is as follows:

1.clean the current cell which a cleaner robot is in;2. if the side-adjacent cell in the direction where the robot is looking exists and is empty, move to it and go to step 1;3.otherwise turn 90 degrees clockwise (to the right relative to its current direction) and move to step 2.How the ans is 10? Why not like this?

PICTURE

You have an infinite robot movements on the first column: upwards-downwards.

Thank you Guy, I have done it. :)

look here "The algorithm for the robot to move and clean the floor in the room is as follows:

Thanks

what is test 13 of pro A?

Could someone explain the idea to solve Problem M?

Can problem K (King's Rout) be solved with dfs? I keep getting wrong answer for test case 13. Can anybody please tell me what this test case is? problem list submission

How to solve F using flows? Problem Link