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

Обратите внимание, что параллельно с отборочным раундом будет проведен Codeforces Round 389 Div.2 (рейтинговый раунд для второго дивизиона)!

Добрый день.

25-го декабря в 12:05 (московское время) стартует Отборочный Раунд 3 (и открытый раунд для Div. 2 по его мотивам) олимпиады для школьников Технокубок 2017. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунды и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд. Впрочем, если забудете — не беда. Через 10 минут после старта будет открыта дополнительная регистрация для опоздавших.

Зарегистрироваться на Отборочный Раунд 3 →
Соревнование открыто для всех в виде отдельного раунда для второго дивизиона (первый — вне конкурса).
Для участников отбора и участников из второго дивизиона будет пересчитан рейтинг.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. На кону — значительные квоты при поступлении в престижные технические вузы России и ценные призы. Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Желаем удачи на олимпиаде,
MikeMirzayanov и команда Технокубка

UPD: Разбалловка: 500 — 1000 — 1500 — 2000 — 2500 — 2500.

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

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

Unusual time >:( Never seen a contest this early before.

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

Ок

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

Contests are the best kind of Christmas gifts.

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

I hoped div 1 round and another big battle bitween nutela guys and me :D

Anyway thanks for one more contest :)

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

Want a contest for Div.1

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

"Wish you bugless code" I like this wish

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

good time for me. hope interesting problem

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

As usual, the score distribution will be released before the contest starts.

So does the ** ** ***** meme.

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

[user:Kostoma]? I think it should be Kostroma .

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

There are two contests in CF now, one is "Technocup 2017 — Elimination Round 3" and the other is "Codeforces Round #389". I do know that I should go to the official website if I were a Russian-speaking high-school student, but now that both the contests are in CF, and I'm an English-speaker, which one should I participate?

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

I'm sorry, but I think it will be understandable only for the countries of the former USSR )))

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

Oh, what a pity! This guy is so unlucky! xDD

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

Btw, Wont we get our new year gift this year? I mean, wont there be an option of changing handles this year? :( I'm fedup with my handle

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

Terms of agreement were in Russian. Will problem statements be in English?

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

sorry, but what is the difference between these 2 contest?

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

    First contest only for Russian pupils, second contest for participants from Div 2.

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

    Being more precise, the round that is "Technocup 2017 — Elimination Round 3" is a qualifying round for the russian school (Junior) informatics olympiad.

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

При попытке зарегистрироваться на ознакомительный/отборочный раунды пишет:

В этот контест могут быть зарегистрированы только официальные участники Технокубка

Хотя, на https://technocup.mail.ru/ зарегистрирован (авторизовался через it.mail.ru) на ту же почту, что и логин кф и сам логин кф указан в https://technocup.mail.ru/cabinet

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

why are the terms of agreement written in english? Should i just register or is there anything important?

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

For me this contest will be on the Christmas morning (I am Romanian). I won't be able to participate.

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

Hope there's no "greedy" tag ^o^

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

    Hi Andy.

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

      The last 4-5 contests have had so many greedy problems! xD

      Greedy problems are hard :'(

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

        I agree. They require a lot of out of the box thinking, unlike relatively similar level DP problems. A div 2 C greedy + constructive algorithms is much harder for me than a div 2 D DP.

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

Technocup problems are usually harder than the normal contest questions right? I am new here.

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

If I am a high school student, but not from Russia, it also can I compete for prizes?

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

Too many homework. Who can help me with my homework I really want to take part in it:)=>

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

=)

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

A great way to learn DFS.

Don't see this spoiler)
»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Wish to have upward rating as Christmas Gift...LOL But downward rating won't be able to restrain myself from participating rated Contests.

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

when is the winter look of the site coming? :D

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

Just curious, why do you have Div.1 Rated Unofficial Round for Technocup round 2, but not round 3. Is round 3 easier than round 2?

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

    For Round 2 we've added two extra problems specially for D1. This time we do not have enough time, sorry. We expect interesting D2 round, you can join in unrated way.

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

Bugless code would be great but I am happy with less buggy code currently. Thanks Mike.

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

Today is my birthday! I am going to take part in this contest as my birthday gift =D Thanks to codeforces!

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

Обидная бага — те, кто попал в топ 45% на прошлых раундах, но не подвтердили участие вовремя, не могут зарегистроваться официально на этот раунд. Или это так и задумано?

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

    Из двух прошлых раундов в Финал были приглашены по топ-100 участников. Задумано, что именно они не могут офиц зарегистрироваться в этот раунд. Работает как-то по-другому?

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

      Такая же проблема. Надо было подтвердить участие в финале по почте. Кто этого не сделал и в финал не проходят и не могут зарегистрироваться на 3 отбор.

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

        Напишите подробнее о проблеме. Я не в курсе подтверждений по почте. По моей информации в Финал были приглашены по топ-100 из раундов. Спасибо.

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

          Пришло вот это письмо. Надо было подтвердить до 13 декабря, кто этого не сделал, как я понимаю, не проходят в финал. На 3 отбор зарегистрироваться тоже не получается.

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

            Если вы попали в топ-100 в одном из трех раундов, то у вас еще будет возможность подтвердить участие.

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

Merry Christmas to all and wish you a positive rating change...

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

finished 3 problem, look at standing, rank 1200, neat. look again 1200 out of 2700, damn, rating will drop.

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

I did not understand problem C. :( Everyone did that and now problem B is Hacked. :|

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

Pretty scared about system tests. Every problem from B onwards could have some tricky corner-case. Good luck guys!

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

Problem F is similar to 364 Div1 B.

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

How can be hacked B?

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

Best tests for B:

abb
bab
bab
bba
aca
bdc
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

So fail;)

Why high school olymps always goes wrong for me?:D

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

Was pretest 8 of question E some edge case?

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

Problem C is much more easy than B :/ Solved C in 2 minutes, but B took about an hour

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

    Good for you — This sounds promising as you probably didn't get hack.

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

    First, I found it difficult to understand C. How did you solve it?

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

      Ex: RRRU|LU|RURUU|LULLL|DLDD|RDRD|LD| answer is 7

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

      There are many ways to solve it.

      1. Start currX and currY with 0. If 'R' occurs, then currX=currX+1, etc. And now check the distance b/w prevX,prevY) to (currX,currY). If it is increasing, then its ok and update curr. Otherwise it is required point, so count++, and update prev and curr.

      2. First delete all the consecutive duplicate characters (For example, RRLUDDL will be same as RLUDL). If current character is making U-type-turn, then it is the point,so count++. else move forward. (RUL,RDL,URL,RL,UD,etc will make U-type-turn). Solution for this : 23321935

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

Whats the logic for E,please?

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

    Binary search on the number of slices that each person can get .

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

    There are a couple of ways to solve it. I think the optimal way is this one:

    Keep the maximum value at the start, you'll choose only this one.

    Go through all the ones that have more than the current minimum value and split them. You'll do this O(log(max_value)) times, so the complexity is O(log(max_value)*n)

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

Hits for problem D?

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

    Hash and group the strings, then compute the results by taking strings greedily.

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

      u_u I could not found the greedy approach!I had no idea if it was convenient for a string to pair with itself or with his palindrome

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

        You can't be greedy in all the problem, only in the first part of it =P

        Try to separate it in two cases:

        1 — the string is not a palindrome? Than, I can put it on the final string IF AND ONLY IF I put his reverse; you can check if Santa will get happier with it xD

        2 — the string is a palindrome? If so, do I have 2 of it, and it compensates to put two of it on the final string?

        For the not greedy part, you have to look for the better string to put in the middle (it has to be a palindrome); notice that this is the same that removing one palindrome string from the final string

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

      Did you use trie as a hash or map<> was enough for this problem?

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

        map<string, vector > was enough.

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

          The cost to insert a string with size n into a trie is Θ(n).
          What is the cost to insert that same string into map<string, ..>?

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

            O(nlog(amount of input)), which is still good enough to fit into TL.

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

              I've understood from your previous comment that map<> is good enough for this task :)

              Now I am more interested in general understanding of the situation with keys in map and set.
              When we are inserting strings in map it is not the same as inserting integer values. Internally map has to perform O(log(m)) comparisons to find the place where we should insert the key. For string keys and integer keys this estimate is the same, but not for the comparison. It takes O(1) operations to compare 2 integers, but to compare strings of size n we need Θ(n) operations.

              So, to sum up, according to my calculations the complexity of inserting m strings of size n to map or set is O(nmlog(m)).
              Am I right?

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

What is the test 10 of problem E?

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

    this is it

    50 300

    9293 9540 6585 6756 215 6853 4819 3033 5529 8201 4072 4862 4071 5500 5717 229 7696 5440 4407 1108 1680 1974 5414 9053 8480 1030 5556 5551 4741 452 1045 2553 8944 7627 3737 3876 2846 3563 3246 8436 1075 2974 9410 1127 1968 830 1380 7371 6414 6384

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

Too bad it's not possible to hack own solution. While hacking others I realized, that my code has the same bug, so I could have used the extra 100 hack points, since it will fail systest anyways...

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

    U want to hack yourself?!:d and u want to earn points when hack yourself?!

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

    It is not too bad :D , if I realized that I will fail a test , I will hack my self then I will submit again with an if condition added xD which says if (input == certainInput) print (the right answer) , then I will hack my self again with another test case but the same concept ...... and I will get a lot of points which I don't deserve :D

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

      You can't resubmit after locking solution and you can't hack without locking

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

Что в 8м тесте в D?

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

    у меня он падал, если не обновить максимальную стоимость строки, которая будет стоять посередине(т.е. без пары) итоговой строки

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

Best contest ever

but it needs more time to solve all the problemset :\

Good Luck everybody :D

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

5651 registered for contest.
2745 have actually participated.

More than a half decided to skip this round. What happened?

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

wtf, my binary search in problem E was giving wrong answer? testcase 8. anyone please?

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

Problem C seemed really hard to me. What are some important observations for it that lead to a solution?

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

    Intuitively, we can tell that if the robot changes the vertical / horizontal direction, then the current position of the robot may lie one of the point.

    One of the way to approach this question is by keeping whether the robot is free to change it’s vertical or horizontal direction without declaring an extra point.

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

    OBS1:A path is shorthest path if is true that his length is equal to the manhatan distanse,I mean abs(X)+abs(Y)

    OBS2:Try to get minimum number of intervals where OBS1 is true

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

    The idea is that the robot will not decrease the distance from its starting position when he is moving to the target. That is, the value |x| + |y| should always increase when he is moving to a target. When you see that this value is decreased, that means he has reached a target before that move and he is now moving to the next target.

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

    If he is going from point p1 to point p2, he can't go to Left and Right beyond that path, only to one of then. Same for Up and Down ;)

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

    There are many ways to solve it.

    1. Start currX and currY with 0. If 'R' occurs, then currX=currX+1, etc. And now check the distance b/w prevX,prevY) to (currX,currY). If it is increasing, then its ok and update curr. Otherwise it is required point, so count++, and update prev and curr.

    2. First delete all the consecutive duplicate characters (For example, RRLUDDL will be same as RLUDL). If current character is making U-type-turn, then it is the point,so count++. else move forward. (RUL,RDL,URL,RL,UD,etc will make U-type-turn). Solution for this : 23321935

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

