Ari's blog

By Ari, history, 4 weeks ago, In English

Note: I can't figure out how to place the tutorials inside spoilers. If someone is familiar with how CF spoilers work and can help I would really appreciate it. For now, be warned that the tutorials are visible by default (but everything else isn't)

UPD: I figured out how to use spoilers! Also added implementations for all problems.

Thanks for participating in our contest!

1509A - Средняя высота

Author: Kuroni
First solve: cfg0d at 00:01:02

Hint
Tutorial
Comments from the authors

Implementation

1509B - ТМТ документ

Author: Ari
First solve: blue5002 at 00:04:51

Hint
Tutorial
Comments from the authors

Implementation

1509C - Спортивный фестиваль

Author: Ari
First solve: Dukkha at 00:05:32

Hint 1
Hint 2
Tutorial
Comments from the authors

Implementation

1508A - Бинарная литература

Author: Ari
First solve (Div. 2): traxex2 at 00:22:48
First solve (Div. 1): tourist at 00:05:04

Hint 1
Hint 2
Hint 3
Tutorial
Comments from the authors

Implementation

1508B - Почти отсортированные

Author: Both of us!
First solve (Div. 2): shenmadongdong.qaq at 00:29:52
First solve (Div. 1): tourist at 00:08:19

Hint 1
Hint 2
Hint 3
Tutorial
Comments from the authors

Implementation

1508C - Завершите MST

Author: Kuroni
First solve (Div. 2): deepspacewaifu at 01:42:36
First solve (Div. 1): maroonrk at 00:33:17

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Comments from the authors

Implementation

1508D - Обмены на ребрах

Author: Ari
First solve: ksun48 at 00:57:13

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Comments from the authors

Implementation

1508E - Дерево-календарь

Author: Kuroni
First solve: ecnerwala at 01:02:26

Hint 1
Hint 2
Hint 3
Hint 4
Tutorial
Comments from the authors

Implementation

1508F - Оптимальное кодирование

Author: Kuroni
First solve: ecnerwala at 01:52:02 (The only contestant who solved this problem!)

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Tutorial
Comments from the authors

Implementation

Finally, here's some funny moments that happened while we were working on the round :)

Memes
 
 
 
 
  • Vote: I like it
  • +431
  • Vote: I do not like it

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

Longest editorial I ever had the chance to read. Anyways thanks, it's awesome <3

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

    Sorry, as we stated the spoilers were not working to our favor :(

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

For Div 2 D, can somebody find a case where it fails? submission, I think on one case it doesn't print any string because my answer gets over n*3.

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

    If you find any mistake or corner case please reply me, my solution fails in the same testcase with the same error (In the test 2 case 43)

    Thanks!

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

      I found one: 1 3 001111 110110 000000

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

        https://codeforces.com/contest/1509/submission/113292585 i did according to the tutorial but my submission gives WA on test 9. Where am I going wrong? please someone help

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

          Your mistake, is a common mistake, since a I had the same mistake use a variable ans and print it just once, your mistake is in the fisrt if, you forgget the endl before the return.

          skipping this you code have a good implementation good look bro!

          PSD: I submmit your code for be sure that im right and sorry for my bad english

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

gg

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

i think problem E div1 can be done with HLD & treap by reversing the operations :thinking:

if any one solved the problem with the similar solution please share it : )

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

This contest was amazing and specially it's editorial after all Thanks for preparing such contests and we're waiting for more contests from you! :D

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

Thank you!

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

I don't understand why my B solution is wrong, pls help 113225551

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

    you go through forward and taking the count of Ts and Ms do the same thing for backward it can't be less Ts from Ms from froward and from backward

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

Can someone explain c

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

    Can someone please explain recurrence relation in C. Not able to understand.

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

My solution to F runs in $$$O(n^2)$$$, and is quite simple. Here's my simple condition for an edge being in the graph:

