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

Автор 18o3, история, 2 года назад, По-английски

ICPC India 2021 Preliminary Online Round is happening at 4th of September 2022 from 8:00-10:30 PM IST here.

Let's use this blog to discuss the round after it ends. I know there is one more blog but it already 256 comments and it would be tedious to continue this round discussion there.

Hope to see you all on the leaderboard.

P.S. Here's the selection criteria for different regionals.

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

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

Pune gwalior me distinct colleges kitne h?

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

How to solve LEXRIS?

I tried with trie and segment tree but that didn't work.

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    I solved it with Polynomial Hashing with DP Segment Tree.

  • »
    »
    2 года назад, # ^ |
    Rev. 8   Проголосовать: нравится +5 Проголосовать: не нравится

    First calculate the lexicographic order of substrings. Now dp[i][j] = best possible result if (i,j) is your first substring. You will need to maintain suffix maximums to query over only substrings lexicographically larger than first string

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

      calculate the lexicographic order of substrings. Is there a way to do this quickly? During the contest we felt that sorting all substrings naively would TLE.

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

        No that won't give TLE since it is N^3

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

          I thought that sorting of every substring using std::sort would take $$$\mathcal{O}(N^3\log(N^2))$$$ time in the worst case. Isn't that true ?

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

            $$$log(n^2) = 2 log n$$$ so it is $$$O(n^3 log n)$$$ in worst case which is fine

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

    It's easy, dp[i][j]=max score if s[i..j] is your last substring. Now the transition is dp[i][j]=score[j-i+1]+max(dp[k][l]) where l<i and s[k..l]<s[i..j]. Now notice that you can easily check this using LCP and Suffix Array. Then it's just some case handling depending on whether the LCP is s[k..l], s[i..j], or both, or neither. Notice that you can maintain prefix max for each row of the DP to quickly get the answer. Then you can take max over all (and 0, of course).

    Submission (uncommented)

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

    Sorting (Lexicographically), then calculated all substring which are same because we cannot select substring with same values we need to select strictly increasing in lexicographic order.

    Used Fenwick tree to find prefix maximum score.

    Now to select each substring (l , r). We need to find the a substring which ends before l (Non overlapping) and is Lexicographically smaller which was maintained by sorting already. So i used fenwick tree to find maximum score till [0 , l-1] and updated current score at r because no substring starting before r can be selected with current subrting. This update also makes a maximum update from (r , n). Please view code for better understanding.

    Code for reference Click Here

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится
    Idea
    PS

    Solution

    Also what would be the CF rating for this problem ?. My guess is 2100+ .

    Regret
  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +14 Проголосовать: не нравится

    This is what we did(without any Complicated data structures):

    Define dp[i][j] as the maximum score for the suffix [i..n] such that the first substring starts at index i and has a length j.

    Now, step 1 is to precompute longest_common_prefix[i][j] as the length of the longest common prefix of substrings starting at i and j respectively for all i,j. This can be done naively in O(n^3) time.

    Now, coming to the transitions, to calculate dp[i][j], we will iterate for k, that is, the starting point of the next substring. Now if lcp[i][k] is 'L' and s[k+L] > s[i] OR if L>=j, then we can say that dp[i][j] = max (dp[k][L+1] + a[j], dp[k][L+2] + a[j]....).

    This can be done quickly by maintaining suffix maximums.

  • »
    »
    2 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

    There is no need for seg tree or fenwick tree. Just sort all the substrings in increasing order. Consider a substring $$$[i,j]$$$ as an interval $$$(i,j)$$$. Every interval has some priority (which is of course, determined by its position in sorted order).

    Now imagine placing intervals in increasing order of their priority (i.e from smallest lexographical order to largest). Suppose you're at the $$$i^{th}$$$ substring. Let $$$l(i)$$$ and $$$r(i)$$$ denote the left and right endpoint of the substring.

    Define $$$dp[r(i)]$$$ as the maximum score you can get if you place the $$$i^{th}$$$ substring at the last operation, so, $$$dp[r(i)] = max ( dp[j] + cost[r(i)-l(i)+1] )$$$ for all $$$j$$$ such that $$$j<l(i)$$$.

    This is because at last I'm placing the substring $$$[l(i) , r(i)]$$$, so before that I must have placed a substring $$$[l(j),r(j)]$$$ such that $$$r(j) < l(i)$$$ (substrings must be non overlapping), and since I'm placing substring in increasing order, its guaranteed that $$$j^{th}$$$ string will be smaller than $$$i^{th}$$$ string (there's a small catch here but you can easily fix it ;) ).

    Since there are $$$O(n^2)$$$ substrings and for every substring I will iterate through all $$$j$$$'s, there are only $$$O(n)$$$ right endpoints, so it would take $$$O(n^3)$$$ time.

    Note that you can sort all substrings using trie, so that would also take $$$O(n^3)$$$ time :)

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

      Very neat and simple solution, thanks for sharing. Can we extend this and use Suffix Array/Segment tree to solve in $$$O(N^2)$$$?

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

        Looks difficult, sorting is also the bottleneck. You can optimize dp transitions using seg tree, but I don't see how can we do sorting in $$$O(n^2)$$$ using suffix tree. (I don't know much about suffix array)

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

    When will the final result come?

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Kinda mad that my LEXRIS failed because it had anti-hash tests :(

»
2 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

How to solve Beautiful Array?

Can anyone provide a counter case to the following idea (except for $$$n \leq 4$$$):

  • Conditions extend to also imply $$$a_i \ne a_{i + 1}$$$.

  • Brute over all possible values for the MOD 3 positions in $$$O(n ^ 3)$$$.

  • For each triple, try to perform swaps between each pair when they have each other's values. I think the order in which we perform the swaps shouldn't matter since we only have 3 positions (I couldn't find a countercase with $$$n \leq 10$$$ while stress testing).

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

    Same as what I did. Did you fail at test 11 too?

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

    You forgot to resolve 3-length cycles, i guess...

    Consider the array,

    [1,2,3,1,2,3,1,2,3,1,2,3, 2,3,1]

    is your answer 2 for this case?

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

    Even handling n=4 was quite tricky imo.

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

      Agreed.

      I simplified it though, basically the answer can't be more than 2, you can just change 1st and 4th element to get a beautiful array.

      You can easily check if answer is 0, now just check if answer is 1.

      If 1st and 4th elements are equal, you just wanna make 2nd and 3rd element different from 1st, if that can be done in 1 move, answer is 1.

      If 1st and 4th element are unequal, then either 1st element will take 4th's value or vice versa, so just try both and this case can also be checked pretty easily.

      Another way could've been, to make a check function and then try every move on the array and check.

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

        What we came up was even simpler, I have no proof to why this works but just intuition.

        • If its already valid, output 0.
        • If all four numbers are the same, output 2.
        • Otherwise, output 1.
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    We failed at test 5.

    1. For each triple a,b,c form 3 groups based on mod 0.
    2. All elements with mod 3 = 0 should be a, mod 3 = 1 should be b and mod 3 = 2 should be c.
    3. All elements that are not a,b,c need to converted so add that many operations.
    4. Now swap (a,b) from Group1&2 and similarly (b,c) from Group2&3 and (a,c) from Group1&3. This will each cost 1 swap, so add number of swaps.
    5. Atlast add 2 swaps for every cycle (b,a,c) or either (c,a,b).
    6. Add number of operations for elements that are still not matched.

    But this got WA, can anybody get why?

    Code Link : Beautiful Array

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

      You need to handle the cases for n = 3 and n = 4 separately as well. Here is a failing test case:-

      1
      3
      3 3 1
      

      answer should be 0 your code gives 1

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

        We didn't even think about this while debugging. We were so sure we were messing up the implementation part. Damn.

        Thanks for the reply.

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

      Congrats for failing.

      Next time fail better

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

For the amrita puri regionals, Will the first team after rank 30 be eligible for regionals? Even if there are some teams below 30 from the same college.

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

I found out that answer for E is $$$m^{th}$$$ term in Expansion of $$$\frac{1}{(1+x)(1-x)^{n+1}}$$$ for all even $$$n$$$ except $$$n=2$$$, for which its just $$$ceil\left({\frac{n^2}{2}}\right)$$$ by OEIS.
How funny it'd have been if I OEIS'd my way into the regionals
But idk how to fft, also no time

»
2 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

Amritapuri meetup when

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

How to solve Tree regression?

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

    It can be proven that it is always optimal to choose the Path as the longest path from among the vertices of the set. (Try to prove by contradiction, it is quite simple)

    So the problem boils down to finding the longest path in a given subset of the tree. For this, we used a concept called auxiliary tree (which is basically, making a tree which contains all the vertices of a subset of the tree along with some more vertices to make sure all the LCAs are present in the auxiliary tree). The size of such auxiliary tree is never more than twice the size of the subset of the tree. The weights of the edges of this auxiliary tree is the original distance between the 2 points in the original tree. Thus we can simply find the longest path using 2dfs method.

    However, solving each query in MlogN gave us TLE, and we had to use O(1) per query LCA, that was quite strange in my opinion, we lost rank 1 due to those penalties :(

    Edit: Refer to radoslav's video on Auxiliary Trees

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

Where and when will we get updates regarding regionals, qualified teams etc?

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

    We will publish it on CodeDrills Discuss and contest pages. Regionals would also publish it on their sites.

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

Any idea on how to solve Integer Median Probability (G)?

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

    When $$$N$$$ is odd then the answer is 1. Now if $$$N$$$ is even then the middle two elements in the array(sorted order) must have the same parity. Consider the number of selections where the smaller middle element is $$$i$$$ and the larger middle element is $$$j$$$ with $$$i < j$$$ (We will have to handle $$$i = j$$$ separately). We have to chose $$$\frac{n}{2}$$$ elements from $$$[1,i]$$$ and $$$\frac{n}{2}$$$ elements from $$$[j,m]$$$ with at least one $$$i$$$ and one $$$j$$$ respectively. Number of ways for $$$[1,i]$$$ are $$$i^\frac{n}{2} - (i-1)^\frac{n}{2}$$$ and for $$$[j,m]$$$ it is $$$(m-j+1)^\frac{n}{2} - (m-j)^\frac{n}{2}$$$. Also you have to arrange them in the array so pick $$$\frac{n}{2}$$$ places for the smaller elements.

    Your answer is now $$$\sum_{i < j,\; j-i\; is\; even} \binom{n}{\frac{n}{2}}[i^\frac{n}{2} - (i-1)^\frac{n}{2}] \cdot [(m-j+1)^\frac{n}{2} - (m-j)^\frac{n}{2}]$$$ plus the number of arrays where both middle elements are equal.

    To find arrays with middle elements equal, just subtract all arrays where middle elements are unequal from the total number of possible selections. To find the number of arrays where middle elements are unequal, you need to compute the above expression for all $$$i < j$$$.

»
2 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

When are the results getting announced?

»
2 года назад, # |
Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится