PikMike's blog

By PikMike, history, 3 weeks ago, translation, In English,

1156A - Inscribed Figures

Tutorial
Solution (PikMike)

1156B - Ugly Pairs

Tutorial
Solution (PikMike)

1156C - Match Points

Tutorial
Solution (BledDest)

1156D - 0-1-Tree

Tutorial
Solution (BledDest)

1156E - Special Segments of Permutation

Tutorial
Solution (BledDest)

1156F - Card Bag

Tutorial
Solution (Roms)

1156G - Optimizer

Tutorial
Solution (e-maxx)
 
 
 
 
  • Vote: I like it  
  • +116
  • Vote: I do not like it  

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

In problem B tutorial, it should be "odd positions in alphabet ("aceg…") and even positions in alphabet ("bdfh…")", instead of "odd positions in alphabet ("acef…") and even positions in alphabet ("bdgi…")"

»
3 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

wonderful tutorial thank you PikMike, we appreciate your effort

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C. Why does my java code fail? https://codeforces.com/contest/1156/submission/53668587

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I love the solution for E, great task ^^

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

In B, complexity is not O(n), it is O(n log n) for sorting.

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

    Solution on the editorial is $$$\mathcal{O}(n \log n)$$$, but since we are only sorting alphabets we can use counting sort to fit the solution in $$$\mathcal{O}(n)$$$. Of course it would be better to write the correct complexity on the editorial, since this optimization is not very needed in this problem :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I know that it is possible to achieve $$$O(n)$$$ by using counting sort. I also told about the solution in editorial.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can use frequency table to maintain the letters, then also we can achieve O(n).

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

can someone please explain the proof of the problem C a little bit more? I didn't get it from the editorial.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's easy to check if m pairs can be formed from the array or not in O(n) time. So you perform binary search on the answer(no. of pairs to be formed) which is done O(nlogn) time.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If i am not wrong then again checking for that will require the same proof anyways?

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

        Suppose let's say for k=4, that means we assume that we can make at least 4 pairs. then we can make pairs in the following manner:

        I have marked the leftmost points as 1,2,3 and 4. They have been paired with points at the end of dotted path.

        We have to prove that the minimum distance in a pair is maximized.

        Suppose if the point 4 is being paired with any other point other than the right most it will minimize its distance. Similarly for 3rd we then choose the best available points. Similar for 2nd and 1st.

        If any other 4 pairs are possible then it is always possible to change them into these pairs by swapping(see editorial). But if even these pairs are not possible then we cannot make 4 pairs.

        Sorry for poor drawing :P

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

Problem E

In fact this problem can be solved using Divide and Conquer. :)