For any vertex $$$v$$$, there are 4 candidates for edges involving this vertex: consider the intervals containing $$$v$$$ which extend the furthest left and the furthest right; let those bounds be $$$l_v$$$ and $$$r_v$$$. Then, $$$v$$$ can have edges to its predecessor in $$$[l_v, v]$$$, its successor in $$$[l_v, v]$$$, its predecessor in $$$[v, r_v]$$$, and its successor in $$$[v, r_v]$$$. Furthermore, an edge exists iff it is a valid candidate for both endpoints.

Then, we can just maintain these candidates and the counts in $$$O(n^2)$$$: starting from the initial state, $$$l_v$$$ decrements and $$$r_v$$$ increments at most $$$O(n^2)$$$ times in total. The code is very short, and runs in less than 1 second.

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

    I'm actually surprised about your solution; I had an $$$O(nq)$$$ solution but I didn't know that $$$O(n^2)$$$ exists (probably the reason is because I abruptly changed the constraint from $$$n = q = 50000$$$ to the current one like 1 day before the round).

    Anyway, this solution is very clean and also interesting, thanks.

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

Why this solution for Div2 C gets TLE despite that fact that it's $$$O(n^2)$$$ ? It is because it should be written iteratively ?

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

Is there any greedy solution for Div2C? It was tagged greedy in the problemset, hence wondering :)

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

    Maybe the fact that the minimum and maximum should be at the end is a greedy intuition?

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

    sorting step; a[i] is either the minimum or the maximum of the first i elements.

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

    I suppose the greedy solution should be based on constructing the solution array in reverse order, the last element being largest or smallest ,for which we choose the answer by greedily choosing which gives a lower sum for leftover n-1 elements, that is

    • For n elements : discrepancy = max — min
    • For n-1 elements : discrepancy = second_max — min OR max — second_min (greedy choice) .....

    This should be achievable with two pointers for current max and min .

    EDIT : this approach only test for each successive term and doesn't indicate whether the sum of discrepancies will be in same relation as maximum discrepancies.

    So you have to go with a dynamic programming approach for the answer

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

      How did you get to the EDIT observation ? Can you give some test I am confused at this point.

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

        I learnt it the long way : The above greedy approach works for shown 4 test cases . But fails for the first hidden test , i.e., 5th test case .

        So I ran the dp approach for the same problem and reconstructed the array of elements for that case. The last element (first choice) was different for both the cases, --> the max discrepancy is not indicative of sum of discrepancies. I suppose a simple example would be : 5 29 30 67 68 82, dp answer is 121 while greedy leads to 131

        the difference can be seen in the first choice itself,

        • the sequence via greedy approach is : (68, 67), 30, 29, 82
        • while the best sequence is : (68, 67), 82, 30, 29

        I used a random generator to get this sequence LINK TO CODE

        :( too lazy to sit on computer for more than half an hour, trying to improve sitting hours tho, hopefully i can do 3+ questions next contest :)

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

I dont think my div1A/div2D is supposed to pass. Can someone hack ?

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

    Done, random generator found a test that fails.

    Here is also a smaller test case (n=6), there is no example with smaller n. Maybe it helps:

    000001011110
    111100100000
    111111111111
    
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      How you are generating these cases? (some online website or you have your own generator)

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

        For the original test I just generated a bunch of random inputs and tried to see if the solution works (using my own program, basically just a while loop that generates a random input (50% chance for 1 and 50% for 0 at each position) and then runs a simplified version of his code to see if it finds an answer).

        For finding the n=6 case, I went over all the possible inputs for n=1...6 and tried each one. There arent too many possible inputs for n=1,2,3,4,5 and for n=6 it found one quite quickly.

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

In problem 2D, after we find whether out frequent character is '0' or '1', what to do ? like how to iterate and create the resulting string ?

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

    The implementation given is based on first approach. You can look at the mix function.

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

Since so many people were asking for problem C (div2), I decided to make a video tutorial for it.

http://youtube.com/watch?v=7CPgT3gYPoc

Hope you like it :)

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

i failed to recognise these types of dp problems during short contests.so i know i need to practise more of these kinds of problem .it will be a great help if you people suggest me some similar kind of problems .

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

    Search DP Tagged problems on CF and Leetcode.

    Some other problems:

    Longest Palindromic Substring (link)

    Longest Palindromic Subsequence (link)

    Matrix chain multiplication (similar problem to div2C)

    Burst the balloons (link)

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

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

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

