Теперь раздел EDU доступен и на английском языке ×

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

Автор vovuh, история, 12 дней назад, По-русски,

<almost-copy-pasted-part>

Привет! В 28.06.2020 17:35 (Московское время) начнётся Codeforces Round #653 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье ZeroAmbition Степановой, Михаилу pikmike Пикляеву, Максиму Ne0n25 Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда. Также спасибо Артему Rox Плоткину и Дмитрию _overrated_ Умнову за обсуждение идей и тестирование раунда!

Удачи!

</almost-copy-pasted-part>

UPD: Также спасибо ma_da_fa_ka за тестирование раунда и отдельное спасибо Дмитрию _overrated_ Умнову, Артему Rox Плоткину и, конечно же, Михаилу MikeMirzayanov Мирзаянову за обсуждение идей и помощь с подготовкой раунда!

UPD2: Разбор опубликован!

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

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

Vovuh orz!

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

This is missing from the announcement after everyone thought our man vovuh retired...

You know I'm back like I never left (I never left)

Another sprint, another step (another step)

Another day, another breath (another breath)

Been chasing dreams, but I never slept (I never slept)

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

This has been happening in the last couple of months :)

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

vovuh is back baby!!!!

»
12 дней назад, # |
Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится
At last vovuh come back in div-3 with his interesting problem-set. We missed him 2 continuous div-3 contest.
#650(He was not there) And #644(Just in the tester list).

Edit: Ok. Only vovuh fans missed him And I am one of them.

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

vovuh — Is not just a name, it is an emotion

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

Missed you Vovuh ❤❤

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

div3 by vovuh are best

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

 vovuh again!

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

I am not able to register for the contest. When I click on the CONTESTS options above, I am able to see only ICPC challenge 2020 registration option.

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

I don't see any difference between vovuh problems/non-vovuh problems.

»
12 дней назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
  • No One:
  • Literally No One:
  • Not Even A Single Soul:
  • Not even Codeforces:
  • vovuh fans: "Vovuh orz!!!!!!!!!! vovuh is back baby!!!! Missed you Vovuh ❤❤"
»
12 дней назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
  • No one:
  • Literally No One:
  • Not even a single Soul:
  • Not even codeforces:
  • VOVUH fans: "Vovuh orz!!!!!!!!!!!! vovuh is back baby!!!!! Missed you Vovuh ❤❤"
»
12 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

yOOoooOOooOOooOOooooOO

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

Vovuh orz!!!!!!!!!! vovuh is back baby!!!! Missed you Vovuh ❤❤

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

Starting RN I'm gonna explain my family members to keep quiet during 8:00 — 10:00 Tomorrow ! Maybe they'll understand this time

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

Vovuh : "The man the myth the legend !"

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

Div-3 and vovuh perfect combination.

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

Finally vovuh is back :)

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

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

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

This comment has been deleted due to negative feedback!

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

I don't know about this man vovuh but going through these comments makes me feel there's a good contest ahead ! Wishing it's true ... All the best to all participants

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

meanwhile vovuh counting all the money he made setting div 3 contests!

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

MikeMirzayanov No more Div.4 rounds?

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

i love doing contest set by vovuh, thanks and keep giving us more contest

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

I can nearly always solve div2 C but I can't solve div3 D should div3 D be harder than div2 C ?

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

Does Div-4 contests are discontinued?

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

vovuh The king!

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

Cringe overloaded

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

meme

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

pls can someone tell me what happens in hacks ?

  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Div-3/educational round Hack phase :
    suppose think. A test can fail a problem .But that was not in the pretest system case.So that problem showed accepted..Then anyone can hack that problem by that case in the 12 hours hacking phase.And the defender no of solved problem-=1. But hacker did not get any point.
    
  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Once the contest ends you can see anyone's solution and if you think that in certain test cases this would fail then you can run against it and it is called hacks. If it was successful you get 50 points(depends on round) and if it wasn't you lose certain points and before hack you have to lock your solution.

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

