lanhf's blog

By lanhf, history, 4 months ago, In English

1896A - Jagged Swaps

Writer: maomao90

Hint 1
Solution
Implementation

1896B - AB Flipping

Writer: maomao90

Hint 1
Solution
Implementation

1896C - Matching Arrays

Writer: maomao90

Hint 1
Solution
Implementation

1896D - Ones and Twos

Writer: lanhf

Hint 1
Solution
Implementation

1896E - Permutation Sorting

Writer: maomao90

Hint 1
Solution
Implementation

1896F - Bracket Xoring

Writer: maomao90

Hint 1
Hint 2
Hint 3
Hint 4
Solution 1
Solution 2
Solution 3
Implementation

1896G - Pepe Racing

Writer: thenymphsofdelphi

Hint 1
Hint 2
Hint 3
Hint 4
Solution 1
Solution 2
Implementation (Solution 1)
Implementation (Solution 2)

1896H2 - Cyclic Hamming (Hard Version)

Writer: xuanquang1999

Hint 1
Hint 2
Hint 3
Hint 4
Solution
  • Vote: I like it
  • +180
  • Vote: I do not like it

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

Auto comment: topic has been updated by lanhf (previous revision, new revision, compare).

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

Thanks everyone for participating in our round! Do you have any suggestions for us?

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

    I loved today's contest! Good job guys!

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

    Maybe code examples for solutions?

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

    Pay the promised prize from previous round :) pretty please!

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

      But that's not the problemsetters' job, is it? And even if it was, the previous CodeTON round was set by different people...

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

        Hmm maybe you are right. But the problemsetters (maomao90) posted on the announcement that there would be prizes, so hopefully they can pass the message along.

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

    sample of problem B is too weak

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

    Thank you for your effort. It's been a great contest, and I liked the problems.

    The hints are good, but I think some of them can be improved to give a real insight on how one could solve the problem:

    1896A:

    Hint 1

    1896C:

    Hint 1
    Hint 2
    Hint 3
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Fast tutorial!

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

random greedy on F (make element i 0 if you can make it 0 without violating balanced string condition)

This takes k = 10 even on random tests of n = 2e5

You are welcome to hack :)

https://mirror.codeforces.com/contest/1896/submission/234298869

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

Nice problems. Thanks for the round.

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

D can also be done using bitsets by storing prefix sums

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

    Yes, it can. I solved with bitset during the contest. Here is my explanation of details and link to submission.

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

      Oh! why does it works? I have thought about this...but is this algorithm's time complexity right? I thought it would goes to O(N*N/w) if the query's s was close to the pref[n].. //Oh my god! I have try your solution.. Incredible improvement "#pragma GCC optimize("Ofast")

      pragma GCC target("avx2")"

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

Will the implementations be append?

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

Good contest, Fast editorial, generous prizes!

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

Hello! I have a question at problem E: For the example: 6 3 2 7 4 1 5 for number 6 h[i] = 5 and the number of positions j where 1 < j < 6 and 1 < a[j] < 6 is 3 (for a[j] = 3, 2 and 4), so the answer for 6 will be 5 — 3 = 2. However, the correct answer for 6 is equal to 4, because it only jumps over number 3..Can you tell me where I'm wrong, please?

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

    Actually, you have to subtract the number of skipped indexes not the total elements < 6 and its position > 6's position

    OR you can make like that , let OP( x ) is number of operations needed to make x at i = x

    OP( 6 ) = 6-1 = 5

    OP( 3 ) = 3-2 = 1 , OP( 2 ) = 2+7-3 = 6 , OP( 4 ) = 4+7-5=6

    for all j : where 1 < j < 6 and 1 < a[j] < 6

    OP( j ) < OP( 6 ) -> OP( 6 ) = OP( 6 ) - 1

    ---[ Detailed Steps ]----

    0 | 6 3 2 7 4 1 5 [ 6 need 5 op ]

    1 | 5 6 3 2 7 4 1 [ 6 need 4 op ]

    2 | 1 5 3 6 2 7 4 [ 6 need 3 — 1 op ] [ 6 skipped 3 position ]

    3 | 1 4 3 5 6 2 7 [ 6 need 1 op ]

    4 | 1 2 3 4 5 6 7 [ 6 is Good ]

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

I tried to do D with another approach but getting a wrong answer.