I cannot understand div2C, help me!!. we have to minimize discrepancies so why are we adding the element having greatest discrepancies. like An-A1???

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

    I will try to explain my approach. First thing to notice is that discrepancy for i = n-1 ( 0- indexing ) will be fixed (max element — min element). Now we put either the max element or the min element at the (n-1)th position that is the only possible way to change the discrepancy for (n-2)th index. Now choosing greedily won't work because we won't know whether our current best move would be a better decision in future also. This is very obvious that we will require to check all possible combinations hence dp is used to optimize the same. So let's talk about,

    1. dp States : sort the given array, let's say 'L' = any index to left and 'R' denotes any index to right( greater than 'L')- this would mean we have the option to choose between Lth element or Rth element for some index 'i'.

    2. Transition function : this is simple as you can choose between L or R so dp[L][R] = min(go(L+1, R) , go(L, R-1))

    3. Base case : L should be less than R

    Code

    My submission : 113239735

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

      So you are first sorting the array and then checking if it is giving an optimal answer for if I put l+1,l+2...or r-1,r-2... elements in that place and finding the minimum of all the possibilities. Is that what you are doing??

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

        No, starting from last index I am trying to put L ( min element for current index i ) or R (max element for current index i ), sorting the array helped me to get imax, min easily/optimally but still this can be exponential (as at every index i can have two options ) so I optimized it using dp.

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

      hi can please explain what your transition equation is doing like why you are going from l+1 to r and l to r-1?

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

        since the array is sorted, l+1, r means I pick smallest element (rth element) and l , r -1 means I pick largest element ( rth element).

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

I enjoyed this round even though I sucked at it, the editorial is very well written and will help me learn.

Cheers bois

»
4 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

https://youtu.be/28njldrBEo4

problem A hope it helps someone ;)

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

