Блог пользователя MikeMirzayanov

Автор MikeMirzayanov, 10 лет назад, По-русски

Соревнование было перенесено в тренировки.

Завтра состоится четвертьфинал ACM-ICPC Южного подрегиона NEERC (2014). Жюри надеется на интересную борьбу, участники — на достойные результаты. Что же, завтра увидим.

А уже в ближайшую субботу (25-го октября) в 11:00 состоится онлайн-трансляция этого соревнования: [contest:481]. Вас ждут интересные задачи, которые жюри постаралось сделать интересными как для начинающих, так и опытных участников.

Конечно, контест будет нерейтинговым. Рекомендуется командное участие. Скорее всего, позже он будет перенесен в Тренировки.

Желаю участникам!

Председатель жюри MikeMirzayanov.

На закуску — виды Саратова:

  • Проголосовать: нравится
  • +353
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

prizes are depicted at bottom right? (i thought alcohol i got 3 hrs ago lost its effect ;)

»
10 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Yeah, I like the last Saratov view. haha

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -59 Проголосовать: не нравится

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

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I don't know man, I find that "Saratov Approaching" pic quite creepy. Like where is NSFL tag? Scarred4lyf :(

»
10 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

100 votes up for the bottom right Saratov view :D

»
10 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

The last Saratov view is mesmerizing *_*

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I love Saratov!!!

»
10 лет назад, # |
  Проголосовать: нравится +88 Проголосовать: не нравится

Oh, dammit. Codeforces is gonna be filtered soon in Iran... :|

»
10 лет назад, # |
Rev. 6   Проголосовать: нравится +141 Проголосовать: не нравится

I'm sorry to say that, but the "Saratov Girls" photo is taken at Sydney's Bondy Beach (Australia) for some Cosmopolitan Magazine event:

Click the image below to follow the link and switch to the 2-nd picture to compare:

1000 babes in bikini

And note Copyright 2012 News Group Newspapers Ltd and/or its licensors. No use without permission. Contact ... when right-clicking the image.

However, I think other pictures may be more authentic :)

And by the way I believe There are many more beautiful girls in Saratov — probably it would be easier to find them via social networks rather than from google...

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

WOW man! Is the last pic is Saratov's view or the prize for the winner's? LOL :v We really miss the onsite contest :(

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

This contest overlaps with the following contest

http://acm.timus.ru/contest.aspx?id=241

Lets hope one of the contests will be shifted :)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      you can use google calender , whenever you find a contest scheduled it and just check the calender every morning , it helps me a lot :)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я правильно понял, что сабмитов с вопросиками после заморозки нет?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Во-первых, контест пересекается с трансляцией УРКОП на Тимусе.

Во-вторых, почему в этот раз контест будет в Соревнованиях, а не сразу в Тренировках? С целью привлечь внимание большего числа участников?

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Нижегородский ГУ пишет в другом четвертьфинале?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Решили пропустить еще один год после того как узнали, что Влад может пропустить этот год и принять участие в следующем.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

To be noted, there is this contest on UVa http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=12 and another one in Timus http://acm.timus.ru/contest.aspx?id=241 same day/time.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Contest on Timus is better for Div. 2, Southern Subregional — for Div. 1

»
10 лет назад, # |
  Проголосовать: нравится -49 Проголосовать: не нравится

please change your photo this photo is not good for CF !! thanks

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Epic girls =D

»
10 лет назад, # |
Rev. 6   Проголосовать: нравится -71 Проголосовать: не нравится

I didn't know why, But since I was a kid, I had a feeling that I love Saratov. And now I know what was the reason of that feeling. :D

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Saratov is beautiful !!

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

that motivates to code :P

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I can't say anything:|

ACM & girls ...

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

Let vote them

I choose third one from left :D

»
10 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

Продрочено.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is it possible to keep rated contests for teams and give ratings to teams like you give ratings for individual users ?

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
  • 2012/2013: top 4
  • 2013/2014: top 4
  • 2014/2015: top 4
  • 2015/2016: ?????
  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Saratov: SU1, SU2

    2011/2012: top2

    2012/2013: top2

    2013/2014: top2

    2014/2015: top2

    2015/2016: ?????

    xD

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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)
    
»
10 лет назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

Спасибо, подрочил

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This picture on the bottom right corner really has nothing to do with a programming website Always distract me when I open the site.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +241 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