Let's consider all the subsegments $$$[l',r']$$$ whose left bound $$$l'$$$ is in $$$[l,mid]$$$ and whose right bound $$$r'$$$ is in $$$(mid,r]$$$ ($$$l,r$$$ and $$$mid$$$ are known in this part of the Divide and Conquer) . When $$$l'$$$ moves from $$$mid$$$ down to $$$l$$$, we can know the rightest pos satisfying $$$\max_{i=mid+1}^{pos}p_i<\max_{i=l'}^{mid}p_i$$$ (it is certain that they cannot be equal) using a pointer $$$rpos$$$. And we are now looking for those $$$r'$$$s. When $$$mid<r'\leq rpos$$$, the maximum value is in $$$[l',mid]$$$. Now $$$l'$$$ and the maximum value (let's call it $$$maxn$$$) are fixed, so we check if the $$$j$$$ whose $$$p_j$$$ is $$$maxn-p_{l'}$$$ is in the range of $$$(mid,rpos]$$$ and update the answer. When $$$rpos<r'\leq r$$$, the maximum value is in $$$(mid,r']$$$. Let's solve this part of the problem offline. When we enumerate $$$i$$$ from $$$r$$$ down to $$$mid+1$$$, we put $$$maxn-p_i$$$ (where $$$maxn=\max_{j=mid+1}^i p_j$$$, which can be got very quickly) into a bin and for an $$$l'$$$ whose $$$rmax+1$$$ is just $$$i$$$ we calculate how many times we put the value of $$$w_{l'}$$$ into the bin.

The time complexity is $$$O(n\log n)$$$.

Code: 53674474

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I don't quite get why the mentioned solution for problem E is O(n(log(n)). Can someone explain more ?

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

    I don't have the proof but i run a dp to see the worst case
    https://pastebin.com/6ZmH8uEX pd. it's slow but it will work in a couple of minutes

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

    As given in the tutorial, we will first find the left and right boundaries of each element upto which it is the maximum element and for finding the solution for segments with size $$$m$$$, will iterate through the half which has fewer elements i.e. $$$< m/2$$$ elements in it.

    Given all this, consider the segments with max element $$$n$$$ present some where in the array, and divides it into two parts of size $$$m_{1}, m_{2}$$$ such that $$$m_{1}+m_{2} = n-1$$$, so here iterate through $$$min(m_{1}, m_{2}) \lt (m/2) = O(n)$$$ elements.

    Now consider the segments with max value = max value in $$$m_{1}$$$-segment & $$$m_{2}$$$-segment. Lets say the array is now partitioned into segments of size $$$m_{3}, m_{4}, m_{5}, m_{6}$$$, with $$$m_{3}+m_{4} = m_{1}-1$$$ and $$$m_{5}+m_{6} = m_{2}-1$$$, now the number of elements to be iterated in total of the the $$$2$$$ selected maximum elements is $$$< (m_{1}/2) + (m_{2}/2) = O(n)$$$ and so on for next $$$4$$$ max elements is $$$< (m_{3}/2)+(m_{4}/2)+(m_{5}/2)+(m_{6}/2) = O(n)$$$, so on for next $$$8$$$ max elements, $$$16$$$ max elements, .... So to check for all the elements $$$O(n) * (log(n)+1) = O(n(log(n))$$$.

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

here is my solution for D that uses DP on Trees. The implementation is extremely simple, but the transitions are more complex to come up with. 53644201

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To make it easier for those who would attempt this riddle: sub[node][0/1] — is an array that counts how many paths can be made by 1-edges and 0-edges when going from leaves to the root. dp[node][0/1] — is an array that counts how many paths are there to the current node, from the root (by subtracting number of paths going up from those going down() ) plus number of paths from the leaves(from first array — "sub"). Pretty smart.

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

I think problem C doesn't need a binary search. A single loop solves the task. Look at my submission 53648314

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

    Please explain your solution, it looks amazing!

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

      At most we can find $$$n/2$$$ pairs of points. So, first we have to sort the array and start to iterate from the middle of the array to the beginning. Also we need a pointer to the last element. If the current point match with the last point, increment the answer by 1 and decrement the pointer of the last element. :) That works because the way we choose the points is optimized.

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

could anyone help me to understand "if(siz[w][x] < siz[w][y]) swap(x, y);" what mean this code ?

i found that just like Union Find's rank unite, when i delete this code , i got ac too(even faster).

But if i delete this code, i think it will change the size of siz[0][i] or siz[1][i], maybe when i calculate the root "if(par[0][i] == i) ans += (siz[0][i] — 1) * 1LL * siz[0][i];"

and got wrong answer.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this code maybe reduce time of path compress sometimes , but it also takes time to run this code

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This means that when merging two trees in union-find BledDest merges smaller tree to bigger one. To balance resulting tree, so the "find" operation wouldn't become O(n) in worst case, and solution wouldn't become O(n^2).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In B why do we have to check whole list cant we check only at junction of odd and even array?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Certainly , it works

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

    After sorting the string, I used a greedy approach, together with a stack and a double ended queue to construct the final string.

    The idea:

    1. If a character cannot be appended at either end of the deque, it is pushed on the stack.

    2. Before and after consuming s[i], the stack is checked to see if any character can be added at either end.

    3. If any character remains on the stack at the end, then there is no solution.

    Here is my submission 53699191

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem E,you can use Sparse-Table and Union-Find. https://codeforc.es/contest/1156/submission/53700970

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Two things need to be proved are missing in C's editorial:

Q1) For a fixed $$$k$$$, why does matching the $$$ith$$$ element from the first $$$k$$$ elements with the $$$ith$$$ element from the last $$$k$$$ elements maximize the minimum distance across all pairs?

A1) Consider the two pairs $$$(L1, R1)$$$ and $$$(L2, R2)$$$, where $$$L2>=L1$$$ and $$$R2 \leq R1$$$. The minimum distance here is $$$R2-L2$$$. We can swap $$$R1$$$ and $$$R2$$$ producing the pairs $$$(L1, R2)$$$ and $$$(L2, R1)$$$. Where $$$R1-L2 \geq R2-L2$$$ and $$$R2-L1 \geq R2-L2$$$. So the minimum distance now is $$$>=$$$ the previous minimum distance. This implies that for any two pairs, the pair with less $$$L$$$ should have the less $$$R$$$. In other words, the $$$ith$$$ elements of the first and last $$$k$$$ elements should be matched.