Problem C : What exactly do those transitions represent ? and if anyone has some intuitive or any other way to deduce the state of that dp ?

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

    I explained it in my youtube video

    But I'll try to give a brief description of my solution (slightly different from editorial)

    Basically as mentioned in the editorial we start from the back because we have complete knowledge of d[n]

    d[n]= maximum element in a — minimum element in a (Coz it is for the whole array)

    Now to minimize d[n-1] we have to remove maximum element or minimum element coz otherwise d[n-1]=d[n]

    So after sorting at every stage we have two options either we remove from right side or left side. This gives us a feel for a dp approach because the same state of array can be reached by taking different paths(overlapping subproblems)

    So we define dp[i][j] as we have removed elements from left (minimum) i times and elements from the right (maximum) j times. We can obviously deduce the maximum and minimum in the current array as jth maximum and ith minimum in original array

    This gives us the transition cost -> jth maximum element — ith minimum element As we can reach state (i,j) from (i-1,j) and (i,j-1)

    So basically dp[i][j]=min(dp[i-1][j],dp[i][j-1]) + cost (Very much like grid DP ) The answer is minimum sum we can get after removing exactly n-1 elements

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

      Beautiful it is.

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

        There is an explanation for the author's Dp State that I liked and suhail.loya described in a youtube comment.

        1. The author's solution says that in the optimal solution, suppose after reordering the elements it is a[p1],a[p2],a[p3],..a[pn] where p1,p2,..,pn is a permutation of 1 to n, every prefix of this reordered optimal sequence will be a subarray of the sorted sequence.

        2. This makes sense because it is always optimal to put the maximum or minimum in the current prefix in the last step. This is basically same as my solution in which I remove elements only from the "ends" of the sorted array so the result will always be a subarray.

        3. So the author's solution starts with a subarray of size 1 for which the answer is 0. Now to expand this subarray either you can add one element to the left, or add one element to the right so at every state we have two options just like my solution(where I remove one element from left or right).

        State Description: dp[l][r] is the minimum cost you can create such that the elements of the current array are a[l],a[l + 1],...a[r] in the sorted array a.

        Transitions : You can reach state (l,r) from (l+1,r) [ expanding to left] or (l,r-1) [expanding to the right]. Cost of expanding will be maximum-minimum in the subarray a[l]....a[r] which is a[r]-a[l] since it is sorted.

        So : dp[l][r] = a[r] - a[l] + min(dp[l + 1][r], dp[l][r - 1])

        Answer : = dp[1][n].

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

          Glad you liked it :)

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          every prefix of this reordered optimal sequence will be a subarray of the sorted sequence.
          

          jalotra Can you please explain why it will always be true?

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

            Example: s[] = 29 30 67 68 82

            optimal[] = 67 68 82 30 29, optimal d = 121.

            See that for each prefix i from 0 to len(s) — 1, the optimal sequence is some contiguous subarray of the sorted sequence.

            Proof :

            1. Let's choose a single starting speed S : s[k] => d[1] = 0 here.

            Now I have to add one element at the back of it.

            2a) S : s[k] => Choose either s[k + 1] s[k - 1], because choosing some other element will make d[2] higher.

            3a) S : s[k] s[k + 1] => Choose either s[k - 1] or s[k + 2].

            3b) S : s[k] s[k — 1] => Choose either s[k + 1] or s[k - 2].

            suhail.loya Is this correct?

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it
              Example: s[] = 29 30 67 68 82
              
              optimal[] = 67 68 82 30 29, optimal d = 121.
              

              jalotra consider prefix for i = 3 in optimal solution (67 68 82 30) .How is this a contiguous subarray of s?

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

                The key observation is at every stage while expanding from the current sequence, you want to add an element which is either the minimum of the new sequence or maximum of the new sequence. So you want to either take one step left or one step right in the sorted sequence.

                What I meant by the statement "every prefix of this reordered optimal sequence will be a subarray of the sorted sequence." that every prefix will contain elements which are in a continguous subarray of the sorted sequence

                So prefix for i=3 (67 68 82 30) although is not a subarray of s[] in exact order but it contains only the elements in the contiguous subarray of s[] from index 1 to 4 (30 67 68 82)

                This result is more obvious in the solution I describe in this comment

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

                  suhail.loya Thanks for helping me out :).I was confused at the subarray part but now it is clear. Yeah, the exact order thing was creating the problem for me.

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

      Nice Explanation . Thanks

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

      So basically we can imagine that we are adding elements to an array let's call it A we know that the last element of that array is either the maximum or the minimum (because otherwise it will make the cost of the function d a lot bigger hence d(n) = max(A) — min(A)) and we work backwards by asking which is the last element max(A) or min(A) and after that we ask the same question for the next biggest and smallest elements left in the original array and here we observe that it must be dp

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

      In the last line i think you meant dp[i][j] = min(dp[i + 1][j], dp[i][j — 1]) + Cost. Nice explanation though.

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

        No, according to my dp states it should be min(dp[i-1][j],dp[i][j-1])

        My states are dp[i][j] -> min cost we can get after removing i elements from minimum side and j elements from maximum side. So to reach (i,j) you can remove one element from maximum side in (i,j-1) or one element from minimum side in (i-1,j)

        Code

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

The second solution for Div1A/Div2D is beautiful.

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

    can anyone explain second solution for Div2D im still unable to understand the math over there :/

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

      Let's say we have these strings, and we currently our pointer is pointed to bold ones in all three of them. (say p1, p2, p3)
      0 10101
      1 10011
      1 00100
      Since we have three pointers pointed to three different strings consists only of 0's and 1's, then atleast two of them must point to either 0 or 1.(In this case, p2 and p3 to 1)
      Now after adding the "1" to our answer, we increment pointer p2 and p3.
      0 1 0101
      1 1 0011
      1 0 0100
      Now p1 and p3 is pointed to "0". So in next step, we increment p1 and p3 by 1.
      0 1 0101
      1 1 0011
      1 0 0100
      We repeat this process until one of them is completely exhausted.
      0101 01
      1100 11 (exhausted)
      1001 00
      Our ans in this case comes to be
      1010011 (len = 7)
      Now in simple terms, len + (one of the remaining in p1 (01) and p3 (00) ) is always less than or equal to 9 (3n).

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

        Thanks alot for your detailed explanation , now its clear

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

