The comment is hidden because of too negative feedback, click here to view it

This blog has 10 lines and 6 pictures. But all the comments are about the bottom right picture. Interesting :D

sorry man. There's only one type of bra for me, it's Algebra

i know, the beach is beautiful, isn't it ? *_*

Anything in particular? :p

Ugly Truth!!

it got filtered in like 43 hours XD

Great prediction!

.

Google lied to me, Sherlock.

Thanks RodionGork for making image larger now everything is clear :D

Thanks for warning it! I totally forgot about the timus contest.

Их вроде и не было никогда, возможно ты с опенкапом перепутал.

Мне кажется пару-тройку недель в списке команд на сайте они были, но потом исчезли. В Москве их пока нет. Опять пропускает? В Петрозаводске были.

The UVA contest will not take place,as far as I know (but not 100% sure). Still we have two contests at the same time on CF and Timus. Both contests are GREAT and both Russian,so,lets hope the personnel in charge will do something about the time clash :)

Or just gives you plain distraction. If you know what I mean ;)

Then don't say anything , Just make sure that you don't flood the blogs with comments that don't mean anything.

I think all of them are good :x :D

Saratov: SU1, SU2

2011/2012: top2

2012/2013: top2

2013/2014: top2

2014/2015: top2

2015/2016: ?????

xD

Full version:

2009/2010 top 4
2010/2011 team with dalex
2011/2012 team with dalex
2012/2013 top 4
2013/2014 top 4
2014/2015 top 4
2015/2016 top 1 (as ez collections became java standard)

Why do you say it has nothing to do with programming? It's a well known programming task — eight queens. You need to place eight white queens on the chess board so that none of them can beat any other. The solution displayed on top is not a valid one though.

Life is pain...

It will be possible soon

It will be possible soon

Мы хотели в Красноярском участвовать (или Краснодарском... путаю эти города), но будем в Московском сегодня, а в Киргизском вне конкурса на следующей неделе уже.

NO

Why the negative rating? The above message was a legitimate bug report I typed during the contest. The ranklist was indeed broken for quite some time (30 minutes or so). My dashboard showed that I had 7 problems solved but one of them (and not the last one submitted) was missing from the scoreboard. It did, as I mentioned before, disappear -- immediately after I solved problem G it was shown in the scoreboard, but it stopped appearing after a while. I have no idea how such a thing is possible, but it is certainly a bug.

We've made about 15 WAs in that case too

my error was a wrong algorithm...

make a count for each color ... and keep the "-1" blankets as a bonus

Now repeat the following process while u have a color where count[color]%(k/n)!=0 :

• Pick the color with the minimum count and count[color]%(k/n)!=0 ... call it color1

• Let's set v = color1%(k/n)

• Pick the color with the maximum count (other than the color1) .. call it color2

• If u can't find possible colors in step2 ... pick the bonus blankets.

• Now color v blankets from color1 with color2 ... and (k/n-v) blankets from color2 with color1

• if (k/n-v)>count[color2] ... use bonus blankets, and remove from them k/n — (v+count[color2])

• if conut[bonus] < (k/n) — (v+count[color2]) ... then the answer is No

After u finish this process, for any color i, it will achieve count[i] % (k/n) = 0

Which can be easily matched with itself

cheaters are everywhere!

13

in final standings top14 without Saratov 5

С — sqrt-декомпозиция на часто и редко выставляемые свойства.

К — я там строил граф, в нем вершинами были пары вершин дерева (i, j), т.е. по сути путь в дереве. Из каждой такой вершины идут направленные ребра в вершины (j, k), где k — вершины дерева, которые в permutation[j] идут раньше i. В этом графе искал циклы, эти циклы соответствуют единичным путям в исходном дереве, т.е. по сути они соответствуют ребрам. Циклы искал, пока не найду достаточно ребер, чтобы собрать дерево.

С — Неявные ДО для каждого параметра с множественным апдейтом по перенумерованному в порядке обхода ДФСа графа. То-есть обычная покраска поддеревьев, но на неявных ДО, из-за чего затраты времени и памяти

K — Заслал следующее решение: Для каждой вершины храню указатель на самую первую вершину в её списке, с которой её можно связать (то-есть они находятся в разных компонентах ДСУ). На каждой итерации внешнего цикла перебираю вершины, и если нахожу такую вершину Х, что для Х я указываю на У, а для У указываю на Х, то добавляю в граф ребро (Х;У) и обновляю все указатели. Это работает потому, что путь между парой вершин (Х;У) не может лежать через остальные вершины, так как на тот момент они друг для друга являются ближайшими из несвязанных.

А может кто-нибудь, пожалуйста, объяснить решение задачи С без ДО, например вот это: 8408457 ?