В гостинице Спорт ребята толи с горя, толи с радости напились в салат, пробегающий мимо чувак почти попал на меня вышедшим у него изо рта содержимым. Передаю ему привет:)

»
10 лет назад, # |
Rev. 4   Проголосовать: нравится +49 Проголосовать: не нравится

Вот так рождаются клёвые задачи!


<-- Остальные фотки в предыдущей правке...
Кто-нибудь знает, где можно посмотреть официальные фотки ЧФ? :)

»
10 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

В онлайн-трансляции будет заморозка? Так было бы намного реалистичнее.

На CF вообще есть такой функционал? В тренировках это не помешало бы.

»
10 лет назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

Trust from the GOD!!! What is this picture??? Do you know hove many person will see that picture???
I GUESS NEXT TIME YOU WILL NOT PUT BAD THINGS IN THIS SIDE

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

Really, can that picture be removed? In addition to different religious views, consider a high-school teacher recommending the website to his/her students. If this picture will be the first thing they will see, it might lead to some embarrassing situation and the teacher getting fired.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why can't I register a team ?? :\

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It says in the post that teams are preferred. But how to register a team for an upcoming contest?

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Кому интересно: завтра также кыргызский четвертьфинал. Смотреть тут: http://olymp.krsu.edu.kg/ContestProblemset.aspx?contest=78

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

I think this contest is same with TIMUS

Duration and starting time are same.

»
10 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Ranklist is broken. My solved G disappeared from the ranklist after a while. WTF?

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +29 Проголосовать: не нравится

    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.

»
10 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

Cant apply binary search on them(hot chicks) due to random distribution... :P

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the 31st test for F?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We've made about 15 WAs in that case too

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    my error was a wrong algorithm...

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      You are choosing the max cut, then choose the next max cut, but this is totally wrong, You have to try all possible cuts and select the maximum cut on the left or on the right.

      in case 31:

      9 3

      15 15 15 30 1 30 15 15 15

      You select (10+1+30) which is 61, then you have only (15+15+15) on the left or the right,

      but if you try all cuts, you will get (15+15+30) + (30+15+15)

      something like this: 8410587

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      Directly while loading the input you can color one side of each -1 blanket any color you like (e.g., add all of them to color 1), the solution always exists anyway, and the code gets simpler: you simply always take the color with the least (non-zero) number of blankets, and if it is not enough, you fill the rest from the color with the most blankets.

      (This is essentially the same algorithm as used in the Alias method)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Strange, I'm doing the same, yet I can't get past test #2. I made random tester and checker just to find that my code easily passes a few million tests. It seems I am missing something, can somebody help me with tests/suggestions?

        The code is 8417893.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Test #2 is most likely the second example input. You are failing it because you are not outputting the blankets in the order in which they appear in the input. (Your third blanket is 3 4, but one of its sides should be 1.)

          I got one WA for this during the actual contest, I was also too careless in reading the statement :)

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I've get AC using your instructions and read about Alias method but can't understand why is it the same algorithm ='(

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Do you have a proof of why this works? (Or a link to a proof; I couldn't find an editorial.)

      We considered this greedy approach, but since we couldn't prove it, we didn't implement it.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Here I am giving the proof of problem B. We know that we can easily solve the problem when n=2. Now if we have n=x then we can simple reduce it to n=x-1 using the technique described above,i.e.,take the color with smallest number of blankets and complete this set with any other set of color u want(above given is the set of color with maximum number of blankets). One thing should be kept in mind that the other chosen set must have blankets greater than required number.

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

editorials?

»
10 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

First time I see, a grandmaster wants to cheat with me! Cheers!

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How many comands go from NEERC Southern Subregional to 1/2 final NEERC Spb?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Как решается C и K?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 9   Проголосовать: нравится +5 Проголосовать: не нравится

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

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

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

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Мы так делали. Вершина u — предок v <=> tin(u) <= tin(v) and tout(u) >= tout(v). Для каждого свойства будем держать список вершин, у которых оно есть, упорядоченный по tin(u). Пусть есть запрос — вершина v, свойство x. Нам тогда нужно искать такую вершину u в списке x, что tin(u) <= tin(v) and tout(u) >= tout(v) в этом списке, при этом tin(u) принимает наибольшее значение. Найдем бинпоиском самое правое tin(u) <= tin(v) в нашем списке. Теперь нам нужно на префиксе u найти вершину r, у которой tout(r) >= tout(v), и при этом она такая самая правая. Найдем это с помощью бинпоиска с максимумом на отрезке, если использовать sparse table, то получится NlogN.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Пара замечаний:

1) После заморозки можно узнать вердикт другой команды. Достаточно зайти в профиль одного из участников, и там все будет видно.