Approach->

  1. Lets reconstruct the array by merging same consecutive elements to a single element. like for array 1,1,2,2,1,1,2 modified new array will be 1,2,1,2.

  2. Let m be the size of the modified array

3.Now if m is even you can form every sum ranging from 1 to total_sum of array(proof is simple)

4.but in case m is odd we can separately check for for the first m-1 groups or last m-1 groups

5.how i checked for the last m-1 groups is if sum of last m-1 groups is >=s then ans is yes otherwise check parity of element in first group and the diff between s and sum of last m-1 groups should be same for yes(coz then you can add elements from 1st group..basically extend your subarray).

6.same goes for checking of first m-1 groups

7.also we have to maintain length of prefix starting with 1,2 and length of suffix starting with 1,2 (can be done either by segment tree or simple multiset which have index of 1 and 2 in the array)

I am getting wrong answer for this approach can anyone explain why??

234328583

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

very nice problems and clear editorial,the best round.

»
3 months ago, # |
  Vote: I like it -20 Vote: I do not like it

CodeTON Round 7 A is the same as CodeTON Round 3 A from a year ago, just worded in a different way

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

Here is a solution for E using persistent segment tree..Stuck in memory for a hole day..234365527

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

Can someone explain why we are taking max here in the editorial of problem D ** So we will compare max(s[l+1,n],s[1,r−1]) with v to get the answer.**

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

    It is actuallly max(s[x+1,n],s[1,y−1]). We check this when parity of sum of entire array and v is different. Lets say sum of all elements is even and v is odd. In this case we need to find a subarray with maximum odd sum. To change the parity of subarray sum , we need to remove a '1' from the subarray. Removing 2 wont change the parity. So either we take a subarray after the first occurence of 1 in the array, or before the last occurence of 1 in the array. We actually take the maximum of both cases. This is what max(s[x+1,n],s[1,y−1]) means.

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

What is difficulty rating for E

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

I solved A with hardcore brute force. I submitted again in the contest but my first solution would have passed. 234320361

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

I wrote this code using wavelet tree for the problem E which gave MLE. Shouldn't the memory complexity of this program be O(N log MAXV) where N = 1e6 and MAXV = 1e6.

I used a similar code with merge sort tree which got accepted while the memory complexity of merge sort tree is similar to wavelet tree for this problem.

Was it due to the fact that wavelet tree has a bit higher constant factor. However even when I reduced the MAXV and N to 1e4 it still gave MLE which it shouldn't even with higher constant factor.

Can someone explain the case with wavelet tree.

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

G is really fun but only for the thought process not implementation ToT

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

In Problem D solution, max(s[l+1,n], s[1,r-1]) should be max(s[x+1,n], s[1, y-1]) ?

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

I was able to pass Merge Sort Tree on problem E only after rewriting all vectors to arrays, in order to optimize memory usage. But even then, my solution consumed 245 MB out of 256 MB. During the contest, figuring out this trickery took me half an hour. Is there any reason to make such memory constraints that solution which requires $$$O(n\log n)$$$ memory barely passes?

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

Sorry for necroposting, I was going to post it before, but I forgor

I am surprised that the authors didn't mention (or did I miss it?) the following trick in F (which probably doesn't simplify the solution, but maybe makes the thought process easier). After each operation, let's also flip every second bit: that is, 2-nd, 4-th, 6-th, and so on. Now every operation flips the bits that correspond to ( instead of that obscure statement.

Looking at the first (or last) bit of the input, we know the parity of the total number of operations, and if it is odd, then we can say that this transformation should be applied to the input string once, and then we can think in terms of flipping open parentheses.

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

C's editorial is too tough to understand

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

Edit

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

Can someone explain this (C) : Let $$$i$$$ be the largest index between $$$1$$$ and $$$n-x$$$ where $$$p_i\neq i+x$$$ ($$$p_i<i+x$$$ due to maximality). Why does $$$p_i$$$ has to be less than $$$i+x$$$ ??

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

    I dont know about editorial but heres how i solved

    first I sort the array , how suppose that rearrangement is possible . so to get x beauty our best chance to bet on last x element (coz they are max in a) and smallest x element from b. after that we want that for n-x element we dont get any beauty . so for max of first n-x elemet we our best chance is max of n-xth element of b .(if(a>b) cout<<no<< else we make pair of these two .) similar for n-x-1 indice and so on. heres link of my solution

    problem c