Всего наилучшего

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

who the hell is mike ,here

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

I know here is not a good place to ask this question but what happened for div4 contests ??

are they removed from codeforces contests or we can see them back soon ??

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

For how much time this server is open

This is my first contest

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

It is high time to introduce filters to comments section on codeforces -_-.

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

Good Luck.

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

Harder than usual div 3 :)

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

The gap between E1 and E2??

»
11 дней назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

subho_01santra I think you are expecting a blog from me. I will do it for you, with proof.

Gotcha ;)

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

How would you prepare for the interviews or FAANG if you have just 1 month left keeping in mind you have decent knowledge and grasp over DS Algo and have done more than 100+ questions on leetcode ?

Any help would be much appreciated! Thank you :)

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

Help me with D after the contest...

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

    D problem was giving TLE when i used unordered_map and when i changed it to map it got accepted. You just have to calculate the minimum number which we have to add to the numbers of the array after which they are divisible by k.

    This can be calculated by taking mod.

    for example the numbers are 5,1,3,4 and value of k = 3

    so for the first element we need to add 1 to get the divisible number

    this number can be calculated by taking mod of a[i]-k & k.

    -> (k + (a[i]-k)%k)%k;

    now similarly for other numbers also we'll calculate in the same way so -> 1,2,0,2 is the required array.

    Now Notice that at a time we can select only one element from the above calculated array. It means that when we see 2 or more elements of same type we can't give the same x to them.

    It means we have to calculate the next greater number which must be added so that the given number is divisible by k.

    the next number can be calculated by multiplying k with the number of times this number has previously occurred, which means we have to maintain the hash table for it.

    Your code here...
            long long int n,k;cin>>n>>k;
            long long int a[n],maxm=-1;
            for(int i=0;i<n;i=i+1) scanf("%lld",&a[i]);
            
            map<long long int,long long int>mp;
            vector<long long int>rem;
            
            for(int i=0;i<n;i=i+1)
            {
               long long int val = mod(k-a[i],k);  // taking mod and storing it.
                if(val)rem.push_back(val);
            }
            for(int i=0;i<rem.size();i=i+1)
            {
    
                long long int val = k*mp[rem[i]] + rem[i];
                mp[rem[i]]++;
                maxm = max(val,maxm);
                
            }
            maxm++;
            printf("%lld\n",maxm);
    
    • »
      »
      »
      11 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Nice, Thank you.

    • »
      »
      »
      11 дней назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      D problem was giving TLE when i used unordered_map and when i changed it to map it 
      got accepted.
      

      Wow, just tried this and confirm the TLE with unordered_map. Does anyone know why this happens?

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

        unordered_map worst case is linear, so you can assume that your algorithm time complexity is O(n * n) in some cases

        don't use unordered_map when it's not needed and you can solve the problem with map :)

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

        same happened with me in problem D

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

      You have not initialized the map but used, does it automatically return zero or I am missing something?

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

    My approach:

    for all the array elements calculate the value required to make it a number divisible by k and store it in map and keep incrementing its value if it repeats.Then, find the max "value" in the key-value pair and ans= key+(value-1)*k+1. If two keys have the max value, take the max key.

    eg: second example, 5 repeats 3 times. so ans= 5+(3-1)*6+1=18.

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

      Can you explain why this works ?

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

        To make a such that a%k==0 you have to increase a by k-(a%k). Now if there is another element with the value of a , minimum increment to make a%k==0 is k-(a%k). But according to statement we can not choose multiple indices to increment by same x. So the next minimum value is k-(a%k)+k. If there is another element with the value of a then we have to increment it by k-(a%k)+k+k. So generally,

        required minimum increment for a value 'a' = k-(a%k) + (frequency of a - 1)*k

        Maximum of these value for each distinct element is the optimal answer. (As values of other element are less than the answer we can increment them accordingly on the way to the answer )

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

          thanks ...well explained

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

          I think your this approach might not work.

          Consider the case 2 6 3 9 for 3 the minimum required increment = 3 for 9 the minimum required increment = 3

          And max of (3, 3) will give 3.

          But the answer here would be 9

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

            Yes. I'm sorry i forgot to mention a really important thing. when calculating the frequency of each element we must take the mod of them. Because as in your case the increment needed for both 3 and 9 is 3. As we are focusing mainly on the x (increment) 3 and 9 is same for us. (3%6 = 9%6 = 3).

            Then the answer would be,

            6 - 3 + (2 - 1) * 6 = 9

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

      I did the same but I got wa!

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

        Kindly see the above reply you will get the test case where your approach might be failing

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

    https://codeforces.com/contest/1374/submission/85372487

    Isn't this linear ... why it's giving TLE?

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

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

