BledDest's blog

By BledDest, 17 months ago, translation, In English,

1000A - Codehorses T-shirts

Editorial
Solution

1000B - Light It Up

Editorial
Solution

1000C - Covered Points Count

Editorial
Solution

1000D - Yet Another Problem On a Subsequence

Editorial
Solution

1000E - We Need More Bosses

Editorial
Solution

1000F - One Occurrence

Editorial
Solution with persistent segment tree
Solution with persistent segment tree (a bit unreadable but runs faster)
Solution with standard segment tree
Mo-based solution

1000G - Two-Paths

Editorial
Solution
 
 
 
 
  • Vote: I like it
  • +53
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can F be solved with a mergesort tree? ( By keeping all the elements which occur once in the nodes, where each node is a sorted vector. Also, merging is easy. )

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is merging easy? Sounds like at least O(n) if it's two pointers. Let the array be and all the queries are [1, n - 1]. How can you merge nodes fast enough?

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I used merge sort tree keeping for each element the range in which it's not repeated : My submission

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I like the fact that you have given different approaches for solving F. Thanks.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain C.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    he is thinking in terms of path compression if some x in [li,ri] keep coming numerous times or some x always remains outside most of the time from many [li,ri]queries then there is no point in keeping its count directly so we keep (li,1) and (ri+1,-1) seperately,a relative positions.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are given n line segments with their starting and ending points. Instead of storing all the points that these line segments, you only use the starting and ending points. So you store li and ri + 1 in a vector 'cval'. Then you sort and store only the unique elements in the vector. For each line segment in the input, you obtain the location of its starting and ending point in 'cval'. Now at the starting point you increase the count of line segments in the array 'cnt' and in the ending point you decrease. Now by obtaining the prefix sums of the values in 'cnt'. At 'cnt[i — 1]' you obtain the number of lines passing through the location i and i — 1 in 'cval'. The difference between cval[i] and cval[i — 1] gives you the number of points and cnt[i — 1] gives you the number of line segemnts passing through these points. By maintaining an array 'ans', we store the number of points with i line segments passing through them.

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

In B that's enough to check a_i + 1 only

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

    You don't right.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why not?

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

      hmm

      Am I wrong in the situaton when there are two adjacent points?

      I didn't think about it because my solution had AC

      • »
        »
        »
        »
        17 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        Could you give a case please. Because if there are only 2 points the solution would be put nothing

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

          No, I meant another thing. It's correct that making a point in a_i-1 and a_i+1 would give the same result. But sometimes it's impossible to put a point in a_i+1(like if there are points with coordinates x and x+1)

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

      There are some facts I can't prove because of my bad Englsh)) They are not very hard, but I can try to write proofs for them in Russian if you would want)

      It's enough. If we can put a point in ai + 1 and ai - 1, the result will be the same. So I can be wrong in a situation when we can put a point in ai - 1 but can't in ai + 1. Let's take a look at this. The points must be like ...ai - 1, ai, ai + 1(because we can't make a point at here)... Let's increase i until we find a free ai + 1. What do we get? A sequence of adjacent points. I want to say that the result will be the same if we put a point in the left of this sequence or in the right.

      If we don't find this i, it means there is a sequence with the end at M. in that case I say that the result will be the same if we put a point in the left or don't put at all.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Mo-based solution for problem 1000F - Одно вхождение is getting TLE

At first I try to write a solution with help of Mo-based solution Editorial, but I getting TLE, after getting many TLE I submit the code from Editorial exactly, but this also getting TLE...:(

  • »
    »
    17 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    We never said Mo-based solution from the editorial gets AC. You still need to optimize things here and there.

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      See my submission using Mo's approach 39747523

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

        At last I get AC with a lot of change, but using Mo's approach. Here it is 39751860

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

          i have a question with Mo's algorithm

          why use this cmp could get AC

          bool cmp(const Query &x, const Query &y){
          	if(x.l/b == y.l/b) return (((x.l/b)&1)?x.r<y.r:x.r>y.r);
          	else return (x.l/b<y.l/b);
          }
          

          other cmp will get TLE

»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone explain normal segment tree approach for 1000F - Одно вхождение ?

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What will happen in E if the graph is complete graph? there won't be any bridge. so what will be the answer?

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

The problem F is very similar to this problem from BZOJ.

Sorry for my poor English.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone elaborate 1000D.

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

    dp[i] is the number of good sequences on the suffix from the i-th element.
    Then and dp[n + 1] = 1

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      please explain that logic with an appropriate example ...it'll be a great help :)

    • »
      »
      »
      17 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      why are we multiplying with dp[j+1] int the above formula.

      • »
        »
        »
        »
        17 months ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        We can choose sequense of length a[i] whith start from i and finish to j ways. After it you solve this problem on the suffix from j + 1 for other way of binom.

»
17 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Mo-based solution of Problem F doesn't get AC.

  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for information! It is being discussed 3 comments higher.

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain problem B a bit more? I didn't understand what he's trying to say.

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

Is it possible to use F's solution to query element that occurs exactly t times on a segment?

I think that in this case we would go with persistent ST from right to left (instead of left->right as in editorial). Suppose we are making a version that corresponds to l'th element of an array. We could precompute indices of occurrence of every array element. Suppose array[l] has more or equal than t - 1 occurrences after l: in this case we should update index of t - 1'th position with an index of t'th one or if such doesn't exist. So, the version l now contains t + 1'th occurrences of t'th elements. Initial version is initialized with negative infinities.

Now, the query [l, r] is the range maximum query [l, r] on l'th version.

As in editorial one needs to unset t + 1'th position assigning negative infinity to it.

I also realized that we could build the tree from left to right and do range minimum queries just as in editorial.

Please, tell me if there is an apparent flaw in this solution.

»
17 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Anyone please explain the solution of Problem 1000F with standard segment tree

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do we need to 'keep only the unique values' in the solution for problem C? I got AC with this and it was pretty straightforward.

»
17 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I got it :) sorry for that comment