Насчет перемешки — ну так они сами себе кайф портят. Я вот специально, собираясь решать, не смотрел, какие задачи хорошо сдавались. А если перемешать, то потом начнется что-то типа: "а как решать I, которая в оригинале была C?", только лишняя путаница.

For now, you need to enter it in virtual participation to be able to make submissions.

Yes...

It was moved to the Gym.

G: Find the leftmost interval that needs changing. Where should you change it? Clearly, the best option is to start from its right end -- this will also lower the most other intervals to the right of the current one. My solution runs in O(n) and uses a deque to store the non-minimal elements in the current length-K interval. Each time you move one step to the right, possibly pop_left once, push_right once, and then pop_right while needed.

K: Obviously, you can connect each vertex to the second one in its list (i.e., the first one other than itself). This gives you at least n/2 edges, but not necessarily all n-1. How to generalize this? Suppose that you already have some components. If some component A and component B were connected via an edge a-b, what would you see? For each vertex of A, the first vertex of B in their list would be b, and vice versa. Notably, a and b are the first ones of A and B for each other. When can you be sure that you found a new edge? If you find two vertices a in A, b in B such that: b is the very first vertex in a's list that is not in A, and a is the very first vertex in b's list that is not in B. Does such a pair of vertices always have to exist?

Same here. Me too. I got "Network Error" every want to submit

Your code does not make much sense to me. Why would you, for example, do "dis[u][v]=dis[v][u]=min(dis[u][v],j-1);"? If v is the j-th vertes in u's list, it can still be much closer than in distance j-1 -- for instance, even in distance 1. So at this point you only get some random upper bounds on the distance.

Afterwards, you only process pairs that are in distance 1, but those had to be in distance 1 even before the Floyd-Warshall, so the Floyd-Warshall actually does nothing, and you only take the pairs of vertices you already know that are in distance 1.

Here is a test case that breaks your solution:

4
1 2 3 4
2 1 3 4
3 4 2 1
4 3 2 1

You will only find the edges 1-2 and 3-4, but not the edge 2-3.

(I already wrote a post with some hints for K, look above.)

First of all, in order to ease your processing you might want to convert the tree such that each node has only one key/value pair. Then each "component" will be represented by a chain of k/v pair nodes, connected from the first one to its parent (unless it's the main component), and from the last one to all of its children in the component graph. Now your problem is simply reduced to finding the first occurrence of some key on the path from any node to the root. This can be done in O(log N) time per query using a technique known as Heavy-Light Decomposition (HLD) — a fairly simple transform that allows you to get from any node in a tree to the root in logarithmic time, by potentially skipping over entire chains.

Here is an easy segment tree based solution:

First build a segment tree by traversing the tree in preorder, then each subtree forms a contiguous segment in the segment tree. Each node u in the segment tree has a map tree[u]. An update operation at node u takes a (key, value) pair and updates tree[u][key] with value if tree[u][key] is not set yet.

Run a dfs to build the segment tree, index[node] is the index of component node in the segment tree.

dfs (node, count)
    index[node] = count
    for each child u of node
        count = dfs(u, count + 1)
    for each (key, value) in property[node]
        // note that the segment (index[node], count) contains the subtree from node
        update (1, 1, n, index[node], count, key, value)
    return count

The update operation:

update (node, l, r, x, y, key, value)
    if x > y
        return
    if l == x and r == y
        tree[node][key] is not defined
            tree[node][key] = value
        return
    mid = (l + r) / 2
    update (node * 2, l, mid, x, min(mid, y), key, value);
    update (node * 2 + 1, mid + 1, r, max(x, mid+1), y, key, value);

Query operation:

query (node, l, r, pos, key)
    if l == r
        if tree[node][key] is defined
            return tree[node][key]
        else
            return N/A
    else
        mid = (l + r) / 2
        if pos <= mid and query (node * 2, l, mid, pos, key) is not N/A
            return query (node * 2, l, mid, pos, key)
        else if pos > mid and query (node * 2 + 1, mid + 1, r, pos, key) is not N/A
            return query (node * 2 + 1, mid + 1, r, pos, key)
        else if tree[node][key] is defined
            return tree[node][key]
        else
            return N/A

Now for query (x, key) answer will be query (1, 1, n, index[x], key)

It's possible that offline solutions got AC in problem C ? I code a offline HLD and i don't know why i got "Idleness limit exceeded on test 1" . Should be because i run a offline algorithm ?

Code: http://pastebin.com/6hE9PWaT

My idea is very similar to many people , for every kind of key i activate all nodes with that key and then answer all queries of same kind of key.

ну я обычно пользуюсь таким способом. 1. Создаем свою группу. 2. Добавляем тренеровку в группу. 3. Через тренеровку там можно смотреть всё.

Полный снимал кто-то с фотика. Ждемс)

Здорово, большое спасибо! Прикрепил к тренировке. Ждем того, кто снимал весь разбор. А, кстати, кто это был?

Теперь доступен полный разбор