awoo's blog

By awoo, history, 11 days ago, translation, In English

1792A - GamingForces

Idea: BledDest

Tutorial
Solution (Neon)

1792B - Stand-up Comedian

Idea: BledDest

Tutorial
Solution (awoo)

1792C - Min Max Sort

Idea: BledDest

Tutorial
Solution (Neon)

1792D - Fixed Prefix Permutations

Idea: BledDest

Tutorial
Solution (awoo)

1792E - Divisors and Table

Idea: adedalic

Tutorial
Solution (adedalic)

1792F1 - Graph Coloring (easy version)

Idea: BledDest

Tutorial
Solution (BledDest)

1792F2 - Graph Coloring (hard version)

Idea: BledDest

Tutorial
Solution (BledDest)
 
 
 
 
  • Vote: I like it
  • +114
  • Vote: I do not like it

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

slow tutorial :)

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Isn't it possible to have an O(n) solution for problem C (Min Max Sort)?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    yeah, there's an easy $$$O(n)$$$ solution for problem C, involving using the array $$$pos[i]$$$, to get the position of index $$$i$$$ in the permutation, then start at the middle value and finding the $$$LIS$$$ to both side. My submission: 190340250

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    maybe you read only the last line.

    read the third last line.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks Man Searching for long time

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A, why the answer is n — cnt1 / 2?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basically, we are assuming that it will take n spell casts. for n=10 and cnt1=2 so initially it was taking 10 spell casts but because of cnt1=2 it will take 10-1=9 spell casts. 8 of second type and 1 of first type.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here, the first operation only makes sense when we have 1 as the health, in all other cases we will try to use the second operation . Try to do rough work, you will get a fair idea.Now by using the first operation, we will try to eliminate all pairs of 1. hence, number of operations = cnt1 / 2.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody explain how to come up with the equation in problem B.

  • »
    »
    11 days ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    Here, the Optimal strategy to solve the problem is by first saying all the jokes that both Alice and bob likes. (type 1 jokes) then by saying jokes alternately that (Alice likes,bob doesn't) and vice versa.

    Equation: a1 + min(a2,a3) x 2
    

    Final strategy is to say remaining jokes : first by saying remaining type 2, type 3 jokes and then by saying the jokes that both doesn't like (Type 4). this should be compared with the points that he already acquired hence a1 is taken. We take a1 + 1 as the judges goes when points become negative. Hence we add 1 to make it -1. Finally, We take the minimum of both these values to form the final equation.

    Equation: a1 + min(a2,a3).2 + min(a1 + 1,abs(a2 - a3) + a4)
    
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve q3 with binary search approach ? And what is the logic behind it.

  • »
    »
    5 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I used binary search. Here was my logic:

    I noticed that the last operation has to be x = 1, and y = n. You have to swap those two, because otherwise another two numbers will be on the outside. We can extend that logic further to say that the last operation has to be (1, n), the second to last has to be (2, n — 1) and so on. Therefore, the maximum number of operations is n / 2, and we can see what the lowest value k is such that if you do the operation on pairs (1, n), (2, n — 1), ... (k, n — k + 1) is sorted.

    Here is the submission: https://codeforces.com/contest/1792/submission/191351639

»
11 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Does anyone have an idea on proving the efficiency of bisearch-on-divisors approach for prob. E? Never expected it will be this fast = =

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain what is the meaning of run binary search on k in problem C tutorial?

»
10 days ago, # |
Rev. 2   Vote: I like it +62 Vote: I do not like it

For whatever it's worth, here's my $$$O(n \log n)$$$ solution for problem F.

First, we notice that the property for the set $$$S$$$ is the same as having a one-colored cut in $$$S$$$ (in other words, the set of vertices can be split into $$$S_1$$$ and $$$S_2$$$ so that all edges between $$$S_1$$$ and $$$S_2$$$ have the same color). The only issue is that a given set $$$S$$$ can possibly be split into $$$S_1$$$ and $$$S_2$$$ in several ways. So I introduce $$$f(n)$$$ to be equal to the number of graphs on $$$n$$$ vertices where the global cut is blue. Then the answer is $$$2 f(n) - 2$$$, since the global cut may be red, but $$$2$$$ extra cases arise when all edges have the same color.

To find $$$f(n)$$$ we need to partition the set of $$$n$$$ vertices into $$$k \geq 2$$$ subsets so that vertices from different subsets are connected by blue edges, but the subsets themselves obey the rules recursively (they have global cuts of red edges). Since $$$f_{\text{red}} = f_{\text{blue}}$$$, we have

$$$ f(n) = \sum\limits_{k \geq 2}~ \sum\limits_{a_1 + \ldots + a_k = n} C(a_1, \ldots, a_k) \cdot f(a_1) \cdot \ldots \cdot f(a_k),$$$

where $$$C(a_1, \ldots, a_k)$$$ roughly means the number of ways to choose subsets of sizes $$$a_1, \ldots, a_k$$$ from a set of size $$$n = a_1 + \ldots + a_k$$$. If $$$b_1$$$ occurs $$$c_1$$$ times, $$$\ldots$$$, $$$b_m$$$ occurs $$$c_m$$$ times within the multiset $$${ a_1, \ldots, a_k}$$$, then

$$$C(a_1, \ldots, a_k) = \frac{n!}{a_1! \cdot \ldots \cdot a_k! \cdot c_1! \cdot \ldots \cdot c_m!}.$$$

Define $h(n) = \frac{f(n)}{n!}.$ The base values are $$$h(0) = 0, h(1) = 1$$$. Via $$$H(x)$$$ we denote the generating function of $$$h$$$: $$$H(x) = h(0) + h(1) \cdot x + h(2) \cdot x^2 + \ldots$$$. After a careful examination (I don't know how to prove rigorously it though) we obtain

$$$ e^{H(x)} = 2H(x) + 1 - x.$$$

Everything else is the standard approach of how to solve these recurrences: if we know $$$H(x) \bmod{x^{m}}$$$, then from the equality above we can obtain $$$H(x) \bmod{x^{2m}}$$$. Underneath we need FFT (NTT) and an exponential generating function. Each step from $$$m$$$ to $$$2m$$$ takes $$$O(m \log m)$$$ time, so the overall complexity if $$$O(n \log n)$$$.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't get why we have to make sure that no set of vertices is connected by both colors in F1. Doesn't the lemma proved it impossible to connect a set of vertices with both colors?

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The lemma proves the other thing: it is impossible to have a set of vertices which is neither blue-connected nor red-connected.

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I made an oversight while reading the lemma.

»
10 days ago, # |
  Vote: I like it +10 Vote: I do not like it

A-F1 video editorial for Chinese:

BiliBili

»
10 days ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

In fact, we can calculate the convolution-like sequences (such as those in problem F) in $$$O(n \log^2 n)$$$ or $$$O(n \log^2 n / \log \log n)$$$ or even faster. One can find the approach from Elegia's report. The implementations usually has lower constant factor in time than those of the Newton iteration (if exist).

Here is my implementation, which imitates Elegia's implementations for other problems.

(but it's just as fast as a brute force lol)

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you have this report as a PDF?

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +24 Vote: I do not like it
      • »
        »
        »
        »
        10 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you know how to find ref. [5] (罗煜翔。(2020)。浅谈 Nimber 和多项式算法。IOI2020 中国国家集训队论⽂集。) ? I wanna see how to do semi-relaxed multiplication in $$$ \frac{n\log ^2 n}{\log \log n} $$$(if that's what it says). And what nimbers have to do with it xd.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Let's discuss about it here, actually in that report, most contents are just putting the general algorithm into the nimber framework. Nimber does not play an important role in the relaxed convolution.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

"The array may large" in E made me realise how I don't trust my gut feeling at all.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Where does the log(divs(m)) of the complexity in question E come from Isn't it only need O(divs(m)⋅z(m)) to calculate the dp array?

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

can somebody explain why in D if we use lower_bound ans EITHER result or the previous one? why not just result? thanks in advance

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It depends on the value immediately after the longest common prefix. While searching for $$$p$$$, you find some inverse $$$q_1, q_2, \dots, q_m$$$ that starts with $$$p_1, p_2, \dots, p_k$$$ for some $$$k$$$. The next value is different. If $$$q_{k+1} > p_{k+1}$$$, then lower_bound will point at $$$q$$$ (or one of inverses with such prefix if there are multiple). However, if $$$q_{k+1} < p_{k+1}$$$, then $$$q$$$ will be smaller than $$$p$$$, and lower_bound will jump over it. The next inverse has to be greater than $$$p$$$, so you only have to look one step behind.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, I thought while $$$n=5\times 10^4$$$, the number of subsets of $$$\{1,...,m\}$$$ is $$$10^3$$$.

So I constructed a map $$$M$$$ mapping each subset $$$L\subset \{1,...,m\}$$$ to $$$\{(a_i[p_1], ..., a_i[p_t])\ |\ i\in \{1,...,n\},\ \{p_1<...<p_t\}=L\}$$$. Then I iterated over every permutation and every $$$k$$$ to see whether the corresponding $$$k$$$ locations have the desired values.

For constructing $$$M$$$, it seemed that I can iterate over all subsets of $$$\{1,...,m\}$$$ and for each subset iterate over all permutations. This 2-layered loop is about $$$5\times 10^7$$$. But my actual implementation requires $$$O(2^m\times n\times m\times \log(n))\approx 8\times 10^9$$$ and thus got TLE. Not sure whether this is optimizable.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have some questions in problem F1

  1. Why iterate k — the number of vertices whick are in the same 'red' component as 1 but not iterate the blue component, is this because you are counting the blue component?

  2. What about the edges between vertices in the same componet as 1 and the rest vertices, are they must be the same color? how to proof?

Hope someone can help me, thx a lot

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    1. We are considering the case when the whole graph is blue-connected, so there's no need to iterate on the blue component. The case when the graph is red-connected is symmetric to it.
    2. It's easy to see that all these edges are blue, since any red edge between any vertex from the "red" component of vertex 1 and any vertex outside this component means that we haven't picked the whole component
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a test case on which my code is failing? I couldn't view the 156th item of 2nd test case. Is there any way to view it?

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

    Click the "Click to see detail" button in the bottom of the page to see the detailed test cases

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

has anyone solved problem C with binary search ?

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

NEED PROVEMENT FOR PROBLEM F

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

F1's solution is flawed I guess. Consider case with n=3, when A1=B1=1, A2=2, B2=1, you get B3=4 which is incorrect.

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

    So what's wrong with the $$$B_3=4$$$?

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A3 which is the answer for n=3 is 6 in the pretest case, but surely 6 is not 4 * 2 :P

      • »
        »
        »
        »
        4 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, maybe the tutorial forget something or i just didn't see.

        But don't forget the limitation 1 and 2.

        The $$$A_3=8$$$ contains the case that all blue and all red.

        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I noticed that too. I'm just saying that define "An" as "the answer for n" is not very strict and could lead to someone's misunderstanding(like me)

        • »
          »
          »
          »
          »
          4 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          另外看兄弟id八成也是国人,直接说汉语就好了吧:)

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

    Sorry, I initially stated the problem without the constraints "at least one edge should be red" and "at least one edge should be blue". I wrote the editorial for that version, but then decided to introduce these constraints. So, the actual answer is $$$A_n-2$$$ since we need to discard the case "all edges are red" and the case "all edges are blue".