Q2) Why does binary search work for this problem?

A2) After sorting the array $$$arr$$$, denote $$$least[i]$$$ to be $$$j-i$$$ where $$$j$$$ is the least index such that $$$arr[j]-arr[i] \geq z$$$, or $$$+\infty$$$ if no such $$$j$$$ exists. For a valid $$$k$$$, $$$max_{i=1}^{i=k}\ least[i] \leq n-k$$$ (Assuming $$$1$$$-based indexing). If the previous inequality doesn't hold, we won't be able to match some $$$ith$$$ elements of the first and last $$$k$$$ elements. Denote $$$k\_inv$$$ to be the least invalid $$$k$$$, $$$max_{i=1}^{i=k\_inv}\ least[i]>n-k\_inv$$$. So any $$$k'$$$ where $$$k'>k\_inv$$$ will be invalid also, because $$$max_{i=1}^{i=k'}\ least[i] \geq max_{i=1}^{i=k\_inv}\ least[i]$$$ and $$$n-k'<n-k\_inv$$$.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

[Problem B]

I am thinking about pretty straight forward, yet quite interesting solution to this problem. It is random shuffling till we get good arrangement or terminating and saying "No answer" after 1000 iterations.

I reckon that many people did it this way. Wonder if it is 100% correct and provable.

Solution: 53719836

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

Another solution for problem E. First, you need to build a tree representing the whole permutation. Choose the largest element n as the root of tree, then elements on the left side of n in the permutation form the left subtree of root, elements on the right side of n in the permutation form the right subtree of root.

The question is about how many pairs of (u, v) for each node x, where u locates in the left subtree of x and v locates in the right subtree of x.

After building the tree, do dsu on the tree. The total time complexity is O(nlogn).

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

In problem E. Why did solutions like these https://codeforces.com/contest/1156/submission/53741778 pass on time? For example test is [1, n, 2, n-1, 3, n-2, ...]

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

I can't understand: "we should match the leftmost L-point with the leftmost R-point, the second L-point with the second R-point, and so on, in order to maximize the minimum distance in a pair". Can someone explain me with?

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

Annotation-2019-05-06-223155

Can anyone please explain these words with some examples? I haven't a clear idea about that.

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

nice problems

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

In problem C : -> in editorial there is a :

for(int i = 0; i < m; i++)
       good &= (a[n - m + i] - a[i] >= z);

     can this be changed to 

     for(int i = l; i < m; i++) // i = l 
       good &= (a[n - m + i] - a[i] >= z); 

     i tried submitting code with this change but it gave wrong answer

-> also in question they say if pair i and j do not have any other match then they can be matched, so in sample test case 2 : 5 6 7 8 9 10  why can't 7 and 8 be a match / pair ?
»
13 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi, would anyone be so kind as to explain this test case for Problem G: Optimizer?

  • c = a
  • a = b
  • b = c
  • res = a&b

Correct output: res = b & a

In such a case where the variables refer to each other in a loop-like way, how do we interpret "res = a & b" ?

Much appreciated, thanks!

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

can somebody explain me or give a hint how to find P⋅Q^(−1) (mod 998244353) (problem F)? I don't understand how to find mod for real number.

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

Problem C, why my code failed, I was so confused...

for every element a[i], I use binary search to find a[i]+z, in order to avoiding select the same position, I construct the binarySearch(target, l, r) with [l,r). every times I change the value of l to search the next position.

iread = lambda: int(input())
lread = lambda: list(map(int, input().split()))
sread = lambda: input()
show = lambda grid: list(map(print, grid))
mod = 10**9 + 7

n,z = lread()
a = lread()
a.sort()

# in array a, find a target'index between index [l, r)
# if there are multi target, return the most left index.
def binarySearch(target, l, r):
    lo, hi = l, r
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

# vis to avoid repeat selection
vis = [0] * n
l, r = 0, n
res = 0
for i in range(n):
    if vis[i]: continue
    target = a[i] + z
    index = binarySearch(target, l, r)
    if index >= n: break
    vis[index] = 1
    res += 1
    l = index + 1
print(res)
»
2 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me with problem C ! I've used two pointers to make pairs Here is my submission

Edit: Sorry i figured the problem!