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

Привет, Codeforces!

9 ноября в 18:05 по Москве начнётся Educational Codeforces Round 32.

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

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

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

Задачи вместе со мной готовил Михаил awoo Пикляев.

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

UPD: Разбор.

У меня также есть сообщение от наших партнёров, Harbour.Space University:

(перевод будет чуть позже)

Thank you for taking part in the 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC. It was a pleasure to have you on board. We hope you enjoyed it and we would love to have you back next time.

Congratulations ITMO and Harbour.Space University teams for winning divisions A and B! It was amazing watching the scoreboard throughout all nine days as teams from New South Wales, Saint Petersburg, Tokyo, among many others, challenged the top spots. Watch the recap here!

``Geometry is the key to success in modern contests'' states Andrey Stankevich, coach of 7 ACM-ICPC World Champions

Lecturing both divisions A and B, Andrey brought a vast wealth of knowledge to the boot camp, and shed light on how to better tackle the problem sets that teams will face in their upcoming regional competitions.

“What technology should we use to analyze big data?” asks Alexey Dral, Head of Data Science School at Corporate University of Sberbank

Leisure day was a full one, with bus city tours, to gaming, to lectures and workshops. We had many special guests Sberbank, including Alexey Dral, who talks about the impact of a boot camp that is not only focused on the coding aspect, but the machine learning, the data processing and the practices that each participant can utilise to become an ACM-ICPC competitor to be reckoned with.

Scholarship Information

We are offering a Scholarship for each of our three tech programmes: Data Science, Computer Science and Cyber Securityfill out the Form for the January 2018 programme start period or the September 2018 programme start period. We will contact you soon. Can't wait to see you here!

Go to form

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

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

9th Nowember seems like a good date for a contest :3

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

Is it .....??

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

Andd 5 page queue during contest................

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

Why in all of your problems in stead of "if" you wrote "iff" ?

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

ignore pls

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

How to solve G?

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

    I'm quite certain that it can be solved by algorithm Boruvki

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

    I used tries, but it passed with just 150 ms left, will probably give TLE on hacks. Also, weirdly, none of test cases have n = 1.

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

      Can you please explain your solution in a bit detail.

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

        https://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems

        Use the technique in the above mentioned thread to find minimum edge between two nodes, one of which is already visited. We can find minimum among possible edges by using priority queue.

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

          I think I might have done something similar. However I'm not sure what the complexity is.

          Basically every time I select the existing vertex with the smallest edge. However it may be an edge to the vertex which is already in the tree. Then I have to remove that edge and find a new one to non visited vertex. I am not sure what is the limit of such edges. Isn't it O(n^2)? I can get an edge to already visited vertex either when I found a new non visited vertex -> O(n) or when I removed the edge to the visited vertex -> O(n^2)?

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

          Ok, here is my accepted O(n^2) submision. Algorithm: at each step choose the minimum edge to connect a vertex to already constructed mst.

          Counterexample:

          At some point we have some mst and the vertices in it are processed. Let's say that all of these vertices point to unprocessed vertex: nxt.

          Now we choose the minimum edge to nxt, from already processed vertex cur. Now we remove nxt from trie and we choose next best edges for cur and nxt and they both point to unprocessed vertex nxt2. These edges are more expensive than edges we already have in the queue: x — nxt.

          Because nxt is now in mst, we have to remove all of these edges. Every time we remove edge x-nxt, we find a new minimum for x, which is nxt2.

          This way, before we add nxt2 to mst, we have to revisit all existing vertices. The same situation will happen for nxt3, etc.

          Could you please tell the difference between your approach or do you also have O(n^2) solution?

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

            I did the same thing, however I dont think it is O(n^2). I think it is O(nlog^2(n)). I mean it can only be O(n^2), if all/most numbers keep getting the same number as their minimum edge.(all vertices point to same nxt) But can that happen? Or can it be shown that vertices pointing to the same number will be O(logn)?

            I can't prove it, but I can't think of an example where all numbers get same minimum. What do you think?

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

              Edit: Please Ignore. It is wrong.

              I think I found a proof:

              Suppose there are k numbers pointing to the same number nxt. We try to prove that k = O(logn)

              Lemma 1: For each bit i, there can only be one number in which the ith bit is different from ith bit of nxt and all previous bits are same.

              Proof: Suppose there exist 2 numbers and first x bits of the numbers match with nxt, and (x+1)th bit is different from nxt. Then the numbers will match to each other since xoring different bits always gives 1, and 2^c > 2^(c-1)+2^(c-2)+...+2^0 for all c.


              In a number n, there will be logn bits. Let us define a function f(i, nxt) which will return all numbers who have exactly first i bits same as nxt, and point to same nxt.

              So, Maximum number of numbers that can point to same nxt will be: Sum of f(i, nxt) for all i belongs to [0, logn]

              From lemma 1, f(0, nxt) = f(1, nxt) = ... = f(logn, nxt) = 1.

              So maximum vertices that can point to nxt = k = logn

              So time complexity for this approach = O(nlog^2(n))

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

                I'm not sure that I understand Lemma 1 and its proof. I don't understand why can't you have 2 vertices already processed which have the same x+1 bits, the same x bits matching with nxt and x+1 bit different. They can't match with each other (or they already did) as they are both processed and in MST.

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

                  Yeah.. I am sorry, it is wrong and makes no sense. I don't know why I wrote that.

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

How to solve E?

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

    Divide and conquer, or meet in the middle. Whatever you wanna call it

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

    Meet in the middle technique:

    Divide the array into two smaller ones of size n/2. Now you can brute-force all the possible combinations of values you can get by choosing subsequences of each array. Store them in two sets. This step takes O(2^(n/2))

    Now iterate through the first set. Our goal is to get the closest number to m-1 (which is the best answer possible). So, for each number x in the first set, we can binary search for the best value y of the second set that gets us closer from m-1. Keep track of the maximum x+y gotten, that is the answer

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

    I solved it using Meet in the middle + Binary search

    Split the n numbers to 2 sets, find all the possible subset sums for every set, that can be done in O(2^(N/2)) for each set

    sort one of them and iterate over the other set, for every element, binary search for the value that gives the max value % m

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

HOW TO SOLVE C PLEASE TELL!!

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

    Binary Search

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

      Can you elaborate

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

        Sure. If you do not know about binary search better learn it from top coder or some other popular resources.

        After that, notice that if you can find an answer for length k, then as well for any length > k, so it's a go left binary search. You try to reduce values of k, and keep validating it as long as it is possible, once you see no more left movement can be done you return.

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

    I used simple greedy. Mark positions of occurrence of each letter in vector v[ch]. Additionally, add -1 and n to it (indexing begins from 0). Now calculate the max distance between 2 elements in each v[ch]. Take min of all these maximums.

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

    For every letter from a-z that exists in the string find the maximum k such that any substring of length at least k contains that letter. Or in other words find the maximum difference between two contiguous occurrences(or boundary) of that letter. Report the minimum k as the answer.

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

    I did without B.S.

    what I did is:

    For any String minimum k value goes to l/2+1 where l is length of string...

    For ex:abcde k=3 and abcd k=2

    I checked for all character,found maximum of distance b/w them..And took minimum

    That will be final answer...32173323

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

Why people don't post Editorial quickly -_-

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

    When it's your turn for preparing editorial, you will know why.

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

      May be :(

      But when I am waiting to read the editorial and solve the problems after the contest but the editorial isn't appearing, :/ I forgot to solve it later. For me, Later is never :( I don't know about others...

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

      Well, if I was hosting a contest, I would make sure to have the editorial completed before the contest begins.

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

    For this contest open hacking phase is still going on. They can not post editorial before it finishes.

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

I found some mistake in one of my submissions and resubmitted it before the contest ended. Will it be considered in case 1st one is hacked?

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

Me at problem D be like:

Solution for k = 1 is obvious.

using ruby to generate the permutation, and do a brute force solution (for small number)

saw a pattern for k = 2.

saw a pattern for k = 3

1 hour left to search for k = 4

2 minutes left (probably found a solution for k = 4)

oh, it is wrong, Ok...

edit: HOLY SH*T, my only mistake was the type of integer, should be int64 instead of int32.

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

unfucking belivable you just copy people problems and don't mention their name. It was a couple of months ago i send problem F to Edvard.

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

    The thing is that Edvard doesn't take any part in preparing Educational Rounds now. He doesn't send me any problem proposals or anything. So the fact that we have prepared a problem that you sent him is just a coincidence.

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

How to solve D

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

    Derangement

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

    1) We always can get sequence 1, 2 ... n

    2) Then calculate answer for each k from 1 to k (from input). We can swap C(n, k) sets of positions. Numbers of swaps for each set is !k (subfactorial).

    ans = 1 + ∑ C(n, i) * !i (i from 1 to k)

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

      How did you get those constants in array arr{0, 1, 1, 2, 9}?

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

        I just write bruteforce, see this numbers and use them

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

        those are the number of permutations of k elements where no element stays in his original(fixed) postition. you can find them yourself by hand for small k's or use this formula a(k) = k*a(k-1) + (-1)^k (proved by Euler)

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

        These numbers are subfactorials.

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

А правильные решения задач где-нибудь выкладываются?

И можно как-нибудь сортировать решения других участников по языку программирования? Я пока знаю только Питон, а попробовать взломать чье-нибудь решение очень хочется :)

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

    Да, но позже Да, можно, заходишь во вкладку статус, дальше внизу страницы видишь Фильтр статуса, выбираешь нужный язык, вердикт и статус и нажимаешь применить

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

Is the contests pages down right now?

http://codeforces.net/contest/888

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

Can anyone explain how to solve the problem G ?

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

    Let's say that you have a lot of groups and want to merge them together with the minimum answer. You know the very base case that every node in a separate group, but how we will continue a lot of xor problems solve by trie store binary bits instead of strings.

    Trie or prefix tree store one copy of every same prefix of the number, here we will put every number from the most significant bit to least significant bit. start traverse through trie all the numbers will have in common the very first node in the trie every node we will have 2 choices in this node (1 or 0) we need to merge the 2 groups by each other, every group of them will connect internally by each other later by the same way and its very obvious because every time we move in the trie the value that we add to the answer will decrease. We will connect the 2 groups by a search for every number in the first group and try to find the minimum number to it in the second group so now we connect the first group to the second group, but internally nothing happened we will move to the first and second group and do the same algorithm.

    Algorithm: when traversing the trie if there is one edge only(1 or 0) you will go through it without adding anything to the answer if there are two edges(1 and 0) you will go through the two edges with adding value to the answer.

    Value: as we said before we need to connect the two groups together with the minimum value, for every element in group 1 we will find the minimum element for him in the second group and take the minimum one.

    Simplest code: here

    Sorry for poor English and poor explanation :'D .

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

How to solve F?

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

I have solved C using binary search but my submission got time limit :((( can any one explain why ??

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

how to solve G?

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

this is weird for 2 days this problem was accepted and today it became wrong answer

http://codeforces.net/contest/888/submission/32182493

i tried the test case 28 on my codeblocks and my output was 2 but here they say it's 1

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

Oh look I am famous!

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

Почему не показываете людей, отправивших первое полное решение на каждую задачу?

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

Can you fix the typo in the statement of problem D? Double f's in if.