»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

We can solve G online with same approach from editorial. Let f(2^i, u) is maximal profit of 2-path from u to 2^i th ancestor of u. f can easily calculated using d' and dp in editorial. Then, we can solve query (u, v) by binary jump on tree (similar to finding LCA).

Code: 39743132

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What does this line mean in solution of B?

int tp = (i & 1) ^ 1;
  • »
    »
    17 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    (1&i) corresponds to 1 or 0 depends whether i is odd or even and xoring with 1 inverses the bit. That means if i is odd, i&1 will 1
    and 1^0 will 0 and if i is even (i&1)^1 will 1
    therefore if i is odd tp will have 0 and if even tp will have 1

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

int tp = (i & 1) ^ 1; meaning in B solution code??Can anyone explain

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone suggest a good resource for understanding and implementing bridges in a graph ?

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this some kind of hashing of edges? y = A[h] ^ B[h] ^ x; in Farhod_Farmon's solution for 1000G.

»
17 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

There's another way to do problem D that might make the code simplier. Maintain a dp[][] where the first dimension is the index you are at and the second dimension is the number of integers you have to choose to include before you can open another good sequence.

dp[i][k] is simply the sum of:

  1. dp[i — 1][k] (you didn't chose the current index to be included in the subsequence)
  2. dp[i — 1][k + 1] (you chose the current index to be included in the subsequence)
  3. dp[i — 1][0] if arr[i] = k and k isn't 0 (you open a new good sequence)

At the beginning, dp[0][0] = 1. At the end, the answer is dp[n][0] — 1 (because empty subsequence isn't allowed)

This is the code:

http://codeforces.com/contest/1000/submission/39787639

Opps and forget my dfs function it's not part of the solution.

»
17 months ago, # |
  Vote: I like it -8 Vote: I do not like it
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

We don't necessarily have to answer the queries offline in 1000G.

»
17 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Another cool dp for G: You can use the dp i -> i, and another one called "dpBestToRoot" which saves the best path to root (which is basically the best detour downward + the bestPathToRoot of your parent + the weight between you and your parent — your part in the detour of your parent).

Now you just do dpBestToRoot[u]+dpBestToRoot[v]-2*dpBestToRoot[lca]+dp[lca]. (http://codeforces.com/contest/1000/submission/39811424)

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

I think more straightforward solution for G is to count dpv than build heavy light decomposition with prefix sums of ways where value for each node would be dpv - ev, u - max(dpu - 2 * ev, u) where v is node and u is child of v that lying on the same way(you know this ways in HLD) 39742958

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In fact, problem C can be solved with O(n) complexity,I think :P

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In solution B , what we are actually doing in this step?

for(int i = int(a.size()) - 2; i >= 0; i--) {
    f[0][i] = f[1][i + 1];
    f[1][i] = (a[i + 1] - a[i]) + f[0][i + 1];
	}
»
16 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Anyone Plz HELP me for 1000C — Covered Points Count I am implementing the same logic as describes above but getting WA for Test Case 4 For Points Covered by 1 Segment. My Code — 39936831 THANKS IN ADVANCE

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In G, since wi > 0, does it matter if we remove the "twice" constraint in the statement?

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys,

I was looking at A and wondering if we could read in the strings of the old and new shirt sizes, store them in different vectors, use algorithm sort and then go through everyone of them to compare if they are the same. Given all the constraints, it looks like this should work. However, I must be missing something because it failed the submission. 40068499

Can anyone point out what I'm missing out on?

Thanks!

  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I found the reason on the main contest page. Thanks guys!