2) Было бы неплохо перемешать задачи. Думаю те, кто уже посмотрел результаты четвертьфинала, уже знали, что I — халява.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

D — Data Center. I dislike such "obfuscation" that LOW voltage is marked by bigger value (1) than HIGH voltage (0), why not ask to find minimum servers with HIGH voltage, which should be marked as 1? I misread (as usually) statement, made opposite, and gain WA #12 8408879.

»
10 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Когда будет открыта дорешка? Те кто снимал разбор, дайте ссылку пожалуйста.

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Is this Contest archived? I can't resubmit any problem!

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

This contest is no longer on the contest page. Why has it been removed ?

EDIT: I now see it has been moved to the gym :)

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can anyone give me some hints about prob. G and K?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

I can's submit problems in the Gym. It goes to a link like this — http://codeforces.me/gym/100513/problem/C?csrf_token=a9770299g5h52c9hda3d7887h9h9313a and shows error code ERR_EMPTY_RESPONSE

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится -21 Проголосовать: не нравится

"Network error"! I can't submit! :(

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will the editorials be published?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone kindly outline the idea for Problem K?

My idea was to regard graph as a chain for every vertex to create distance matrix,then use floyd to compute shortest distance, finally union set to output n-1 edges 8417836 don't know where it is wrong and it keeps wrong answer for test 4

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any idea about problem C ?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Bruce also mentions heavy-light decomposition in his blog but I think that it is an overkill and that my solution is simpler to implement. Here it is:

      Preprocess the tree into a list of (key,value) pairs by running a simple DFS and maintaining a stack for the occurrences of each property. Here are the steps:

      • Each time you enter a new vertex v, append all its properties to the list, push them into the corresponding stacks, and then store the current length of the list into L[v].

      • Each time you finish processing a vertex, pop all its properties from their stacks and append the new tops of those stacks to the list (these key,value pairs just became visible again).

      After this preprocessing, for any vertex v and any key k, we simply need to find the last occurrence of k in the first L[v] elements of our list. To do this quickly, just build an interval tree on top of the list, and in each node store the set of keys that occur at least once in its subtree.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        That is slightly simpler (although the heavy-light decomposition only takes about 25 lines of code). I suspect it could be simplified further to avoid the interval tree: just keep a separate list for each property, with a field for the position in the original combined list (which doesn't physically need to be constructed). Then the search just becomes a binary search on the right per-property list, and can use lower_bound.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

          This is exactly how I solved it (8408659).

          For each property:

          Consider only nodes that contain it. Iterate these nodes in the dfs order (we can run a dfs beforehand to determine this). When you enter a node, push its value to the stack. When you exit from a node, pop its value. Since there might be missing nodes (not all of nodes have this property), we can add some extra spaces between the sequence of nodes to simplify the query process. Eventually, we just use lower_bound to find the relative position of the given node in the preprocessed sequences and return its value.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Yes, you should construct an online solution. This is an "interactive" problem: you can't read the next query until you print the answer to the previous one and call fflush(stdout).

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ok i know it now , Thank you very much , it's first time that i try to solve an interactive problem :v.

        PS: How do you solve it with an online solution ?

»
10 лет назад, # |
  Проголосовать: нравится +66 Проголосовать: не нравится

I've added analysis of all the problems except L to my blog.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

После того, как перенесли в тренировки, нет возможности просмотреть кода сданных задач другими участниками. Как-то можно найти их?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

Разбор Но здесь нет задач A,B,C, т.к. их снимал другой человек

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem A? Как решать задачу А?

UPD: ;) find http://codeforces.me/blog/entry/14368#comment-194335

»
10 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

could adminstor put the Ural Regional School Programming Contest 2014 contest into the gym to practice,it is also a very good contest,thanks

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am left with all these girls, you fall in love you want

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

I think I didn't understand problem 100513L - Useful Roads . Can someone provide me with the output for the following test case?

6 6
1 2
1 3
1 4
2 5
2 6
3 6

I think the useful edges are all, cause all of them can be used to go to some vertex.