Could someone please explain how they approached (thought process) problem C in DIV 2 during the contest. How they arrived at greedy idea that it's always better to place the smallest/largest value in the end in DP transition.

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

    Discrepancies are calculated at every stage, so that means in the last stage when we'll have all the elements of the array and the discrepancy for the last stage will be equal to max(a1, a2, ...an) — min(a1, a2, ... an), this difference will be maximum among all the differences that you can have with the elements of the array. So this difference should occur at the last stage only because if it occurs at some stage i which is before the last stage, this difference will keep on adding in our solution and our final result will not be optimal. So this means that either of the max value of the whole array or the min value of the whole array should be added in the end, so this max difference will be added only once which is in the last stage

    I hope that helps :)

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

Nice Editorial tho

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

(https://codeforces.com/contest/1509/submission/113217480)

Can anyone please help me where I am getting wrong?

I have considered two cases

  1. the first and the last character should not be M

2 The number of T should be even and the number of M should be half of the number of T

Am I missing anything?

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

Can anyone prove problem C can or cannot be solved with greedy? I use greedy and cannot pass example 3.

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

Getting trouble in deciding the states for dp in C(The sports festival) can any one tell how to decide the state of dp like in two state dp problems like this?

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

Can anyone explain E Solution? Not very clear from tutorial

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

In problem C, I don't get how does dp(l+r, r) correspond to placing the smallest element at the end of the sequence.

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

In the Problem div2B, shouldn't this statement: "A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero) characters" be corrected as: "A string a is a subsequence of a string b if a can be obtained from b by deletion of several (possibly, zero) characters, without changing the order of the elements"? I wasted some time thinking if the order is important or not -_-

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

    Why stop there?

    "... without changing the order of the elements, without inserting new characters, without turning the characters upside down,..." The list can go on.

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

editorial is awesome

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

Great contest. Even better editorial.

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

Great contest great editorial

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

I don't understand why my solution for Div1A is wrong. can somebody please help me check? 113203126. My method was just to try each pair of strings, and for every character of the strings, if they were different, my answer would add each of the characters once, and if they are the same, it would add just that one character. This generates three different solutions, and we take the shortest one. It should guarantee that the shortest string would have a length shorter than 3n. Please help, thanks

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

    Sometimes the length of your ans string is less than 3*n.
    Test case :
    n=2
    0101
    1010
    1011
    I fixed that but still, it gave WA. Then I found this case out. It is possible to make n+1 mismatches(positions in which the bits differ) in between the pairs of the strings. Thus the final string would be of length 3*n+1.
    4
    00011111
    11100111
    01010000

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

    What about,

    000011110000 111100000000 000000001111

    BTW, Same mistake ):

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

      oh wow. thank you guys. I can't believe I made this logic error

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

Anyone, please I need help for the problem TMT Document(#715-DIV-2/B). My solution https://codeforces.com/contest/1509/submission/113289284 This solution is giving me 'runtime error, it is running fine and giving me output as normal in my IDE. I also think that I have passed the test cases.. any guess??

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

    Try for case: MMM (Cases where count of M is more than count of T)

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

      thanks, It really helped. I had just forgotten about this edge case!!

»
4 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

Speedforces :))

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

questions are really good...thank you for such good contest

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

Is there anyway to bound the maximum of minimum hamming distances of three distinct binary strings? I'd appreciate if someone can give out a proof or explain their intuition behind this. Thanks.

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

In TMT question I used counting. First incrementing count when T is found and when M is found then decrementing. Also another variable for counting m. If at anytime count becomes negative , solution is impossible. At the end I checked for if count of T == 2 * count of M. Can anyone help me why this solution was not working ?

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

I'm new here but I don't understand my solution gets TLE on test 13 of problem div2/C. To me is exactly the same solution as in the editorial (but in Python). Could someone please check? https://codeforces.com/contest/1509/submission/113305170

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

So far one of the best tutorials

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

Hi, can somebody tell me I got WA on test2(C++) in B? Code: 113309060. Thanks [Edit]: The accepted solution in Python: 113304387

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

