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

Я могу ошибаться, но видимо это подразделение(филиал) МФТИ

Как мне сказали — они все закончили МФТИ в том году, и поступили в Иннополис только чтобы еще раз в АСМ поучаствовать (ну и поучиться в "крутом" Иннополисе с хорошей стипендией обычным студентами, и, наверное, очень хорошей — участникам международных олимпиад).

P.S. Извините, если спалил чей-то хитрый план.

Да

Было 13

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

Не думаю что это канонично, но заходит такое:

Сначала сделаем чтобы в каждой паре первая сторона была больше (перевернем где нужно).

Затем переберем обе стороны, вариантов 8000*4000, теперь для заданных размеров надо узнать какие подходят, пробегаться за 8000 опять будет долго, зато можно узнать за константу, если сделать запрос в матрице сколько пар правее и ниже нащей. Чтобы размер матрицы не был 10^6 на 10^6 сожмем координаты, чтобы переводить из несжатой в сжатую за константу сохраним перевод в массиве.

Получим 8000^2 решение.

http://pastebin.com/XpRPaGTy (без оптимизации map-> массив для сжатых 4 секунды) up 1 секунда с оптимизацией http://pastebin.com/RxdwVtbu

Решение за n^2 log(n): Переберем ширину — 2n варианта. теперь посмотрим для каждого прямоугольника, как лучше его положить. Выберем такой вариант, который даст хотя бы нужную ширину и максимальную высоту. Посортим все возможные высоты. Тогда ответ можно получить за один просмотр массива высот.

Решение за n^2: Сохраняем каждую пару (w, h) так, что w > h (переворачиваем, если нужно). Сортируем по w. Запоминаем все уникальные h.

Затем для каждого h и i (i <= n) запомним на суффиксе от i до n, сколько есть элементов таких, что их высота > h.

Далее просто итерируемся по по возрастанию w, внутри итерируемся по уникальным значениям h, за константу отвечаем, сколько у нас элементов, больших h и имеющих ширину не менее w.

Код решения: [submission:13688964]

А еще можно было решить двумерным деревом отрезков) [submission:13698682]

Инкремент на прямоугольнике, запрос в единичной ячейке.

Answer for connected component is , where k is number of marked vertices in this CC.

Assume for simplicity that our graph is a tree. Suppose we are solving for the subtree rooted at vertex v. Firstly we solve recursively for all children. After this step in each child's subtree at most one unmatched marked vertex, so we can match these vertices by combining them in paths going through vertex v. If there is left unmatched vertex in some child's subtree and v is also marked, then we match them.

If our graph is not a tree, we can just take it's dfs tree or some spanning tree.

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

http://contest.sgu.ru/monitor/1

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

Если что, у тебя была включена галочка "по-русски".

Скорее всего дело в другом. После окончания контеста у Иннополиса висело сразу несколько не протестировавшихся сабмитов. В то же время, 16-я попытка(то есть первая, которая зашла) протестировалась еще до окончания контеста. Короче, у Иннополиса было стандартное "исправил-послал" в последние несколько минут, и сразу несколько их сабмитов прошли все тесты. На ЧФ засчитывалось по первой попытке, а на КФ засчитывается ресабмит :) .