How to solve C ?

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

    Between any two points, to move on the shortest path, you will go only in two directions: {R, U} or {R, D} or {L, U} or {L, D}. You can't go R and after other moves, make L because it won't give you the shortest path. So, all you have to do is to check if you "change" your directions. For example, if you move to R and U/D, and then move to L, it means that you arrived at a point before move to L. In other words, you have to split your string in continuous substrings such that in any substring, there aren't 'U' with 'D' and 'R' with 'L'.

    Example: RUDRDDRUURDRDURDRD ===> RU|DRDDR|UUR|DRD|UR|DRD ==> 6 points

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

D hack case :

4 3

aba 4

aba 3

aba 3

aba -2

Answer : 10

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

free christmas trees for everybody

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

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

Merry Christmas!

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

После этого контеста я перестал понимать смысл претестов.

Серьезно, если посылать вслепую, ничего не изменится

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

That moment when you make 11 hacks on B and then recieve Wrong Answer on main tests xD Merry Christmas guys

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

why system test so quickly?

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

Problem E , WA 21 . Anyone knows why ?

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

Problem E statement says: "Santa Claus wants to present to everyone either a whole tangerine or exactly one part of it (that also means that everyone must get a positive number of slices)", that is #tangerines > 0, but in test #11:

total pupils k = 2000000000

total sum of parts of all tangerines = 128135987

Obviously, no solution. Answer in test is 1. Am I wrong?

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

the expected time complexity for E is Nlog2N right ? my Nlog3N solution got TLE.

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

Why in java when I defined a HashSet of Pair<Character,Character> and insert (a,a) then insert (a,b), the HashSet only contain (a,b), even the 2 inserted value are different (Obviously (a,a) != (a,b)) ?

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

    Sets by definition don't keep duplicates (duplicate keys in this case). So when you put (a, a) the value a is mapped to key a, and then when you put (a, b), the old value for key a is erased and overwritten as b.

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

      I know that, by I created a HashSet not a HashMap and as I know HashSet contains only keys (not pair <key,value> as you said) and doesn't contains duplicates, now Pair<"a,"a"> != Pair<"a,"b"> and these 2 are not considered duplicates, right ? or I'm messing something there ?

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

      You are wrong.

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

    It only checks for first element in pair. You have to create a custom compare function.

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

    Check your line if(a.charAt(i) != b.charAt(i)). You never insert (a,a) into the set.

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

anyone who got TLE on E? sorting the numbers of slices gives me AC.. it's weird..

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

B :O WTF !!

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

In what time does the ediorial come in general ?? I am new to codeforces.

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

taketop150

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

During the contest i've found out that my knowledge of C++ is really awful. I've been writing in Java for so long and changed my language about a week ago so that OK I guees. But could you guys please help me. In my code for D I had map<string, vector > val which meant all the prices of string s. After reading the data, I did the following: for (auto p : val) sort(p.second.begin(), p.second.end()) which, as I thought, sorted all the arrays in val. But actually it didn't because when I accesed val[i], it's elements were in input order. Why so?

23302886 that's the submission to make it clear.

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

    for (auto &p : val) 23308346

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

      Absolutely right solution failed because of only 1 character in code. So cruel. Thank you a lot. But could you please explain if I am right that for (pair<string, vector<int>> p : val) copies it's items, so in fact it works in O(n) ?

      Despite the fact that I could be in top-15 or even better, I'm not sad because finding this gap in my knowledge in CF round is much better than in some important rated olympiad. Also, I believe that the person who does such a stupid mistakes shouldn't be in Div1 :)

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

    Чтобы изменять элемент map'a надо писать: for (auto &p : val), т.к. иначе p только копирует значение.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    for(auto &p : val)
    
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

Can anyone help me in D? WA test 14, don't know what's wrong...

http://mirror.codeforces.com/contest/752/submission/23309705

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

Кто-нибудь может объяснить, почему моя D получает RE на 18ом тесте? http://mirror.codeforces.com/contest/752/submission/23308631

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

    Я поменял в компараторе <= на < и оно зашло. До этого падало на сортировке. Я не понимаю, почему. Есть у кого-нибудь предположения? UPD: кажется, понял

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

      Возможна ситуация, что a < b, b < a в твоем случае, а это плохо

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

How the output for first test case

4 RURD

is 2 ?

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

Where is UPD2???(((

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

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

TLE in div2E because I didn't sort the array :( such case very problem no wow

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

    Actually O(n × log2(n)) is little bit tedious solution for this problem. Mine got AC without sorting(same complexity). I used some bit-wise operations to reduce the time.

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

    Without sorting, solution of O(log(10^7) * (n + 10^7)) is getting AC.

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

    log(10^7)*log(10^7)*n is getting AC. However, I had to do a little optimization like getting rid of long long .

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

В задаче D wa 14 что делать?

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

Could someone tell me why my code on problem D was wrong on test 11? Is hash unavailable for it?I'm really confused.Thanks! Here is my code: http://mirror.codeforces.com/contest/752/submission/23309803

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

How to solve F?

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

    You can always use a single node, the centroid of the tree. Once you find that, find the list of each vertices in each subtree. Then put them in a priority queue and always make a pair one each from the two longest lists.

    Code

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

When will be editorial??

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

Can anyone tell how to solve E using binary search (if possible) ???

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

    Binary search the minimum amount everyone should have. To calculate how many people can receive this amount of slices, just run through every element in the array (since every element is independent). Here's my code (pretty short) 23302187

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

      Thanks a lot :)

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

      could you explain this part of your code?

      fr(n) {
                  int p = 1, j;
                  for (j = m; j <= a[i]; j *= 2) {
                      p *= 2;
                  }
                  c += max(p / 2, p - j + a[i]);
              }
      

      i know here you are finding for each tangerine how many people can get an amount m. I had to spend almost 3 hours to figure out an appropriate way to do this. Check my submission 23315399 (the howmany(wholesize,piece) function). I knew there must be a more concise approach to calculate this.

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

        I discovered it by observation. Notice that j = minimum (m * 2^k) that k is integer and m * 2^k >= a[i].

        If j = a[i] then the amount will be exactly 2^k (equals to p). Otherwise when a[i] is decreased by one, two of the "m" will become m*2-1 and not divisible anymore. The amount will decrease by one until the amount becomes 2^(k-1).

        Like this

        a[i] = 8, m = 2 : {8} -> {4,4} -> {2,2,2,2}
        a[i] = 7, m = 2 : {7} -> {3,4} -> {3,2,2}
        a[i] = 6, m = 2 : {6} -> {3,3} -> {3,3}
        a[i] = 5, m = 2 : {5} -> {2,3} -> {2,3}
        a[i] = 4, m = 2 : {4} -> {2,2} -> {2,2}
        
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

My first realization for Problem D to solve using Tries and some greedy approach. But it seems hard for me to code it. If someone thinks like me, please share your logic and code also. Thanks everyone. :)

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

    It's actually quite a hard problem, tbh. I thought I solved it in contest but failed systest. The approach is greedy, but you have to be very careful.

    First, sort the strings in non-increasing order of cost. Then, when we arrive at each string, we have to consider two cases:

    1. The string is not a palindrome. In this case, we want to pair it with the reverse of this string. Also, we want the beauty to be the highest possible, so we will take one of the "reversed strings" that we need to find from an std::set that contains the strings already traversed. Of course, this should be the one with maximum beauty and can be found using lower_bound().

    2. The string is a palindrome. We do the same process as #1, but slightly modified. Consider the case:
      4 3
      aba 6
      aba -3
      rty 2
      rty 4
      If we implement #1 with this test case, regardless whether the string is a palindrome or not, we will get an answer of 9. The actual answer should be 12. We notice that we can always unpair exactly one pair of palindromes that are already paired from #1 and we will put then in the middle of the final answer's string. Greedily, we will choose the one with lowest negative number (in this case it is -3). Let's denote this value as m. Finally, there is also in another case, where there are not matching pairs for the palindrome. In this case, we will put in the middle of the string, but only if the beauty of it exceeds m.

    The answer is retrieved from doing #1 on the whole set, regardless of it being palindrome of not, then along the way take into consideration the cases in #2. Final answer = (answer of #1) + m. Hope this helps.

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

      Thanks. I actually think to map the same string and their beauties. And another variable for putting string in the middle. Variable initialized to 0.

      1. If a string is palindrome, then I could take Even number of string like this and also 1 from putting in the middle. But I will take Even number from this if beauties positive. And if left any positive beauties string, then update the variable I mentioned above, which will maximize my middle string beauty.

      2. If a string is not a palindrome we can took even number of its copy ( I mean from several string). I will take up to it positive donation. Because if I discard it I will not get any positive donation. So, take as many as possible but the donation should be positive.

      For your test case:-

      aba is palindrome. So, it could stay in middle. I can take No even string first. Then, update the variable to 6

      rty is not a palindrome. So, I will take up to its positive donation as possible. So, I will take two from this. Donation: 2+4 = 6

      So, Total = 6 + 6 = 12

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

      The answer should be 6.

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

      How is the answer 12? Won't the final string be "aba" giving beauty 6. Am i missing something? Thanks.

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

        Optimal answer will be: "rtyabarty" with considering "aba" that has 6 beauty so max beauty will be 4 + 2 + 6 = 12

        Edit: nvm i realized I was mistaken, maybe he meant the second "rty" to be "ytr" then in this case it will be 12

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

      Maybe test should be like this? If you want answer = 12: 4 3 aba 6 aba -3 rty 2 utr 4

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

      the answer for your test is 6, or i didn't understand something.(?) //

      p.s by the way , i don't know why i am getting WA on test #8, if someone had the same problem i will be thankful if he will tell me which problem he had. :))

      p.p.s my code : CODE,PROBLEM D

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

    I don't exactly know, what do you mean when you say "greedy approach" but my solution is smth like greedy approach. Ask smth if you don't understand)

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

