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 :(

So 5 Hours

You can see duration from this link Duration :)

For what reason?

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. :)

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

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

Yes it is. We did that.

First trick: we need only first 60 concatenates.

http://pastebin.com/RxdwVtbu

http://pastebin.com/kjWGJRfB

n^2 solution: Save all pairs (w, h) such thatw > 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]

Problem K

The 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.

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))

Integer overflow probably. For me it failed on checking (f[i] - s[i]) * (f[j] - s[j]) > 0

code

http://pastebin.com/GaViDkZg

[submission:13683752]

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

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

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

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

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

Yep. Sort both the days and applicants (by d_i) in reverse order, process them in parallel. More specifically: when considering candidate i, it suffices to only consider the days j with t_j > d_i (all other days are useless anyway). So we process the candidates by descending d_i, and for each candidate we would like to find the earliest time they could be done. Clearly if we only consider days j with t_j > d_i, then the optimal solution will be some prefix of this sequence of days.

You can use a segment tree where leaf j starts 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 have t_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 day j as soon as we process a candidate i with t_j > d_i, because after that, all candidates will have a lower d_i value, and thus they can also use this day (recall that we process all candidates by d_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 with t_j > d_i). The candidate can then finish if and only if time ≥ 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 in d.

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

I solved using BIT in nLogn complexity. Code

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

Hint: try to solve for a tree

More detailed explanation

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

look here "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. "