Now I see why vovuh rounds are so amazing. Thoroughly enjoyed the round!

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

Easy solution to E2: Copy a solution to this problem https://codeforces.com/contest/799/problem/E which is the exact same except you don't have to reconstruct the indices. Then add boring code to reconstruct the indices

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

    nice, 2500 problem for div3 contestants

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

    I tried that but I was failing at test 12. Well if this worked for you then I definitely made some really stupid mistake.

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

https://ideone.com/oNqhoj

My code is obviously wrong (fails sample test case 2 lol).. But I spent more then an hour can't find where my logic is wrong :/.. I'm almost convinced my 24 IS the correct answer haha..

Any help is appreciated. (Would be awesome if you don't spoil the problem but hint me where I went wrong)

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

    Try this test case

    1
    5 38
    15 29 7 15 7 
    
    

    Edit: answer should be 70. Your code gives 108.

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

      Ty! I finally was able to get rid of WA but then I was struck by TLE :(

      https://codeforces.com/contest/1374/submission/85394497

      Could you identify my bottleneck ? I think the solution is nlog(n) and should pass ..?

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

        Your code has worst case complexity of O(n^2), having worst case when all elements are same.

        See this part in your code

                for(int i = 0; i < n; i++) {
                    if(arr[i] == 0)
                        continue;
                    while(myset.find(arr[i]) != myset.end())
                        arr[i] += k;
                    myset.insert(arr[i]);
                }
        

        For each iteration of inner loop, it will search multiset the number of times value of arr[i] has appeared before in the array. if n same elements have appeared before, then inner loop runs n times, giving complexity of O(n) for inner loop. The outer loop runs n times, giving total complexity of O(n^2).

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

Hints for F?

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

    Just simulate. If it does not end in correct ordering, then do one triple swap including two same elements from a[]. The simulate again. If still not correct ordering it is impossible.

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

      Thanks for the solution! I thought of this solution, but I am still figuring how to prove that it will be impossible, in case both simulations fail.

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

        Seems that it does not work good :/

        Here is the submission of #1 85347474 He does count invariants, and if odd parity, does one swap in two same elements.

        Then sorts with triple swaps, but including the indices in comparison, which does not change the order of elements, but makes the parity even.

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

        The idea behind proving whether it is possible/impossible is based on the following idea:

        Define f(P) for some permutation P to be the number of pairs of indices (i, j) such that i and j are the 'wrong way round' — that is, i < j but in the permutation p, j is to the left of i.

        For example if n = 4 and P = {1, 2, 3, 4} then f(P) = 0. f({2, 1, 3, 4}) = 1 and f({4, 3, 2, 1}) = 6 (everything is the wrong way round).

        We claim that each cyclic shift is invariant mod 2 for f(P) — that is, f(P) will change by -2, 0 or 2 with each shift. This is because if [a, b, c] --> [c, a, b] then the pairs (a, c) and (b, c) have reversed (now a, b are to the right of c when before they were to the left). So since there are two changes, then f(P) goes up by 2, stays constant or down by 2.

        This also explains why we need to do two simulations — if two elements in the original array are the same, then we label them (x, x') in one simulation and (x', x) in the other simulation. Then for the starting configuration, f(P) will be odd for one of them and even for the other, and at least one of them should work.

        From this we can conclude that it's impossible if both below conditions are met:

        • there are no duplicate elements (otherwise by the above, at least one of the x, x' or x', x should work)
        • the original permutation has f(P) odd (then it can never reach 0 since it's always odd)
»
11 дней назад, # |
Rev. 8   Проголосовать: нравится -26 Проголосовать: не нравится

The tasks is interesting!

Problem A: Result: ((n — x) / x) * x + y

85303459

Problem B: n = 1 => impossile (0) n >= 1 impossible n <=> n * 2 ^ x = 6 ^ y (x >= 0 and y >= 1)

<=> n = 2 ^ (y — x) * 3 ^ y Therefore condition is exp (2) <= exp (3) and n (that time) != 1

Result: x + y = 2 * exp (3) — exp (2)

85350815

»
11 дней назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Really enjoyed this round. hail vovuh

»
11 дней назад, # |
Rev. 3   Проголосовать: нравится -19 Проголосовать: не нравится

Deleted

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

What's the limit for compilation time? I submitted my code for E2 nearly the end of contest and got this verdict. "Can't compile file: Compilation process timed out." I guessed the reason is that my code is too long, but I don't think I can make it significantly shorter. Do you know how to make it compile?

85381670

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

    I don't think your code is too long xD https://codeforces.com/contest/1373/submission/85026680

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

    We don't specify the exact time limit for compilation, but your solution can't be compiled on my laptop in 30 seconds or even in 1 minute. Probably, it is a bug of GCC or how your solution is written. Try to fix it and submit again.

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

      I manage to make it compile now. Thanks for reply! The reason is I wrote this in my segment tree code.

      node sg[nax << 2] = {};
      

      erase "= {}" part fix the issue. I write this since I think it can prevent UB sometimes, probably it causes me UB this time...

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

Can someone tell me where my code is wrong for E1? https://codeforces.com/contest/1374/submission/85384974

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

    what if they only read from both books. what would be your answer, you will print INT_MAX which is wrong

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

      so add this to your code

      if ( k < both.size() ) ans = both[k] ; 
      
      • »
        »
        »
        »
        11 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you give an example test case? I'm not sure I understand what you are saying because the loop would take care of the case where they read from both books (when i = k)

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

          check out this case, you code will produce negative value. because $$$k - i$$$ is negative and you index the vector with negative indices.

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

    what if both is empty?

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

Please a fast editorial , i need to upsolve

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

What is the test 4 of problem E like ?

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

Really not enjoy Math-intensive problems... I suggest every contest (especially for DIV3) add a Math index to indicate how much questions are Math-related.

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

What is the test 4 of problem E like ?

I tried to use priority_queue a(only a like), b(only b like), c(both a and b like)

Then with ca(number of chosen a), cb(number of chose b)

  • If (ca < k), I will take min if exist (a.top() and c.top())

  • If (cb < k), I will take min if exist (b.top() and c.top())

  • If (c.top()) is selected I will increase both (ca) and (cb) else I only increase 1 (a.top() -> ca and b.top() -> cb)

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

E2 would have been better easier if it didn't have to traceback indexes.

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

    If you really think so, then try this

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

      Hi! Thank you so much for sharing the problem! It feels good to know my approach for E2 was correct!

      Though had to add a few extra steps because of coordinate compression.

      Here's my submission for 799-E -- 85410030 (solved using two BITs , same as E2)

      Although my thought still remains, tracing back through BIT would have sucked :p

      Thanks!

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

What a huge implemention on E1.

Three pointers and so many if-else, I am about to not to solve it. Luckily, before the end of the contest I finally solved it by huge implemention :), hope not to be FST.

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

    I think instead of using 3 pointers, you can just iterate over how many books are you taking which Alice and Bob both like. Then it is obvious that you have to take k — (both likes) books from 1 0 and 0 1. Just precalculate the prefix sums.

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

      I have done the same but it gives WA on test case 5. can you please check it 85387758
      upd : missed case (0,0)

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

        Instead of else b.push_back(t), you have to use else if(B==1) b.push_back(t)

        Because you are also pushing 0 0 values into b, where no one likes the book. Instead, you should push 0 1 values into b, where Bob likes the book.

        I slightly changed your code according to the above logic. Check 85389515.

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

      Yup, there are many ways to solve E1 with easy implementation. You can even just take the minimum number of commonly liked books initially, then keep replacing the two longest individually liked selections with the shortest one commonly liked one remaining if it makes the answer better.

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

    You could have implemented it directly using priority queue, one for each of the possible cases.

    Then greedily go through the input :)

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

    Hi! I think the approach for E1 was fairly straighforward. (maybe)

    I stored time for (0,1) , (1,0) and (1,1) in different arrays and sorted them by non decreasing order of time.
    Also we don't need to store (0,0) (why?)

    Say we can take x amount of (1,1) then we know we have to take k-x from (0,1) and (1,0).

    Let's iterate over all possible case of x and the minimum possible time is answer.

    Here's my submission : 85342055

    Thanks!

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

      shit... I didn't consider the x factor. I knew that taking all of both would be wrong but then I went into some other direction.

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

      Thanks. Best solution for me at least.

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

      Tried doing something different but on the same lines

      Took Three separate vectors for (0,1) , (1,0) and (1,1) , and sorted them

      Then took a variable which would store the answer , Now

      Iterate over three vectors at the same time , keeping variable i for 1,1 and j for 0,1 and 1,0

      if time amount of (1,1) at i is greater than time amount of ((0,1) + (1,0)) at j then add (0,1) + (1,0) at j and j++ else add (1,1) and i++

      But getting WA on test 8

      Here's my code 85373064

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

        My implemention is:
        1. Can (1,1) replace (0,1)+(1,0)?
        (1) (1,1) <=(0,1)+(1,0)
        (2) One of them run out of their "own like" set which means the book only he likes, but he still needs to read book, so just put (1,1) dont need to check anything.
        2. Can (1,1) replace (0,1) or (1,0)
        In this situation, one of them has got k books to read but the other is not. Just check (1,1)<=(0,1) or(1,1)<=(1,0), then just choose (1,1)
        3. Otherwise we just choose the book in their "own like" set
        PS: we also have to check whether the set (1,1) has run out, if so we just go to 3, and get the number of books we need, because we have checked the exist of answer before, which is put all the referenced books in the shared set and check whether both of them have k books to read.

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

          Thanks for the answer , but I dont think you saw my submission

          There was only one typo in a loop (wrote i instead of i1) and Nothing wrong with the logic , got AC

          Iam not completely sure if I understand your 2nd point though

          Thanks for the effort of commenting though

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

      I have also done similar thing. Here's my video Editorial for E1 Video Link

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

    You overkilled it.

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

How to Solve F ?

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

Why am I getting TLE on test case 8? 85389867

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

D: Could someone please tell why this is giving TLE?

http://codeforces.com/contest/1374/submission/85383846

inline bool c(ll a, ll b) { return (a >= b); }

int main() { ll t; scanf("%lld", &t); while(t--) { ll n, k; scanf("%lld %lld", &n, &k);

ll p = 0;
unordered_map<ll, ll> mxx;
for(ll i = 0; i < n; i++)
{
  ll x;
  scanf("%lld", &x);

  x = x % k;
  if(x == 0)
    continue;

  x = k - x;
  mxx[x]++;
}

for(auto i: mxx)
{
  ll v = i.first + k * (i.second - 1) + 1;
  p = max(p, v);
}

printf("%lld\n", p);

} }

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

I see C easier than A ;) :v

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

    It seems to me also.

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

    Can you explain me C I feel so stupid :(

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

      Here check out my video solution. It is time stamped so just skip to C.

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

      the input is string with only opening and closing brackets, strings like () , (()), ()(())() are regular strings but there are some inputs not regular your task to count the minimum moves to make it regular , for example: )( here you need one move to make it regular , ))()()(( here you need two moves to make it regular right :) and so on... I hope this is useful for you, and don't say stupid again i hate this word, no one stupid, there are some can understand from first time and others after two or more times just practice more that's make you very fast for reading and understanding problems , Good Luck ^_^

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

      Its a standard question of matching brackets. Google it you'll find it

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

https://codeforces.com/contest/1374/submission/85372487

I think this solution is linear. Anyone explain the reason for TLE?

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

Why am I getting TLE in this submission for Question D? My Submission

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

»
11 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
For D ,Even O(n*t) solution is resulting in TLE , Is there still any scope left for improvement in my code .

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

    using map instead of unordered_map, got it Accepted, But could anyone pls explain why did it happen?

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

      Don't use unordered_map or unordered_set they blow up for certain inputs , if you want a detailed explanation read this blog

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

      Check out this blog. Basically, unordered_map offers constant time operations on average when it is known that the inputs are fairly randomised. However, it is possible to make test cases such that collisions become very likely, resulting in linear time operations, thus blowing up complexity.

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

What's wrong with this code. (Problem D) It gives MLE at test case 5. Thanks in advance.

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

    because you create many map keys. For Example fre = {{1, 4}, {100000, 3}}, k = 1000000 You are created keys 2, 3, 4 .... 1000000. if(fre[num] > 0) created this keys

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

      Thanks got it.

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

        You must refer to the next element. By the way, such a solution will not work even in time. use binary search to find the element closest to the current element x. After it has reached the required value. So the asymptotic will become nlog (n), not kn

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

How to solve D if the first operation can be performed any number of times on each $$$i$$$.

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

    Pls do not bother about it

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

    You mean [k = 3, a = {2, 2, 2, 2}]?

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

      I mean let's say $$$k$$$ = 4 and $$$a$$$ = $$$[1,4,8]$$$. In original problem answer would be 4 because we can perform operation $$$a_i = a_i + x$$$ on a particular $$$i$$$ at most once. How to solve it if we can perform it any number of times. Like in this case answer would be 3 as we can perform $$$a_1 = a_1 + 1$$$ and $$$a_1 = a_1 + 2$$$.

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

    If x is answer to the current question, then an O(x).k solution can be easily found for the modified question. We maintain a frequency array of size k, to store the remainders and another frequency array of size k to store currently available remainders . While processing x, we can check if it can make a remainder which is needed, and we can modify accordingly.

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

    I initially didn't read that line and was getting hopeless. I mean there won't be any fast algorithm, I have a felling that there won't be any polynomial time algorithm

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

My A, B, C, D, E1 solution`s
A: 85388328
B: 85388390
C: 85388427
D: 85388457
E1:85388485
If you have questions regarding the logic of the solution or the principle of the code — write here

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

    Why am I getting TLE in this submission for Question D?My Submission

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

      Because worst case time complexity of unordered map in order of n . Solve it by using map

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

      I didnt fully understand the reason, but its in unordered_map. Use the common map and it will work. I will now try to understand why you cannot use unordered_map.
      P.S. I understood the reason. In some cases, unordered_map works for a long time

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

    E1 -> simple and easy implementation. Should have clicked this.

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

    In E1, is it always necessary to take A and B in pair?

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

      Yes. Since we write the values ​​in set, this will be the most profitable solution.

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

Tutorial of problem C: First, solve this, then assume your output is $$$ans$$$. Now, back to C, and print $$$(n-ans)/2$$$ for each testcase. I wish I've made a clear solution and stay tuned for my YouTube channel :'D

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

Can someone help me in finding bug in my E2(Hard Version) solution?
Here is my solution 85387601
It is failing in 12th test case. Thanks in advance.

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

    Our solution seems to have the same idea. Even my solution is failing on test 12, with the same answer. If someone could help it would be great, thanks

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

Can anyone please tell me what's wrong with my solution in E2??

giving RE on test case 5.

https://codeforces.com/submissions/Lord_Saga

»
11 дней назад, # |
  Проголосовать: нравится -62 Проголосовать: не нравится
Question D should be rejudged , as it has extreme time limits , there are people who used map , passed their tasks , while i got TLE using unordered_map , which is faster .

In O(n*t) time limit , even the time complexity to take input is O(n*t) , there is no way my solution should fail . Definitely , There is a big scandal behind all this . We want Enquiry.

Hope , Mike sir will look into this matter .

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

    Unordered map can run in O(n) per query in the worst case if there are enough collisions. It is trivial to generate cases that cause such behavior for unordered map without custom hashes and would make the solution run in O(t * n ^ 2).

    CF blog that discusses this.

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

    "Definitely , There is a big scandal behind all this"

    Maybe in your mind.

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

    unordered maps are not always faster than maps, as ordered maps can take anywhere between o(1) to o(n) for indexing while maps always take o(logn).

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

    So, How come don' I see any attempt at this contest in your account?

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

      Here is my code , i did on my real account . It passed with map as suggested in above comment . I was not aware about blowing property of unordered map .

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

what a bad day for me, my rating continously decreasing from past 4-5 contest and my current rating is just 1615 and this contest is unrated for me in which my rank would be in top 10. hope this would never happened to anyone

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

is vovuh from BTS?

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

I'm going to assume that my solution for problem E2 using treap is not the intended one, because that would be very weird for a div3 contest. But I usually try to kill a mosquito with a bazooka during contests, so I'm sure that there is a simpler and nicer way to solve the problem :P

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

    Can you please explain your treap solution?

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

      Fix the amount of books of type 1-1 that you will take. You can calculate how many books of type 1-0 and 0-1 you will need to force that both people have at least k books. Obviously, you will take the ones that have lower cost for each group of books. This works for E1.

      Now for E2, you should keep the same strategy, but maybe you have to use a few more books to complete the M books you need to take. But both people already have at least K books, so you can take any other book you want (even if it is a 0-0 book). Obviously, you will take the smallest amount of books you need (let's say X). Here is where treap comes up to help us: you can use it to calculate the sum of the first X smallest values in the remaining books that you didn't take before.

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

        but why didn't u implement it??????

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

          You can see my submission during contest here :)

          If you are looking for a clean implementation, don't even waste time with my code. I was on a hurry because the contest was reaching its end, so I had to code everything quickly :P

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

        But how do you save the indices of solution set of books? I could calculate the minimum answer using set, but couldn't figure how to find the indices of final answer.

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

          You can keep track of the number of 1-1 books in the optimal solution, sort the unchosen books, and take the smallest m-k books, print them along with the chosen books

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

Can someone explain how to solve E2? I saw some people using treap to solve the problem.

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

    I think the main part of this problem is how to find k-smallest elements sum. Usually you can do this by binary search tree, so treap can do the job. The easiest way to implement for me is to use segment tree that each node store pair of (number of element, sub of element) in subtree. To get sum of k-smallest elements. Check if left node size greater than k or not. If yes, try searching on left subtree, otherwise subtract sum of left subtree and search on right subtree. Fenwick tree can also do the job if you keep two fenwick trees that one store sum and one store number of elements and use binary lifting or binary search to find sum of k-smallest elements.

    I saw many people solve using priority_queue or multiset, but I don't know how it works though.

    Edit: I think I get it now. It’s similar to finding median by priority_queue or multiset. Notice that k is always increasing. So you can simply do the same thing. When you encounter query, just transfer elements between 2 multiset respected to value of k. The total number of operations will still be $$$O(n)$$$

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

Thanks for this contest! Through this contest, I realized that my implementation skill is very very weaker than others In F, I observed the main idea very quickly, but that is all.. I failed to write accurate code...

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

https://codeforces.com/contest/1374/submission/85392451 its showing TLE for using map also. pls someone find the fault.

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

Can anyone tell me why I am getting this runtime error in TC 5 for E1 ?
Link for submission — https://codeforces.com/contest/1374/submission/85375093
I am pretty sure this has to do something with my comparator function for sort but I cannot figure it out.

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

Can someone help me with D? I am not able to understand what's wrong with my code. Main logic below

lli == long long int

        lli mx = 0, mxval = 0;
        map<lli,lli> mp;
        while(n--)
        {
            lli x;
            cin>>x;
            if(x % k == 0) continue;
            lli diff = (k - x%k)%k;
            mp[diff]++;
            if(mp[diff] >= mx)
            {
                mx = mp[diff];
                if(diff >= mxval)
                    mxval = diff;
            }
        }
        if(mx == 0 and mxval == 0) cout<<0<<endl;
        else cout<<(mx-1)*k + mxval+1<<endl;
  • »
    »
    11 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You should skip elements with diff = 0.

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

    Seems that the mistake is in:

    if(mp[diff] >= mx){
        mx = mp[diff];
        if(diff >= mxval)
            mxval = diff;
    }
    

    You can do this instead:

    if(mp[diff] > mx || (mp[diff] == x && diff > mxval) ) {
        mx = mp[diff];
        mxval = diff;
    }
    

    The reason is that if mp[diff] > mx and diff < mxval you are not updating the mxval but you must do it.

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

      Can you explain why I should update mxval when mp[diff] > mx and diff < mxval. Cause mxval should also be 'max' right? so should be update when mp[diff] >= mx and diff >= mxval

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

        You need to take the maximum mp[diff] no matter what. Then, over all the diff which have the maximum value mp[diff] you should take also the maximum.

        Consider this case:

        3 3
        1 2 2
        

        Correct output: 5.

        That is because the correct results are mx = 2 and mxval = 1, but in your code it gives mx = 2 and mxval = 2 which is incorrect. If you still don't get it just do the simulation by hand.

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

          Hi, I was able to solve the question now. What a stupid mistake from my part. Thanks so much for your help :)

          Also I saw you became Expert after this round, congratulations!

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

Here is my screencast of this contest, do check out it :)

Link: https://youtu.be/afn_V7YkX3U

On my channel I do educational content, so if you want to improve, make sure to subscribe to the channel!

»
11 дней назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

My solutions for A,B,C,D,E1
A -> A
B -> B
C-> C
D -> D
E1 -> E1

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

Can Anybody explain me C please

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

    Keep a counter, initialised to zero. Traverse through the string now, whenever you encounter ( counter++, otherwise counter--

    Now if the counter becomes negative at any moment l, it means that you have a extra closing bracket, in this situation move it to the end of the string. This approach will ensure that every opening bracket is matched to some closing bracket. And also set the counter to 0.

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

    Suppose you have variable $$$bal$$$ which stands for balance. We go through string from left to right, if we have $$$"("$$$ now then do $$$bal+=1$$$ and $$$bal-=1$$$ if we have $$$")"$$$. The answer is the global minimum value of $$$bal$$$. For example $$$s=)))((((())$$$, then balance will be $$$-1, -2, -3, -2, -1, 0, 1, 2, 1, 0$$$. The most minimal value of $$$bal$$$ was -3, thus the answer is 3. So you can fix the sequence by 3 moves. You can take 3 rightmost opening brackets and move them to the front of the string. So string $$$)))((((())$$$ will become $$$((()))(())$$$.

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

      Hey so will the deformation always occurs in the form of )))(((, can ) or ( appear in between balanced sequences. Cause I'm unable to concretely prove it. Thanks!

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

        not always, you can get string like $$$)())())())(((($$$ answer is 4, and you take last 4 opening brackets and move them to the beginning, you will get $$$(((()())())())$$$

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

    You can use stack by popping the perfect brackets and keeping the length of unperfect brackets and print the answer by dividing the length of the stack

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

How to solve problem D ?

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

Kindly explain statement of problem E1.

»
11 дней назад, #