Can anyone tell what wrong am I doing here Solution

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

Когда уже будет список приглашенных?

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

    Такой же вопрос! И разбор где? Обидно как-то... Обычно сразу же, а даже комментариев никаких от авторов((

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

    Как гласит главная страница технокубка: "Результаты третьего отборочного раунда будут опубликованы позднее."

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

Who's waiting for Mike's blog on chaning handle like me!? :-""

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

When we can change nickname?

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

Есть еще какие-то способы попасть на технокубок?

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

    Боюсь, что нет. Вроде больше отборочных не планировалось.

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

      Жаль...Просто не было возможности поучаствовать в этом раунде. А дипломы каких-то олимпиад не могут служить пропуском?

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

Появились результаты, также 100 человек пригласили https://technocup.mail.ru/media/docs/%D0%A2%D0%B5%D1%85%D0%BD%D0%BE%D0%BA%D1%83%D0%B1%D0%BE%D0%BA_2017_3.pdf

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

hi first thx for the contest... this submission 23355723 is for problem D. i don't know why i got WA#8 :( please help me... thanks

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

    I don't know what is wrong with your code, but you fail in this testcase:

    3 3

    aba 5

    aba -5

    xyx 3

    answer is 5.

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

Can somebody tell me why i got WA with this solution?

http://mirror.codeforces.com/contest/748/submission/23331649

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

Can somebody tell me why i got WA in problem D with this solution?

http://mirror.codeforces.com/contest/748/submission/23331649

update : i got accepted

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

Could someone tell me why my answer got wrong in problem C in the pretest 14 (the answer was 50306 but i just got 50305) :(
http://mirror.codeforces.com/contest/748/submission/23372619