Ari sorry if i'm wrong, but in my opinion 2D is much simpler than 2C. In D, the solution comes to mind immediately, and in 2C, vice versa.

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

    You are not wrong, but many people will disagree with you because we have tested and testers rated 2D harder than 2C :) Heck, at first we even proposed 2D as 2B since we had the same opinion as yours (you can check our comments on the problem).

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

In Div2 problem C, I understood that for every subarray we have two choices either we can remove leftmost element or the rightmost element and take the minimum out of them but why at every state we are adding s[r]-s[l] to the minimum? couldn't just we store dp[i][j]=min(dp[i][j-1],dp[i+1][j])? i didn't understand this part can someone explain this more clearly.

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

    because at evry state you already know that answer is atleast s[r]-s[l]. since we have sorted the array . Think this like you know the answer of the current length lets we have exmple n = 6 and arr = [1,3,3,3,6,6]; dn = s[5]-s[0] = 5 now dn-1 = you choose from (arr[0] to arr[4]) or (arr[1] to arr[5]) and you have to add that dn also for complete answer.

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

      ohh right now i got it, we know that for any subarray the value will be atleast s[r]-s[l] no matter how we arrange the elements we just need to find the minimum score by removing leftmost and rightmost which we have stored in the dp and add that value for the complete answer of the current subarray. thank you :)

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

Please suggest some problems like div 2 C (matrix chain multiplication). Thanks in advance.

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

Great set, even better editorial! Awaiting more rounds from you!

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

Ari, Please share with us what mistake were you doing in the first place that caused spoiler tags to overflow? Also, how did you rectify it?

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

In Problem C of div 2 could someone please explain and give a testcase why this approach fails ??? I did this and got WA on testcase 5 .

Keeping the most frequent elements in the front and if frequency of two elements are same then keep the smaller among them in the front.

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

    your approach fails on test case 1 3 3 3 9 9. According to you answer should be 3 3 3 9 9 1, which gives a sum of d's = 20. But there exists another optimal solution 3 3 3 1 9 9 which gives a sum of d's = 18. So, check your solution on this test case.

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

can somebody please tell me why i am getting tle in case 18 in 3 question if i initialize dp with 0 and ac when initiallizing with -1?

please tell me when to initialize with -1 and when with 0

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

    because dp[i][j] value can be zero ( max == min ) let any pos dp[3][6] = 0 ; Now whenever dp[3][6] will call then it will again compute. That's why zero not working.

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

Problem D Solution video in HINDI. if anyone is having any problem in understanding the problem. This video and the solution discussed might help. https://www.youtube.com/watch?v=OxueGHcZYyY

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

