BledDest's blog

By BledDest, 2 years 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
Tutorial of W7 main contest
 
 
 
 
  • Vote: I like it
  • +53
  • Vote: I do not like it

»
2 years 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. )

  • »
    »
    2 years 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?

  • »
    »
    2 years 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

»
2 years 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.

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

can anyone explain C.

  • »
    »
    2 years 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.

  • »
    »
    2 years 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.

»
2 years 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

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

    You don't right.

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

      Why not?

    • »
      »
      »
      2 years 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

      • »
        »
        »
        »
        2 years 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

        • »
          »
          »
          »
          »
          2 years 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)

    • »
      »
      »
      2 years 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.

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

Mo-based solution for problem 1000F - One Occurrence 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...:(

  • »
    »
    2 years 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.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone explain normal segment tree approach for 1000F - One Occurrence ?

»
2 years 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?

»
2 years 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.

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

Can anyone elaborate 1000D.

  • »
    »
    2 years 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

    • »
      »
      »
      2 years 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 :)

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

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

      • »
        »
        »
        »
        2 years 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.

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

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

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

»
2 years 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.

»
2 years 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.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
2 years 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.

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

I got it :) sorry for that comment

»
2 years 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

»
2 years 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;
  • »
    »
    2 years 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

»
2 years 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

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

    tp is 1 if i is even and is 0 otherwise

»
2 years 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 ?

»
2 years 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.

»
2 years 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.

»
2 years ago, # |
  Vote: I like it -8 Vote: I do not like it
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 years 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)

»
2 years 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

»
2 years 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

»
2 years 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];
	}
»
2 years 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

»
2 years 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?

»
2 years 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!

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

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

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

In problem E, what is being asked in the question and why the answer for that is equal to the diameter of the bridge tree instead of the total number of bridges?

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

    I also did not understand at the beginning. In the problem they ask to find two vertex such that the number of bridges between them is maximum The task does not give specific starting and finishing positions, you need to find such that the number of bridges between them is maximum (shortest path)

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

For problem F, I used a mergesort tree to get online queries in $$$O(\log^2 n)$$$ (barely snuck under the time limit).

Let each element in the array be a triple $$$(l, r, x)$$$, where $$$x$$$ is the value of that element, $$$l$$$ is the index of the previous occurrence of value $$$x$$$ in the array $$$+1$$$, and $$$r$$$ is the index of the next occurrence of value $$$x$$$ in the array $$$-1$$$. If there is no next or previous occurrence, then just use $$$+\infty$$$ or $$$-\infty$$$ or something.

Now, to query an interval $$$[a, b]$$$, we would like to know if there exists any triple $$$(l, r, x)$$$ in the array between indices $$$a$$$ and $$$b$$$, such that $$$l\leq a$$$ and $$$r\geq b$$$. If any such triple exists, we return $$$x$$$.

Now, we build a mergesort tree on the triples $$$(l, r, x)$$$ (sorted by $$$l$$$). Each node of the segment tree will store a sorted list of the triples on some interval, as well as a list of pairs $$$(r, x)$$$ which denote prefix maximums in terms of $$$r$$$ (and $$$x$$$ just gets copied over from whichever element had the largest $$$r$$$), on that sorted list.

Next, using normal segment tree tactics, we can make it so that for a query interval $$$[a, b]$$$, we only need to examine $$$O(\log n)$$$ nodes to try and find some valid $$$x$$$. For each node, we binary search the sorted list of triples to get a prefix such that $$$l\leq a$$$, and then take the corresponding $$$(r, x)$$$ at the end of that prefix, which gives us the largest possible $$$r$$$ on that prefix. If $$$r<b$$$, then no valid solution exists, otherwise the $$$x$$$ that we found is valid. Examining one node thus takes $$$O(\log n)$$$ time.

So, we can query an interval $$$[a, b]$$$ in $$$O(\log^2 n)$$$ time. Submission here: 84532864