gen's blog

Codeforces Round #599 Editorial
By gen, history, 5 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +62
  • Vote: I do not like it

Comments Comments (97)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +126 Vote: I do not like it

Isn't div1 B a weaker version of 920E - Связные компоненты??

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

    This one has a more elaborate editorial :)

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

    190E
    653E (a little longer)
    920E
    1242B

    all about components of complement graph :)

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

      Thank you for sharing...Solved.

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

      Thanking you for encouraging you to comment such things more often, it is really helpful.

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

    Not easier but actually the same. 101945655 Here is the submission for Connected Components. And 101944622 is for 0-1 MST.

    Only the output format is different.

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

It seems that the data is so weak.

I used std::map<int,int> in Div1. C but it passed the system test.

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

    I used int at first too, and I realized the error after the first submission.

    But this doesn't seem matter according to the data.

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

I suspect 7500 in div1 C editorial is a typo of 75000.

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

    Also, $$$\varnothing$$$ has been rendered wrongly as $$$varnothing$$$.

    gen please look into this and the above comment.

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

Hi, my implementation for Div2 B2 is O(N^2).

This is how my algorithm works: If s[i] != t[i], I used an inner loop (with index j=i+1) to find s[i] == s[j] or s[i] == s[j].

However, the editorial states that the complexity is O(N). Is my analysis for the complexity wrong? Or is there a more efficient way of implementation?

Thanks!

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

    I suggest you simulation it by vector,vec[i] present the position occurence in s or t, which complexity may be O(n),but n<=50,So,there is unnecessary。

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

    No. complexity is O(n) for div2 B2. here link to O(n) solution https://mirror.codeforces.com/contest/1243/submission/64410431

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

      Your code also seems to have O(n^2) complexity. Is there anything that I am missing?

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

      I think your solution is $$$O(n^2)$$$

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

      i have tried to write the code in o(nlogn) using set hovever if you use unordered set in my code the complexity would become o(n). https://mirror.codeforces.com/contest/1243/submission/64422994

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

        In my experience with Java/Kotlin it's not good to use unordered HashSets if you want to repeatedly get a single element from them (e.g. using Kotlin's extension .first() function; presumably the most idiomatic Java equivalent is .iterator().next()) as it potentially might need to step through empty buckets in $$$O(n)$$$ time. (A LinkedHashSet is better for this use case.) I'm unsure if this is true for C++ unordered sets as well, but it probably works in a similar manner

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

      It does not matter if it is O(n^2) or O(n), for a simple reason that n <= 50. However, for purists, let me say it is O(n^2) for sure. You can improve it using unordered_map or any other data structure that does the search operation in linear time. Though, it seems counter-intuitive, it would be easier to implement such a solution. If you do not believe me, let me say, I am reincarnation of Joseph Stalin and I would send you to labor camps.

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

The system test for 1C is too weak.