For this submission of div2-D https://codeforces.com/contest/1509/submission/113251552
can someone provide a small enough test case. I was able to make a test case using random generator but it was large and not useful to find mistake.And i tried to find one myself but failed to do so. So a test case or a logical prove to show that the solution is wrong would be very helpful :) .

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

    4

    10111100

    00111101

    00000000

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

      thanks, also you found it so quickly, i was also trying to make a similar kind of case but failed :(
      Also string 1 is just reverse of string 2 XD

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

        It's pretty easy to find it:

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

          Oh ok , I actually tried generating some random cases but didn't got any small case so i thought it was not possible for small cases.Now i feel estupid XD.

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

in Div2E, how to DFS on the unassigned edges ? In general, the number of unassigned edges could be up to 1e10 so trivial DFS will cause TLE

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

I solved Div2C using ternary search. Any idea for the proof. 113242501

Update: hacked

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

Let me highlight that d1D is really interesting to solve. Thanks for such a great task!

(btw, I failed to spot that d1E was indeed an attempt to 1477D - Nezzar and Hidden Permutations xD)

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

    I remember when I came up with this idea to solve your problem I was soo excited, then I saw it was wrong x(

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

why I'm getting TLE in problem C for Div2 even it working in O(n^2)? my solution

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

Thanks for such an amazing editorial

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

Can anyone give me a test case or tell me what's wrong with my solution in div.2 D

My approach was to try every possible 2 strings and greedily make a resulting string such that it contains both strings and check if its size is less than 3*n.

Submission link getting wrong answer on test 843 of test-set#6

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

DIV 1 (A) OR DIV 2 (D) Video tutorial Link: https://www.youtube.com/watch?v=-FGrj4umVR8

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

can anyone tell why my submission getting wa in test case 3 113414122

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

How to solve Div2E/Div1B recursively? or how to find the length of the first block?

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

    Let's suppose there are n elements. Then, if you place a 1 at the front, then there will be n-1 positions to fill; for 2, n-2; similarly for 3, n-3 and so on. Eg. if you put 3 as the first element, this is how the array will look like.

    3, 2, 1, ....n-3 elements

    Now, if you have n elements, then there are 2 ^ n-1 almost sorted permutations. So, if you put 3 at front, then the minimum ranking of an almost sorted permutation that starts with 3 will be 2^n-1 + 2^n-2 (because permutations starting with 1 and 2 will precede 3). Eg. 1, ...n elements (total: 2^n-1) 2, 1, ...n-2 elements (total: 2^n-2) 3, 2, 1, ... n-3 elements (total: 2^n-3).

    Thus if the k is between 2^n-3 (inclusive) and 2^n-4 (exclusive), then the permutation definitely starts with 3, and now you need to find rest of the elements of the permutation in this way recursively. Hope this clears it up.

    Btw, did you understand how the second solution works?

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

      Hey thanks for your reply! and yes I do understand how the second solution works.

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

hey in the ques of binary literature, I just compared three-string taking two at once compared all the characters and when the char were the same pushed one in another string and if they were different pushed both of them into the string. I got three strings in the end and I printed the one with the least length. But it failed testcase2 part 30 can anyone explain to me why?

https://codeforces.com/contest/1509/submission/113708604

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

Has anyone managed to solve the c problem with Python? I get always TLE on test 13: https://codeforces.com/contest/1509/submission/113919293

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

For div1 F,in Tutorial:

However, there will be cases when u→ur is actually not needed (I will call this phenomenon being hidden). What is the condition for u→ur to be hidden? That's when there's a path from u to ur with length ≥2! Suppose this path is in the format u→⋯→t→ur. We can prove that t<u: if t>u then that implies at>au but at<aur, which means the right edge of u is u→t instead. Because t<u, we can take the range [l,r] such that l≤u≤r, l is as small as possible, and check if there exists an index t∈[l,u] such that au<at<aw. That concludes the solution for finding the optimal encoding for q-permutations.

Here,I think we should check if there exist an index t∈[l,ur] instead of [l,u] such that au<at<aw. Where are I wrong?

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

    You are not wrong, it's just that we have proven that if there is such t then it cannot lie between u and ur, so we only need to query in [l, u].

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

      I don't think you have answered my question correctly.The defination of $$$l$$$ should be different.

      In my opinion,$$$l=\min_{i,[u,ur]\in[L_i,R_i]} L_i$$$

      In the tutorial,$$$l=\min_{i,u\in[L_i,R_i]} L_i$$$

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

        Ah yeah I see that's true, typo on my part. I will update the editorial.

        Edit: similar typo on second part of editorial as well :(

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

Can't think of the problematic case in div1D, can anyone provide an explicit example?

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

It is really a ****ing enjoyment to read your code for F(div2)...orz %%%%

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

if the pivot point we chose is on the convex hull of the set of points, then one of the border segments may actually intersect some other segments!

Hi, I have tried to solve problem D and pick the smallest y, smallest x point which should definitely be on the convex hull. However, it still passed the tests without encountering the case above.

Are the tests simply weak or is that case really impossible to encounter? Actually, I also cannot think of how that case should happen there should be no segment that can intersect with a border segment. Is my understanding wrong?

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Right below that, listed as one of the workarounds: "Always choose the bottom-most and left-most point as a pivot. This makes this potentially troublesome segment predictable, and also allows us to slightly simplify the angular sorting code." That's exactly what you did.

    A segment can intersect with a border segment if, for example, you have a square ABCD, you choose A as pivot and your sort by angle puts B and D next to each other(for example, by sorting like C(0°),B(45°),D(315°)).