Educational Codeforces Round 32
By BledDest, history, 7 years ago, In English

Hello Codeforces!

On November 09, 18:05 MSK Educational Codeforces Round 32 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Mikhail awoo Piklyaev and me.

Good luck to all participants!

UPD: Editorial.

I also have a message from our partners, 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 Security — fill 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

  • Vote: I like it
  • +123
  • Vote: I do not like it

Comments Comments (75)
| Write comment?
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Yeah, definitely)

    Sorry for the typo, it is fixed now.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -51 Vote: I do not like it

Is it .....??

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    It means if and only if.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -33 Vote: I do not like it

      The regular "ïf" mean the same.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        It's different, if x then y can't be said as, "if you get y, then you can get x". But, x if and only if y, you could say, "if you get y, you can get x".

        → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

ignore pls

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve G?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain your solution in a bit detail.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 5   Vote: I like it +5 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 years ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

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

                  → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Why DP doesn't work in E ?

      We take %m of each element before storing in array, then sort the elements followed by L to R DP which says dp[i] = max(dp[i], (arr[i]+dp[j]) % m ), for all j < i. Before running dp[i] is initialized with max(arr[i], dp[i-1])

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Because of TLE+MLE

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        because there is no optimal substructure. To solve for i, you are taking (arr[i]+dp[j])%m, which might be less than (arr[i] + suboptimal[j])%m, where suboptimal[j] < dp[j]

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any idea why this is getting TLE ?

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

HOW TO SOLVE C PLEASE TELL!!

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Binary Search

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you elaborate

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Why people don't post Editorial quickly -_-

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +71 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
7 years ago, # |
← Rev. 8   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Derangement

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I just write bruteforce, see this numbers and use them

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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)

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        These numbers are subfactorials.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          But array should be {1, 0, 1, 2, 9}. I didn't use 0 and 1 indexes

          → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Is the contests pages down right now?

http://codeforces.net/contest/888

→ Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can anyone explain how to solve the problem G ?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 .

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve G?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh look I am famous!

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply