Блог пользователя awoo

Автор awoo, история, 10 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Educational Codeforces Round 20
  • Проголосовать: нравится
  • +63
  • Проголосовать: не нравится

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +30 Проголосовать: не нравится

for problem D , after an O(N) preprocessing , check(mid) for binary search can be done in N/mid complexity , the worst case would be (N/(N/2)) + (N/(N/4)) + (N/(N/8)) + ... = N/2 + N/4 + N/8 ... = N , so the actual complexity comes out to be O(N) instead of O(NlogN).

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

In problem G... We can use interval tree to maintain the sequence , instead of segmenttree. Each node of the interval tree represents a lazy tag. To modify , we firstly split the sequence and then processes the modification. Note that in one split operation , the numbers of intervals only increases by 2. Thus there is no need to use sparse table... This data structure operates at time Complexity O( n + q( log( k + q ) + log( n ) ) And it costs O( n + k + q ) memory.

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

Silly question! Realised my mistake!

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

Problem A, Python3, TLE #15, 22MBytes. Problem A, the same code, C++ MSVisualStudio2010, AC, 260 ms, 3.6 MBytes.

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

For problem D, how do you decide to choose binary search to compute the minimum width? I do understand the code itself, but still have no idea how to pick binary search for this problem.

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

Can anybody please tell that why in Problem C the GCD of resulting sequence is always a divisor of n?

  • »
    »
    10 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +13 Проголосовать: не нравится

    Let's consider the case when GCD isn't a divisor of n. Let it be some value g. Then resulting sequence looks like x1·g, x2·g, ..., xk·g. Its sum is equal to x1·g + x2·g + ... + xk·g = g·(x1 + x2 + ... + xk). That is divisible by g. The sum is equal to n. Thus n is divisible by g. This lead us to contradiction(? I'm not sure of right word to use).

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

In problem C why we need to check that n — s > (k — 1) * d? also we need to check that gcd(n-s,d)=d right ?

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

In problem C test:#10, n=24, k=2, answer is "8 16". So, the max divisor is 8 ? But 8 is greater than , isn't it a contradiction of the statement in editorial?

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

There's like 'didnt want to tnink at all' solution for G.

We can actually build a valid persistent treap over whole range(N * K) — build a treap over given N elements, make K copies of it, merge them. Congratulations, u now have a valid treap with 10^9 elements in it.

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

Can anyone please further explain the solution to F?

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

    Let's say we have a set S of K elements. The power sets (all possible subsets including null sets is 2^K)

    Now for this problem we are given an array a1, a2, ..., aN and here we have to find subsequences of this array such that all GCD is equal to 1.

    Let's try all g (all possible GCDs) from 100k to 1. ans[g] is how many possible subsets we can make with GCD in this subset is equal to g. Our answer will be in ans[1]

    We now iterate for all possible g, let's denote the number of elements which has GCD equals to g as cnt(g). Then the value of cnt(g) is sum of all numbers of elements which has divisors of g, 2g, 3g, and so on.

    The number of possible subsets with GCD = g is equals to 2^cnt(g) — 1 (since we have to exclude null subset). However for some multiple of g, we have already counted before. That's why by using inclusion-exclusion ans[g] value will be equal to 2^cnt(g) — 1 — ans[2g] — ans[3g] — ...

    To have a better understanding, you can view my solution Submission

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Can someone post good clean solutions for problems A and B in Java? Everything I saw so far was quite tricky and hard to fathom. Thanks in advance!

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

How to solve E in linear time?

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

    Consider the dpi j table from the tutorial. For a given i, all j such that dpi j are true must be in one continuous segment. Therefore, you can do dynamic programming by storing the min and max of this segment for all i instead of storing the boolean for all i by j

    My code (java) might be easier to understand than my explanation: 26787020

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

      Sorry, but I didn't got your explanation, and I got less the Java code. You are saying that for a given i, all the j such that dpi, j are true are contiguous. Let be i = n ; dpi,  - k and dpi, k would be equal to true, and for all j such that  - k < j < k would be equal to false. Am I making any mistake? Thanks in advance for your clarification

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

        In the dp table, think about how any column relates the the column before it. On a 'W', 'L', or 'D', the true values in the later columns are either shifted up, down, or not at all from the previous column. Similarly, a '?' results in union of these three. None of these operations ever split up a segment of true values into two segments.

        You also know that the first column is a single segment of length 1. Therefore, induction tells you every column must be a continuous segment of true values (or all false).

        This poor ascii representation of the third example might help

             4 
             3                                       T
             2                                     T T
             1     T                            T  T T
           j 0  T  T  T                      T     T T
            -1     T  T  T                T          T
            -2        T  T  T          T
            -3           T  T  T     T
            -4              T  T  T
                0  1  2  3  4  5  6  7  8  9 10 11 12 13 ...
                 ?  L  L  L  L  L  W  W  W  W  W  ?  ? 
                                    i
        
  • »
    »
    10 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    I was able to do greedy in O(n) with a stack (Submission).

    From the start, keep a running sum of the score. Treat (W) as +1, (L) as -1, and ignore (D)s and (?)s.

    At any point, if the score becomes k or -k, assign the nearest (?) to a (W) if score=-k, or (L) if score=k. Here, you can keep track of the nearest (?) by using something like a stack.

    Now be careful, after changing you'll have to slide the whole window after that (?). If the shift will make a part of the score still hit k or -k, then output NO. Otherwise, keep going.

    Now once you reach the end, we'll need to make the score k or -k so we simulate both options. Making use of the stack of (?), to target score=k, we assign the last k — score unknowns as (W)s. The remaining (?)s can be (D)s. Similarly, do it for (L) with score — (-k) unknowns. Check if it still satisfies everything, then we can output either working answer (otherwise, output NO).

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Can someone please explain the use of the mobius function for problem F?

»
10 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

In problem C, I could not apprehend, how we reach described solution. And, why does it give us best answer ? Could someone explain me ?

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

    We're trying to maximize a the GCD of a (positive strictly increasing) sequence of length k that sums to n.

    Consider any sequence that has a GCD greater than 1:

    • 2,4,6,8
    • 3,6,12,15
    • 7,21,49

    Note that if a sequence has a GCD > 1, we can factor that number out:

    • 2{1,2,3,4}
    • 3{1,2,4,5}
    • 7{1,3,7}

    Because we can factor this number out, n (the sum of the sequence) must be divisible by the factor.

    Also note that the smallest possible sequence of length k, {1,2,...,k}, sums to k*(k+1)/2.

    We can combine these two observations in the following way.

    • Iterate from 1 to root(n) to find the factors of n.
    • For every factor x, we can consider if it's possible to make a valid sequence of length k where every element is a multiple of x.
    • We know that for this factor, the smallest possible sum is obtained with the sequence x*{1,2,...,k}
    • Therefore, the sequence is possible if and only if x*[k*(k+1)/2] <= n.
    • That's all there is to this problem. Also note that once you find the largest factor that satisfied the above equality, you can stop searching, since any smaller factor will yield a smaller GCD
    • The edge cases where you should return '-1' are where the equality x*[k*(k+1)/2] <= n doesn't apply for even the smallest factor, x=1.

    Below is an example:

    Consider the input "12 3"

    • The factors of 12 are [1,2,3,4,6,12]
    • k*(k+1)/2 = 6
    • We need to find the largest factor of 12, x, such that 6x <= 12
    • x is obviously 2.
    • The answer will be some sequence 2{a,b,c} that sums to 12
    • The answer is therefore "2 4 6"

    I hope that helps!

»
10 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Here is another practice problem to apply the idea from problem F: http://codeforces.me/problemset/problem/439/E. This problem requires the same idea used on problem F plus some knwoledge about stars and bars formula. Hope it can be useful for those who want to become better :)

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

Could you please explain problem G in details. It is pretty hard to understand. And is there any code example? I didn't get how to build the tree, what whould represent sparse table. Please, help me

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

My AC submission for G

WA with a smaller tree

I made a segment tree that is somewhat "persistent" for the initial period, and I thought that the memory complexity should be around O(Qlog(NK)), yet instead I had to allocate much more memory for my solution to pass. Now I wonder if I had a wrong bound or I just underestimated the constant factors. Would anyone mind prove the memory complexity for me?

Many thanks in advance.

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

In problem C, in test case #21, my output sequence gcd is 3 and it's clearly increasing, the checker says my gcd is 1, perhaps I missed something! 26808542, I also submitted a very close version to the editorial binary searching among the divisors of N and it passed! 26809758

So what's the problem?!

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

Can someone provide the proof of the assertion in Problem C ?

The gcd of k positive integers that sum up to n, is always a divisor of n.

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

There's an easier way to solve problem F: https://www.geeksforgeeks.org/count-number-of-subsets-of-a-set-with-gcd-equal-to-a-given-number/

Here's my code using this approach: Code

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

The editorial for C is so unrigorous: how is it written by a red coder is beyond me. God, let me increase my typing speed. Then I will show them what is an actual competitive programmer.

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

The editorial for C is unrigorous: how is it possible for a red coder to write like that is beyond me.

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

Can someone explain the solution to problem F

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

Why does greedy work for D — Magazine Ad? Can anyone provide a full/half proof?

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

    Think of the first line, suppose by using the greedy logic you decide that you can have n words in the first line. Since greedy is taking as many words as possible, no other solution can have more than n words in the first line. Also, by taking more words, you're leaving fewer words for the remaining k-1 lines. So if a solution is possible by taking more than n words in line 1, it should be possible by taking exactly n also.

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

The linear solution of E,based on greddy. https://codeforces.me/contest/803/submission/156600793

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

The linear solution of problem E,based on greedy. https://codeforces.me/contest/803/submission/156600793