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

Автор awoo, история, 7 лет назад, По-русски

Привет, Codeforces!

27 октября в 17:05 по Москве начнётся Educational Codeforces Round 31.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Владимир vovuh Петров, Алексей Perforator Рипинен и Михаил MikeMirzayanov Мирзаянов.

Удачи в раунде! Успешных решений!

Поздравляем победителей:

Rank Competitor Problems Solved Penalty
1 biGinNer 6 175
2 natsugiri 6 228
3 palayutm 6 283
4 LHiC 6 293
5 eddy1021 6 295

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 No_One_Loves_The_Weak 18
2 halyavin 22:-10
3 dreamoon_love_AA 33:-35
4 kuko- 15
5 STommydx 12:-1

Было сделано 259 успешных и 368 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A eddy1021 0:01
B eddy1021 0:02
C vintage_Vlad_Makeev 0:06
D cyand1317 0:18
E eddy1021 0:36
F zscoder 0:35

UPD: Разбор доступен по ссылке

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

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

?detar ti si

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

I have made a chrome extension which automatically downvotes any comments with the phrase "is it rated". You can download it from: goo.gl/V8KP39

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

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

Is it rated? Фалунь Дафа хорош!

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

Когда хотел посмотреть комментарии, а там сплошные спойлеры на Is it rated?

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

UPD: FIXED!

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

Score distribution? :)

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

Is it rated?

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

Very nice contest!!! D was a very interesting problem, it tricked me into thinking I have a correct solution when it was miserably wrong.

Can you please tell me how to solve D? I noticed that it will probably be some kind of divide and conquer but that's where I got stuck, but I might be completely wrong (again.. ).

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

    It's just merging 2 to 3 piles of balls every time, with each time the cost.equals to the sum of the number of balls merged, so a greedy algorithm would work.

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

    Think backwards. You have all the elements in their original position and you want to put them in starting position with smallest cost. To solve this, you can adapt the greedy algorithm to find the Huffman code. There are two main differences:

    1) You get the 3 smallest elements to generate a new one (instead of two).

    2) In the case when you have a even amount of elements you'll get a suboptimal solution if you follow this algorithm. But you can be greedy here too, just convert the smallest two to a new element to get and odd number of elements.

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

      Thank you!

      Thinking backwards can sometimes be very helpful, but I've never used it on a construction/greedy problem.

      I'll bear this trick in mind.

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

      how did you come up with this solution?

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

        I tried some approaches that didn't work. Until I realized the problem we were trying to solve was almost the same that this one: https://en.wikipedia.org/wiki/Huffman_coding#Problem_definition

        You can see the relation if you see the problem backwards. Initially you have all colors in their positions and you want to bring them all to first position.

        This problem has a known greedy solution. If you don't know the solution for the Huffman Coding problem, please read about it. You'll need to know it in order to understand next paragraph.

        The thing is that now you have a ternary (not a binary) tree. So we must adapt the solution. My first try was to greedily try to get the 3 smallest values and merge them. But this does not work when you have a even number of colors, because you'll have to make an operation with only 2 nodes.

        First I tried to make this operation using two nodes as late as possible in the merging process (when we have only 2 or 4 nodes left), but this is not optimal. So I drew some test cases and concluded that you should do it as soon as possible, so every case you have a even number of nodes you should merge the smallest two and get a problem with odd number of nodes, in which you can apply the greedy approach.

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

      Can you please explain the solution for problem-D in detail. Can you please explain what changes when n is even. I am still unable to to visualise the solution you told.

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

    Greedy will work to solve D.The process of D is to build a Huffman Tree.So we can construct a Huffman Tree with 3 leaves each node that isn't a leaf to get the answer.

    What's more,there're similar problems in China.

    1. http://uoj.ac/problem/130
    2. http://tyvj.cn/p/1066 (In Chinese)
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Соревнование завершено, откроют ли тесты в дорешке?

Интересует 8-й тест задачи C...

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

    Скоро автоматически откроются, в течение часа обычно становятся доступны. 8 тест рандомный, n = 10000, ничего особо не видно

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

      Мне было видно) Рекурсия моя накрывалась на таком размере) Уже исправил)

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

Seems that a greedy algorithm would be the best solution for F while I used min cost flow. The time limit is quite loose.

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

defender & Hacker same person :p

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

What is the hack for div2 B ?

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

6 1 4 4 4 4 4 Why 38 in this case in D ?

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

    1 4 4 4 4 4

    take (1, 4, 4, 4, 4, 4) and spread like this (1, 4, 4) (4, 4) (4) total cost = 21

    take (1, 4, 4) and spread (1) (4) (4) total cost 9

    take (4, 4) and spread (4) (4) total cost 8

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

How to solve E?

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
  • can someone explain what did they mean with ordered pairs in c.
  • the pairs are ordered based on what and when we can make a pair of (x,y) and when we can't I really hate when i don't understand the most important line in the problem XD .
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    It means pair (x, y) is not the same as pair (y, x).

    Btw you can always ask jury a question during the contest, use it if you don't understand something in statement

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      • thx finally i solved it... I wonder when i will be able to solve D problems I have no idea what am i supposed to learn to do that there are alot alot of algorithms and learning them all is not a great idea .
      • isn't there a beginning to train on harder problems ?
      • btw why pressing enter here isn't working i can only make lines with bulleted list
»
7 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

I think educational rounds should be rated. I mean, they are perfectly good rounds

I consider some problems to not have well known solutions (even though this information is in the description of the educational rounds — maybe the ideia was once used somewhere else, but to recognize the idea in a particular problem statement is always a unique activity) and usually very few people can solve all problems (depending on the difficulty maybe it could be rated just for div 2)

Also if someone does not wish to compete they could just do the round in a virtual participation

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

    Oh boy, commenting without knowing codeforces tradition of downvoting.... That's gotta hurt.

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

      So, he can't write his opinion about site ? Let's remove the comments. Nobody will write their "stupid" opinions.

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

can someone explain me how to solve c i didnt' get why people are multiplying the size of the group of connected station with itself because it is not necessary the if there is path from(1,2) then there is also a path from(2,1).

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

    For every group of connected stations, it is necessary that every station is reachable from every other station since every pi's are distinct which means that only one train can leave a station(i's are distinct) and only one can reach it(pi's are distinct). Due to which every connected stations would form a cycle and would contribute it's size^2 to the final result.

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

    In this problem, the graph is directed, so if you have a strong component, it is a cycle.

    In a cycle, if you can reach vertex Y from vertex X, you can reach vertex X from vertex Y. In other words, all vertex in the same component can reach all other vertex in this component (including itself).

    So, if you have a component with N vertex, then you have N * N pairs reachable from each other.

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

hey...guys help......gettin WA...i ran dfs and got all components...then i joined the first two components with highest vertices ..then N*N (N=number of vertex in a comp) for all components...but getting wrong answer on case 18 shows my output>ans

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

where can i see the problems? im new in this page. :( yesterday i registered for the concourse, but i can't participated. can you helpe me to find the problems please?

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

where is the editorial ?

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

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

I am confused with something.How can someone solve two problems in two seconds...