sys. hacked lots of submissions after contest.

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

    I hacked them by my hand :(

    It spent me an hour.

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

      Just imagine how many hack you can do in 3.5 years

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

I think the editorial of div 2 B2 is incomplete.

  1. There is no explanation on how to efficiently find characters in the strings. My implementation (64439067) used TreeSets, which pushes the complexity up to $$$O(n \log n)$$$. I think it can be done in $$$O(n)$$$ using arrays/vectors and pointers but the implementation is non-trivial. (Edit: Apparently it doesn't matter too much though cause $$$n \leq 50$$$)

Disproved; see below
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    no its complete. if total number of each character is even you can always find a solution within 2*n moves.check this https://mirror.codeforces.com/contest/1243/submission/64410431

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

      I give up. I'm not sure how leaving out the parity check can cause a false negative. Unless there's a difference in implementation that someone can enlighten me to.

      edit: Found my error. Apparently "find $$$t_j = t_i$$$ else find $$$s_j = t_i$$$" fails, but "find $$$s_j = s_i$$$ else find $$$s_j = t_i$$$" passes.

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

    Can you tell me its sufficiency? The above seems to prove only the necessity. Thank you！

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

      Instead of an explicit parity check, I simply try to make $$$s_i = t_i$$$ for each $$$i$$$. If the algorithm fails, it means it can't find a match for $$$t_i$$$, which only can happen if $$$cnt(t_i)$$$ is odd.

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

Can someone please explain the time complexity in Div2C Editorial

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

    You try all the numbers smaller than sqrt(n) to see if it's a divisor of n, so the complexity if O(sqrt(n)).

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

Some more duplicate problems on div1B.

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

    It is not similar to this problem, during contest i also thought it is similar to this problem but after making required change it kept giving me wrong answer on pretest then again after some modification i passed pretest but it fail on main test.

    And the reason behind that in Div1B is we can have the edge in its own vertex set as well that differ the complete approach. In 1228-D it is strict that we won't have edge in own vertex set but that is not the case here

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

for problem C in div1，15·5000=7500???

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

Can someone please explain the case of n=pq for 1242A Tile Painting

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

Can people who submitted "gcd of all divisors except 1" in div.2 C describe their way of thinking? I know that it works, you can prove it with editorial's proof, but to me it makes no sense and seems like a random guess.

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

    Think about it in terms of Bezout's Identity.

    Let us take two integers $$$x$$$ and $$$y$$$.

    Suppose, $$$n = Ax + By$$$

    Let $$$g = \gcd(x, y)$$$

    $$$n = Agx' + Bgy' = g(Ax' + By')$$$

    This means that we can write $$$n$$$ as a linear combination of $$$x$$$ and $$$y$$$ if $$$g$$$ divides $$$n$$$.

    Conversely, if we find a combination such that $$$Ax + By = g$$$, we can reach any multiple of $$$g$$$ too.

    Suppose, we want to reach $$$kg$$$, then $$$(kA)x + (kB)y = kg$$$

    Now, let us take $$$N = p_1 ^{a_1} p_2^{a_2} ... p_k^{a_k}$$$

    Now, gcd of any two primes is $$$1$$$. This means that if there are at least $$$2$$$ primes, we can reach all the integers as $$$A p_1 + B p_2$$$

    I suspect that this was the idea behind writing gcd of all the divisors. Suppose $$$g$$$ is the gcd, then we can paint $$$[1, g]$$$ with different colours but after that we cannot use any more colours.

    The editorial and the intended solution went one step further and noticed that we do not really need to know the GCD of all the divisors since $$$2$$$ primes are always coprime to each other and if there is only $$$1$$$ prime, then that prime number is the gcd.

    Let us generalise the question. Suppose we were given a set $$$ S = (a_1, a_2, \dots , a_n)$$$ and told that if $$$(i - j) \in S$$$, then $$$i$$$ and $$$j$$$ have to be the same colour, the solution is the gcd of $$$S$$$. We can reach any integer that is a multiple of the gcd of $$$S$$$. So we can only choose the colours in $$$[1, g]$$$. Whenever we colour $$$x$$$, the colour of $$$x + g$$$ is decided.

    However, this question has an additional step that $$$S$$$ is only the divisors of an integer so this allows us to make it sharper. :)

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

      Thanks a lot, your answer was helpful for me!

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

      My solution was to find the gcd too, but it only made intuitive sense during the contest so thanks for this proof!

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

DIV 2B. if both strings are already same then answer is yes.

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

I had a different, possibly simpler solution to div1B.

All nodes with more than $$$\frac{n}{2}$$$ edges of zero cost are in the same zero-cost component. Loop all nodes with more than n/2 edges with connected to each other, so connect them in the DSU in O(n log n). Loop all nodes with at least $$$\frac{n}{2}$$$ edges with cost 1, and connect all nodes they have zero-cost edges to in total time O(m log n). Total complexity is O((m + n) log n).

Code: 64382712 (I use $$$\frac{n}{2} - 10$$$ here because I didn't want to think about the constants)

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

    If you use DSU with path compression, the $$$O(\log n)$$$ factor can be reduced to $$$O(\alpha(n))$$$, where $$$\alpha$$$ is the inverse Ackermann function, a function that grows so slowly that it can be considered $$$O(1)$$$ for any data set that can physically fit in this universe. But in my experience uploading DSU solutions with/without path compression, I can't seem to see much appreciable difference.

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

    This was really nice observation and pretty easy to implement as well

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

    Thanks Mango , your codes are the best. :)

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

Div 1 B can be solved using Prim's also.

I keep a set of pairs,which are disconnected vertices , first entry will be number of edges from connected part to the vertex and select will be vertex number. and i keep a map from second entry to first entry of set.

Every time fetch the first element in set, if its degree equal no of connected nodes, increment answer by 1.then update map and set with edges of this node.

Here is my submission : https://mirror.codeforces.com/contest/1242/submission/64390575

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

Could you give me a intuition explanation for Chinese Remainder Theorem?

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

Well, I did the same thing, except that I determined, for every vertex i, any other vertex j that:

a. i isn't connected to j with a 1-weight edge,

b. i and j lie in different connected components.

I do that by initializing j to 0 and looping over the vertices incident to the current i, incrementing j if necessary.

However, this gives WA 13... :(

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

In div2 C, my implementation is: if n==1, ans is 1. Otherwise get the divisors of n. Get gcd of all the divisors except 1. Answer is the gcd. Here is my JAVA code: 64462563

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

    Instead of divisors can find prime factors. Since gcd of prime factors is always 1, thus if there are more than 1 prime factor then answer will be 1 and if there is only 1 prime factor then answer will be that prime factor.

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

My solution for div1B:

Let G1 be the graph where only edges with cost 1 are considered. Pick any vertex (S) with minimum degree.

Let X be the set of vertices which have 0 cost edge with S and Y be the set of vertices which has 1 cost edge with S. Note that the size(Y) <= m/n.

Build a new graph as follows:

  1. For each vertex in X add an edge to S (O(n))

  2. For each vertex in Y add an edge to all its 0 cost neighbours (O((m/n)*n))

Now, the answer is Number of connected components of this new graph -1.

My Submission

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

    Got you! Did you find this somewhere?

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

      Let n be the number of vertices, m be the number of edges

      sum(degree) = 2*m

      n*min_degree <= 2*m

      min_degree <= 2*m/n

      size(Y) = min_degree <= 2*m/n

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

      I dint find this anywhere. During the contest I was trying to find an equivalent sparse graph which would have the same number of connected components as the graph formed by 0 cost edges and eventually found this.

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

    Proof of this please: "Now, the answer is Number of connected components of this new graph -1."

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

      The "new graph" is equivalent to the graph mentioned in the editorial in terms of the number of connected components, just that the connected component which contains vertices in X is sparse.

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

    I read your code and understood it. But can you explain the complexity since the worst time complexity seems O(n^2). Also why to find the vertex with min degree, I could just merge(union) all the vertex which have 0 weight edge between them in O(n^2)?

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

      In the problem we need to find minimum degree vertex.As if you take any vertex randomly , then it might have degree about 10^5.(eg. In worst case, all 99999 vertices might be connected to a single vertex and if you select that vertex then it would have o(99999) * o(100000)[o(100000) is for zero weight components traverse]. But if you select minimum degree vertex then in worst case, minimum degree would be 10^(2.5) because in worst case a vertex can be connected to every other vertex which can only happen if n<=10(2.5) then it would have about 10^5 edges. Therefore, minimum degree must be smaller than equal to 10^(2.5). Hope you understood why are we minimum degree vertex :)

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

    Why to take minimum? Edit: I figured it out.

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

    In your code, you find value of cc before building the new graph and if this cc is greater than 1, "0" is printed, can u explain what's the reason behind finding cc here?

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

      If the no of components only considering the 1 weight edges are >1 (let's say 2) then we can connect the vertices of 1st component with that of 2nd component by using only 0 weight edges, thus making a single component. The same idea can be extended for more than 2 components.

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

Can anybody explain Div2D in a more intuitive way? Like what is the key observation over here? With an example? I have read some of the comments explaining the solution but not how they got there.

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

    I solved it after reading the editorial and implemented each step as it is written, https://mirror.codeforces.com/contest/1242/submission/65618215.

    Key observation: 1. If number of 0-weight edges are less than<1e5. Then you would have made DSU and answer would #connected_components -1. (This is relatively simple and almost everyone would've got it. ). Tough part was total 0-weight edges could n^2 — m (~10^10). You need to build the same DSU in some other way.

    Implementation: 

    map<int,int> m;
for v in 1..n:
  for(int u: adj[v])
     m[root(u)]++;

    This map m will hold number of edges from component of u to v.

    for each component: 
    if (sz[component] > map[compnonent]) 
        unite(component, v);

    Catch is to how to iterate over all components?

    Wrong/sub-optimal Approaches:

    1. Iterate only for entries of map. This is wrong.
    1. Iterate over 1..v-1. This will TLE.

    Right one

    Mainatain a set for that. After the vth iteration, push v in it. All those components which got merged, remove them..

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

    101944622 This is the code implemented according to the editorial.

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

I solved Div2 D using the approach mentioned in the editorial,solution. However when I applied the same approach to this similar question 190E-Counter Attack, it is giving TLE although the time complexity is still the same,. Any help would be appreciated!

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

I found the typo of editorial of Div1D. It will be fixed soon.

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

    On the editorial says "Every interval has exactly one non-self number", it means that the non-self numbers are periodic $$$($$$if n is non-self the $$$n$$$ + $$$k^{2}$$$ + $$$1$$$ is also non-self $$$)$$$; however, with $$$k$$$ = $$$2$$$, the numbers are $$$3, 9, 13, 18,...$$$ and clearly there is not a period. Thanks in advance.

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

      $$$3$$$ is in first interval $$$[1, 5]$$$, $$$9$$$ is in second interval $$$[6, 10]$$$, $$$13$$$ is in third interval $$$[11, 15]$$$, etc. All non-self numbers can be in each interval without having exactly same period.

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

I solved div1B using the algorithm provided int the editorial. But I still wonder why the complexity is O(nlongn + m), as we iterate every vertice from 1 ~ n and every time we iterate every zero weight component to try to unite them, it seems that the complexity should be n^2. Are there anyone explain it for me? Thanks a lot!

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

    I will try to give you some intuition: Yes, you are right, for every vertex we are going over all the zero-weight-components, and you are right there can be N of them. But the complexity is not N^2, here's why: The number of zero-weight-components you can have at any given time is actually bounded by M/(N — 1), the number of edges. Because in order to leave a vertex unmerged, it needs to have a degree equal to N — 1. In other words, it needs to have an edge between it and every other node. This can happen at most M/(N — 1) times. Since M is actually min(10^5, N*(N — 1)/2), you can see that M/(N — 1) cannot exceed 10^3. And now, every node after that will have all of it's edges with weight 0, because we have already used all our weight 1 edges. So every subsequent node we consider will be merged.

    It's not very rigorous I know but I hope I could provide some intuition

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

      I see, thanks a lot for your explaination!

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

Did anyone solved div2D exactly as explaind in editorial.

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

    I tried to stay as faithful as possible to the explanation in the editorial, you can check my code here: https://mirror.codeforces.com/contest/1243/submission/64548383

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

      Oh... It helped me a lot. Thanks for replying. I was stuck for 1 day.

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

      Sorry to bother you again, but can you tell why i > v[i][j]?

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

        It's just because we want to process the nodes whose label is less than the current one. This is because when we are iterating over node i, the sets for nodes whose index is greater than i have not been created yet, as we are only creating the set after finishing with i.

        You could probably do an implementation where you create all the sets in the beginning, I don't see why it would not work. But as I told you, I tried to stay as close as possible to the editorial and this is what the editorial suggested.

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

          oh, that means if we remove i>v[i][j] , then it would increase time complexity for visiting adjacent vertices by factor of 2, which is sufficient for passing the time limit. [I tried :-)]. Thanks again for help.

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

Could anybody help me with my code of Div1.C? It did output the correct answer when running with the first example input on my own computer, but I don't know why it just printed 0 when submitted.

Here's the local output:

Yes
10 4
5 1
7 2
2 3

Here's the online output:

Yes
10 0
5 0
7 0
2 0

I'm really confused about this. And here's my submission 64595444. Thanks a lot!

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

    Type of a is long long int, that is why your second %d buffer doesn't work. Change a to just int or make %lld for a in your printf.

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

      That's what's the matter! Thank you very much! :)

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

Can someone explain 0-1 MST solution with DSU? I understood the general idea that we should count the number of zero-weight components. The part that I couldn't get starts from "For each of the zero weight components, we count the number of edges from this component to v."

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

I did not understand the editorial for D. I understood the claim but did not quite understand the proof neither how to come up with such claim out of blue. Did anyone come up with the solution in some other way? Or any better explanation?

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

    I also think my sentence is bit messy.

    Suppose you have $$$k^2$$$ self numbers and $$$1$$$ non-self number in $$$k^2+1$$$ size interval. Then each $$$k$$$ numbers of $$$k^2$$$ self numbers will be appended to $$$s$$$ at the same time, and they will generate new $$$k$$$ non-self numbers in total. Each non-self numbers will be included in next interval($$$k \cdot i, k \cdot i + 1, \ldots , k \cdot i + k - 1$$$ th intervals), because each summation will be fit in corresponding interval as I described as formula in editorial.

    Now let's see this formula:

    $$$ \sum_{j=1}^{k} (i \cdot (k^2 + 1) + t \cdot k + j) + offset = (k \cdot i + t) \cdot (k^2 + 1) + \frac{k \cdot (k+1)}{2} - t + offset $$$

    $$$k$$$ numbers of $$$t$$$-th subinterval(size $$$k$$$) of $$$i$$$-th subinterval(size $$$k^2 + 1$$$) will be $$$(i \cdot (k^2 + 1) + t \cdot k + j) + r[j]$$$ for $$$j = 1, 2, \ldots, k$$$ where $$$r[j]$$$ is $$$0$$$ or $$$1$$$, because if non-self number is inserted at the left(or inside) of the $$$t$$$-th subinterval, then part(or whole) of the subinterval will be shifted, so that $$$r[j]$$$ is offset consideration, and $$$\sum_{j} r[j] = offset$$$.

    Since $$$0 \le t \lt k$$$ and $$$0 \le offset \le k$$$, this is always true: $$$1 \le \frac{k \cdot (k+1)}{2} - t + offset \le k^2 + 1$$$. This means generated sum of $$$t$$$-th subinterval will always be in $$$(k \cdot i + t)$$$-th interval. ($$$i$$$-th interval represents $$$[i \cdot (k^2+1) + 1, (i+1) \cdot (k^2+1)]$$$.)

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

I can not understand the solution of div2E-div1C until i read the problem statement again and realized that i did not read statement carefully before. I did not notice on the important condition "All of the integers are distinct".

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

for 1242B if we find the number of connected components of the given 1 weighted graph complement the problem is solved!

we can find the vertex v with minimum degree of the given 1 weighted graph.

Merge all vertices except ones adjacent to v into one component and make the root of them to v in the dsu.

the number of remaining vertices (adjacent to the v) can't be large!!

Let degree of v be d then d<n & n*d<=2m so d<=sqrt(m).

Now brute force for all zero edges between neighborhoods of v and the remaining vertices and complete the dsu.

complexity is o(n*sqrt(m)).

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

Div2E/Div1C: can we get more details about the graph we should construct?

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

Can someone please help me out in finding the reason for getting TLE for problem 1243D - 0-1 MST ??Here's my submission 64726030 ...According to me it's O(m)...

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

hello, could someone help me with the explanation of the problem D div2? Please.

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

In problem div2D ,

For each of the zero weight components, we count the number of edges from this component to v. If the number of such edges is less than the size of the component of u

Using DSU , how are we going to count the number of edges for each component, can someone help please?

Thanks in advance!

Edit : Found the code above. Sorry for the trouble!

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

can someone expalin me how answer is 1 for n = 6 in tile painting question??

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

    For 6 divisor is 2,3. then 1 3 5 (2 difference) is same color and 1 4 (3 difference) is same color.. 2 4 6 (2 difference) is same color.. All are included.. so answer 1

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

can anyone please tell me why This submission is getting accepted while This is not? Thanks in advance

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

A simple solution to 1242A Tile painting
https://mirror.codeforces.com/contest/1242/submission/86986617

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

0-1 MST ( Div2 D ) , Prim's Algorithm Solution Without DSU
Time Complexity: O( (n * log n) + m )

Commented Code
→ Reply