skywalkert's blog

By skywalkert, history, 5 years ago, In English

This editorial corresponds to 2017 Chinese Multi-University Training, BeihangU Contest (stage 1), which was held on Jun 25th, 2017.

There are 12 problems in total. You can solve them as a team member or an individual in a 5-hour contest. By the time you join as virtual participants, 770 teams, or even more, will compete with you virtually.


Editorial in the English version has been completed, which is a bit different from its Chinese version (mostly because I don't want bad editorials to ruin the contest, lol). However, for the sake of hiding spoilers, editorials are locked and will be shown as the following conditions are met:

  • Editorials for the easiest 4 problems will be revealed after the replay (all unlocked);
  • Each for the hardest 5 will be released if the corresponding problem has been solved by at least 5 users or teams on Codeforces::Gym (all unlocked);
  • Each for the others will be published when the relevant problem has been solved by at least 10 users or teams in virtual participation (including the replay) on Codeforces::Gym (all unlocked).

Or you can find solutions in comments?


102253A - Add More Zero

Idea: skywalkert

solution

102253B - Balala Power!

Idea: sd0061

solution

102253C - Colorful Tree

Idea: sd0061

solution

102253D - Division Game

Idea: skywalkert

solution

102253E - Expectation of Division

Idea: skywalkert

solution

102253F - Function

Idea: chitanda

solution

102253G - Gear Up

Idea: constroy

solution

102253H - Hints of sd0061

Idea: constroy

solution

102253I - I Curse Myself

Idea: sd0061

solution

102253J - Journey with Knapsack

Idea: skywalkert

solution

102253K - KazaQ's Socks

Idea: chitanda

solution

102253L - Limited Permutation

Idea: skywalkert

solution

Hope you can enjoy it. Any comments, as well as downvotes, would be appreciated.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Only A and K are unlocked. What about B and F?

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

    What do you mean? Can you see in this blog the author names and solutions for A, B, F and K?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -35 Vote: I do not like it

      Calm the fuck down, dude! What I'm saying is we still don't have access to the solutions of contestants on the contest page for B and F, unlike A and K (the codes for which are available). Can you not see there? :D

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

        Easy, dude. All public contests in Codeforces::Gym do not show tests and allow view submissions only to solvers. These rules are fixed by Codeforces admins and we can't change the setting.

        'solution' in this blog only means some description about the stanard algorithms and programs. Sorry for misleading.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -29 Vote: I do not like it

          But still somehow you guys managed to show the submissions for A and K. Nevermind! May I know the second test case of problem B, because I did the exact same thing as said in the editorial and it shows WA on TC2.

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

            Well, 'allow view submissions only to solvers', which is literally written in the setting page, means that when you have solved a certain problem, you can view all submissions in this problem, except those submitted by someone who has enabled COACH mode. So, as you team solved A and K, that's why you can see something.

            By the way, your last submitted code for B may fail on some cases like 26*26*26 strings of 'a' and 1 string of 'b'.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried solving A like this (m * log10(2) + 1); But it's showing ans = 20 for m=64.which is wrong. while it shows correct output for m values=4,5,6, 7 and various others.

->And if i do floor(m * log10(2)); now it shows 19 for m=64 which is correct. while it shows wrong for m values = 4,5,6,7 and various others.

ANyone can help?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone post the solution of B

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Problem B? I am not able to understand problem statement.

Also can you explain how this ans came for this test case. Input- 3 a ba abc

Output- 18221

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry for necroposting.

What is the solution in expected sqrt(n*m) for H?

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

    And how to solve I in Klog(K) ?

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

      There is a problem requiring $$$\mathcal{O}(K \log K)$$$ algorithm. You can solve that problem on LibreOJ, or just view accepted solutions.

      Brief description:

      There are $$$n$$$ sets of numbers. The $$$i$$$-th set contains $$$c_i$$$ integers. Note that a value may be contained multiple times in a set, but every two copies are considered different.

      You can select one integer from each set, and then get a score equal to the total sum of the selected integers.

      You are asked to find $$$k$$$ possible schemes with the largest scores, and output these scores in decreasing order.

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

    What is the solution in expected sqrt(n*m) for H?

    It should be a typo.

    Split the range of values into $$$T$$$ blocks, and there are at most $$$m$$$ useful blocks. If generated elements are random enough, each block will contain $$$\frac{n}{T}$$$ elements. Erasing useless elements may help the further process, but it's just an optimization of constraints.

    I think the expected $$$\mathcal{O}(\sqrt{n m})$$$ should be $$$\mathcal{O}(n + \sqrt{n m})$$$.

    And how to solve I in Klog(K)?

    Just boost the process of sequence merging by data structures like Heap or SegmentTree (additional definition of states required).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is nlogn a typo in J editorial? The best solution I could get was nlog^2(n) using online fft to calculate the partition generating function.

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

    It can be done in $$$\mathcal{O}(n \log n)$$$ using Euler transform and Newton's method. These two approaches both require the knowledge of Taylor series expansion.


    Here's the detail for faster solving. Alert: TL;DR.
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

skywalkert please release the editorial for problem E.

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Hi, I am the original author of problem H. Recently I have found out a really elegant way to solve it.

Basically, we can realize the classic nth_element in linear time.
Then, what if we deal with the m positions at once?
Still, we use linear time partition, to partition array a[0, n) into three parts, [0, l), [l, r) and [r, n).
The positions(elem. of b) in [l, r) is definitly solved.
If any elements of b fall in [0, l), we go to solve sub-array [0, l) with those elements recursively. Also the same for [r, n).

This way is faster than the 'm times of nth_element', intuitively.
But the rigorous time complexity is quite difficult to prove.
Notice that b is arranged in a way so that most of sub-arrays of a is not encountered.
I roughly guess it O(n + m * log(n)).