Автор awoo, 4 года назад, По-русски

Привет, Codeforces!

В 27.10.2020 17:35 (Московское время) состоится Educational Codeforces Round 97 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.

Удачи в раунде! Успешных решений!

Поздравляем победителей:

Место Участник Задач решено Штраф
1 Um_nik 7 149
2 jiangly 7 193
3 hank55663 7 214
4 neal 7 231
5 uwi 7 250

Было сделано 205 успешных и 712 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A Drew_is_me 0:01
B Drew_is_me 0:03
C IgorI 0:03
D xb0nS 0:09
E vinfat 0:17
F SunshinePie 0:28
G tfg 0:13

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

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

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

Is it only me or other people also feel that educational rounds are harder than div2 rounds(considering they have more number of questions)?

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

    +1

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

    I know it would be controversial, coming from a newbie, however adding a point system in Educational rounds similar to Div2 rounds, but in a compressed manner, would have fared better. Experts would have focused on harder problems upto their level, while the newbie/pupils start from the easier ones and gradually peaking up...

    The current system follows the number of solved problems and time penalty. While it's not bad, but why not something similar to Div2 round point system?

    Apology in advance, if I am missing some obvious reasons.

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

      I just see this as a different kind of Div2 event.

      There are Div2-only rounds (not Div1+Div2), which follow the said scoring system. This is just another way of scoring. I don't see why Div2 can't have both formats.

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

*Во вторник)))

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

[cf comment sections these days: no offense ](cf)

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

    I don't know why but it turns out that the people are desperate to make my situation as the meme guy lol!

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

One more Educ from awoo!

Hope, that Educ will be as good as last one from you)

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

    The comment is deleleted)))

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

      Ikr, and this actually defeats the purpose of 'comment section', it should be used to express your opinion or thoughts but those comments are often downvoted

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

can I go to 2000? :)

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

can i go to 2000 rating QAQ

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

Is it rated ?

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

why does people love spamming CF announcements with "is it rated?" it's so annoying & frustrating !

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

comment deleted, figured it out

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

6 minutes left time to be ready : )

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

Upvote if you lose some rating because of this round :(

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

Мое решение задачи G скомпилировалось и дало правильный ответ для претестов на моей машине, но в проверяющей системе оно вывело неправильный ответ(.

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

In one of the examples, the range of cans that the customer could buy was between 3 and 4. How could we sell a pack with 5 cans to him (according to explanations?

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

    If the customer wants 3 cans 5 // 3 is 0 3 % 5 is 3 so the customer will buy 3 cans one by one which is smaller than 5/2 = 2.5

    (same thing if the customer wants 4 cans)

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

Wtf is pretest 2 in C

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

    If you did greedy, it wont work.

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

      Its DP. Difficult but very nice kind of DP!

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

        DP wasn't difficult. The difficult part was to prove that DP works.

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

          Isnt the very notion of dp would work in every problem even if it greedy (ignoring the part that dp solution would very slow relatively)

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

            How do you know that you can only assign it increasingly? Why isn't there a case that a number with ti=4 is placed at 2 and then one with ti=3 and then one with ti =4 snd then more values.

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

              I agree but I think the more hard part was to come up that its dp not greedy, which I did not during contest

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

              The proof was the constructive part. To me, constructive logic comes more easily than the DP part. The DP wasn't difficult, yes, but it took a lot of time for me to realize that it can be done by DP :(

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

How to solve C ? My greedy solution didn't work :( .

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится
    Spoiler
    Brief Explanation

    Submission

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

      I struggled with C, but the moment I read knapsack I instantly had the solution.

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

      can you explain the base case? why you check time <= 2*n + 10

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

        since the cooking time lies between 1 to n (inclusive); so for every T > 2*n you will have difference of at least 'n' for each dish . which will make the answer worse .. so there is no point in going ahead of 2*n .

        PS:- he has kept additional 10 minutes for his convenience .

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

    it's dp. look at constraints, they gives hint in itself.

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

    You can solve using Dynamic Programming . Sort the given array . The corresponding array of times will be also sorted and will be of size n .

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

    $$$dp[i][j]$$$ — min answer having placed the first $$$i$$$ dishes in the first $$$j$$$ minutes.

    First lets sort the dishes in non-decreasing order of $$$t_{i}$$$ so we can iterate on time in ascending order.

    $$$dp[0][0]$$$ is clearly $$$0$$$.

    Clearly at any state (where $$$i \lt n$$$) we can place the dish now, in which case $$$dp[i + 1][j + 1]$$$ = $$$min$$$($$$dp[i + 1][j + 1]$$$, $$$dp[i][j]$$$ + unpleasantness), where unpleasantness is of removing the $$$i$$$-th dish at the instant j or $$$abs(j - t_{i})$$$.

    Or we can just not place it, in which case, $$$dp[i][j + 1]$$$ = min($$$dp[i][j + 1]$$$, $$$dp[i][j]$$$)

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

      Apologies in advance if my comment seems stupid. I used a similar logic as yours. However, my dp[i][j] represented the optimal cost if time taken is i and the no. of objects picked are j, i represented the time and j represented the number of elements picked. so my dp transitions were dp(i,j)=min(dp[i-1][j],dp[i-1][j-1]+mininum of abs(A[k]-i) provided k is permitted. I have stored permitted ks in a vector of unordered_maps. However, I am getting WA. Can you please explain where my approach goes wrong. Thanx in advance.

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

      I believe the 2nd equation should be dp[i+1][j+1] = min(dp[i+1][j+1], dp[i+1][j])

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

        Oops, yeah it should have been $$$dp[i][j + 1]$$$ = min($$$dp[i][j + 1]$$$, $$$dp[i][j]$$$), since we don't place a dish in this step. Thanks for pointing that out.

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

      How do you get this good of a intuition with DP? It seems so obvious when someone tells use this DP and during the contest I cannot think of any transitions or states.

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

        once you master Recursion.

        then just by adding few lines of code you can code TopDown Dynamic programming(recursion + storing answers at every recursion call).

        and if you starts with base case and use recursion logic, like how the solution builds up in call stack, you will be able to figure out BottomUp Dynamic programming.(base case + iteration)

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

      can we solve it using dp but without sorting the dishes?? i think this question would become like max biparate matching with one end as time and other as dishes.

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

.

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

    Dynamic Programming!

    Sort the intitial oven times

    Try giving time t to current index i note their absolute difference move forward for the remaining suffix and find the minimum sum of absolute difference of timings it can be done using bottom up dp easily.

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

How to solve B ?

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

    .

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

      But why does it work?

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

      What is "group of contiguous unordered elements" here?

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

        .

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

          The code is clear, but I still got no clue why this gives answer.

          In this 96877997 there is an explanation based on pairs "00" and "11", and the number of such pairs. Somehow that relates to your explanation, does it?

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

            .

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

              Ok, thanks!

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

                I solved it in a similar manner, but ig the approach was kinda more logical..

                We can assuredly say, that any set of consecutive characters cannot be allowed.. Also, we can argue that k 1s are incorrectly placed only when k 0s are incorrectly placed as well.

                So, we just have to count the set of incorrect occurences. And it would require half steps to correct them.

                One of the ways of doinng so can be to count the consecutive set of characters+(bool)(s[0]==s[n-1]).(Since in an even lengthed sequence, they cannot be same..) You can check my submission here for reference-96899666

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

            Let me try. Let's divide the string into : S = "A" + "B" + "C".
            A = alternating
            B = not alternating
            C = rest of the string
            Here B can either be a series of 1s(111..) or 0s(000...). We are going to pick a substring D = "B" + "some part of C" and reverse that. B = 111 then D should end at some position i such that s[i] = 0. you keep the first 1 of B, so "111" becomes "1 + 010... + 11". And we are going to do it again and again. So if you analyze at the end we will have
            S = "X" + "Y" + "Z" where,
            X = alternating
            Y = series of 1s/0s
            Z = series of 0s/1s (opposite of Y)
            And at the end when you are only left with Y and Z, it will take 1 operation for each 0s/1s.

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

          @Uvaish_Zafri

          Amazing Brother, positive and helpful people like you are very rare in comments, thanks for the explanation <3

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

    Another way is to count number of consecutive ones. Let this be K. Therefore, add K — 1 to the answer. Do same for zeroes. Answer is max of answer for one and answer of zero. 96876793

    This is mainly because when we solve for 111000, we see that we actually need 2 moves.

    First move => 100110.
    Second move => 101010.

    Try for higher strings like 11110000, you will notice the answer is always K — 1 for K consecutive ones.

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

Am I the only one who misread problem D and tried to solve thinking it was DFS for most of the contest T_T

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

    I found D way easier than B (maybe because I'm more familiar with graph theory) Basically just give the nodes greedly and maintain the height (because if you try to store the tree you'll mle)

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

how to do B ??

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

Isnt B much harder than D or im missing something obvious?

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

RIP my ratings

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

How to solve B?

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

    Here is an intuitive solution that worked for me.

    For each consecutive pair of 1s, u have to insert a 0 between them and u will always have a "smart way" to do that in a single move(considering the fact that we have equal zeroes and ones). The same holds for pair of zeroes as well.

    Doing it for a single pair of 1s, also do the job for a single pair of 0s. So count the consecutive 0s(00)-> cnt0 and 1s(11) -> cnt1, then max(cnt0, cnt1) will be the answer.

    Hope it helps.

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

    At this kinds of problems, you usually want to search for alternative statements that are more helpful. We can see that we could reframe it as: given a string s consisting of n/2 0's and n/2 1's, lets define f(s) = the number of i for which s[i] = s[i + 1], 1 <= i < n.

    To make s alternating, we want to make f(s)=0.

    A reverse operation changes f(s) with at best 2. So f(s) can be decreased with at most 2 in one operation. A lower bound for the answer to this problem is ceil(f(s)/2).

    Now we only have to prove that you can always decrease f(s) by 2, excepting the case where f(s) = 1.

    if f(s) > 1, then we will always have at least a pair of consecutive 0's and at least a pair of consecutive 1's. So we can just reverse the substring cotaining one of this 1's and one of this 0's and decrease f(s) by 2.

    For example s = 01001011,f(s) = 2. we have the 0 pair (3,4) and the 1 pair (7,8). So if we reverse (4,7) we get 01010101.

    If f(s) = 1, than the string will have to be either 0101..0110101...1010 or 1010....1001...0101. So you can reverse a prefix/suffix and decrease f(s) by 1, arriving at f(s)=0.

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

Guys, where can I hack? I don't see any locks..

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

    Educational rounds do not have the same hacking feature as div2 or div1. You can hack after the contest, but you'll not get any points for that.

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

how to solve G? is nsqrtnlogn supposed to pass? (I had tle on test 17)

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

    nlogn is intended, nlog^2 or nsqrt can pass if written carefully enough but I highly doubt sqrtlog can pass.

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

    Just make Aho-Corasic, and calculate link2(v) = link(v) but only with ends of strings. Now u just go left-to-right in some string of query. After adding some char, you have node V, u must check every suffix, that's end of some string, of this node. U can do it with link2(v). It works O(q * sqrt(5*10^5)), bcs u have only sqrt(5*10^5) different lengths of strings;

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

      How the O(sqrt(5e5)) comes?Can you explain further. My solution with HLD is O(log^2 n).

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

        you have maximum fail depth when calculating query value only if size of n strings must be strictly increasing.

        For example : a, aa, aaa, aaaa, aaaaa ....

        so n is sqrt(5e5) in worst testcase

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

          Oh, I didn't notice this during the contest. So I built the FAIL pointer into a tree and then solved it by HLD+segment tree.

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

problem 2 ~~~~~ string solve(){ // CALM DOWN : — )

ll n;
cin>>n;

string s;
cin>>s;

ll l=0;
ll r=n-1;
vector<char> ans1(n);
bool t=0;

for(int i=0;i<n;i++){
    if(t){
       ans1[i]=('0');
       t=!t;
    }else {
       ans1[i]=('1');
       t=!t;
    }
}

ll tl=l;
ll tr=r;
ll last=0;
bool rev=0;

while(l<r){

    while(l<r and s[l]==ans1[tl]){
       l++;
       if(rev==0){
         tl++;
       }else tl--;
    }

    while(l<r and s[r]==ans1[tr]){
       r--;
       if(rev==0)
         tr--;
       else tr++;
    }



    if(l>=r) break;

    last++;
    swap(tl,tr);
    rev=!rev;
}


l=0;
r=n-1;
tl=l;
tr=r;
ll last1=0;
rev=0;

while(l<r){
    while(l<r and s[l]!=ans1[tl]){
       l++;
       if(rev==0){
         tl++;
       }else tl--;
    }
    while(l<r and s[r]!=ans1[tr]){
       r--;
       if(rev==0)
         tr--;
       else tr++;
    }

    if(l>=r or l>=n or r<0) break;

    last1++;
    swap(tl,tr);
    rev=!rev;
}


ret(min(last,last1));

ret(""); } ~~~~~ why this code is giving TLE .... i have created both the ans array and then used 2 pointer one pointer at left and another at right and i swap the pointers please if any one could help

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

    Please put code in spoiler tags

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

    code looks very dirty... plz polish up

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

      can you explain how to do this question with two pointer??? thanks for help

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

        i can't understand what your code exactly works..

        i don't solve this problem using not two pointer but greedy.

        so i recommend to read the tutorial of this problem.. main idea of that is gorgeous in low rating problem

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

WTF is test 11 in E?

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

Very nice problemset.

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

Even D was much easier than B.. what the hell is answer to B ?

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

    whats the solution of D???

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

      D can be solved with this observation.

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

      Use queue and push the levels into the queue. When you find a smaller number, pop and push the popped level + 1 in the queue. Keep track of max level pushed. Print the max level pushed.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится
    • We may assume the array is circular.
    • An alternating array has no monochromatic adjacent pair (like 00 or 11).
    • If the array is not alternating, there are always two adjacent pairs 00 and 11. We can remove both of them in one operation.
    • Every operation removes at most two adjacent monochromatic pairs.
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Man I went for this exact approach other the fact I still dont get why we assume it to be a circular array ? Please help on this one ...

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

        Just for convenience. Otherwise the third statement is false.

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

What is the expected time complexity for E?

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

    O(NlogN)

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

    I solved it in $$$O(n log(n))$$$, if LIS is required to solve it I don't think it can be any better.

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

      Can you explain your approach?

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

        First of all, if $$$a_{b_{i + 1}} - a_{b_{i}} \ge b_{i + 1} - b_{i}$$$ isn't true for all $$$i \lt n - 1$$$ there is no way to place numbers between them, so the answer can't exist.

        Now lets mark the closest left and right $$$b_{i}$$$ for each index. (for any position b/w $$$b_{i}$$$ and $$$b_{i + 1}$$$, the closest left one is $$$b_{i}$$$ and the closest right one is $$$b_{i + 1}$$$, so we can mark it in $$$O(n)$$$). Lets call these $$$left_{i}$$$ and $$$right_{i}$$$.

        Now clearly for the increasing condition, for any $$$i$$$, $$$a_{i} \ge a_{left_{i}} + (i - left_{i})$$$ so we can actually place some valid numbers in this range (if not we can't even place $$$a_{left_{i}} + 1, a_{left_{i}} + 2, \ldots, a_{i} - 1$$$ between $$$left_{i}$$$ and $$$a_{i}$$$ while keeping it increasing). Similarly we must also have $$$a_{i} \le a_{right_{i}} + (right_{i} - i)$$$. If either of these don't hold, we will have to update $$$a_{i}$$$. So lets set $$$marked_{i} = 1$$$.

        Now in each range $$$(b_{i}, b_{i + 1})$$$, all values with $$$marked_{i} = 0$$$ are individually valid. We want to take a maximum subset of these such that they are increasing and values can be placed between them. Now for increasing the first thing that comes to mind is longest increasing sequence, but if we just do LIS we can end up with issues in cases like this (which Sample 4 thankfully contains):

        3 0
        2 1 3
        

        Here the longest increasing sequence may give us $$$(2, 3)$$$ but this isn't actually valid, we can't place any digit between them such that it forms an increasing sequence. So we also need that for any $$$i, j, (i \lt j)$$$ we pick, $$$a_{j} - a_{i} \ge j - i$$$ must hold. This can be simplified to $$$a_{j} - j \ge a_{i} - i$$$. Or in other words, we just want to find the longest non-decreasing sequence of $$$a_{i} - i$$$ in each segment.

        Adding the sizes of all these sets together will give us the total number of values which don't need to be changed, so the answer will just be $$$n$$$ minus this total size.

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

          Perfect!! Thanks ExplodingFreeze.

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

          i was almost there, unfortunately i didn't knew nlogn approach for LIS :(((.

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

          shouldn't it be longest increasing subsequence of ai-i instead of longest non-decreasing??

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

            nope

            1 2 3 4 5 becomes -> (1-1) (2-2) (3-3) (4-4) (5-5)

            0 0 0 0 0

            if 1 2 3 4 5 is good then we should count longest non-decreasing of ai — i

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

              But why do we consider a[i]-=i for eg in one of the editorials it is written [2,5,3,1] we can' take 2,3 as LIS but after doing above operation it solves the problem. I am not getting the exact problem and solution by this.

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

          Thanks! It really helped!

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

          Thanks a lot for this explanation. During virtual I got stuck on the point where :
          while finding LIS , we must keep in mind that a[j] >= a[i] + (j-i)
          It didn't strike me that we can move that j over to the other side of the equation and started thinking it might require something like convex hull trick to work. -_-

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

In problem D , for first vertex 1 i considered largest increasing sub-sequence starting from i=2 as it's children . For example if input was 1,2,3,5,6,4 . I considered 2,3 as child of 1 and 5,6 as child of 2 and 4 as child of 3 . What is wrong in this approach or in my solution

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

    Your approach is correct Maybe you glitched your code or failed maintaining the height ?

    Here is my code which AC https://codeforces.net/contest/1437/submission/96920232

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

    For this test case-

    8 1 2 3 8 7 6 5 4

    Answer should be 3 your code is giving 1 . I might be wrong

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

    1 as root

    2 3 5 6 can all be childrens of root

    4 can be a child of 2

    so overall the height is $$$2$$$

    The easy way to describe the answer is to calculate the number of increasing sequences, and in each sequence count the number of elements in it.

    In each node, you can put an entire increasing sequence as the children of it. and now the number of nodes for the next level increases by the number of elements in the increasing sequence.

    for example this: $$$1, 7, 8, 5, 6, 2, 3, 4$$$

    $$$[7, 8]$$$ $$$[5, 6]$$$ $$$[2, 3, 4]$$$

    so $$$[5, 6]$$$ will be a child of $$$7$$$ , and $$$[2, 3, 4]$$$ will be a child of $$$8$$$. and now for the next level you have $$$5$$$ nodes namely $$$[5, 6, 2, 3, 4]$$$.

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

      i did same can but it is giving wrong on 273rd input in test case 2. Can you check.96912116

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

        Your code break on this such case:

        $$$n = 10$$$

        $$$1, 2, 3, 6, 5, 4, 10, 9, 8, 7$$$

        Your code output $$$4$$$, while the correct answer is $$$3$$$

        How the answer is $$$3$$$?

        well at depth $$$0$$$ you have $$$1$$$

        and at depth $$$1$$$ you have $$$2, 3, 6$$$

        and at depth $$$2$$$ you have $$$[5]$$$ under $$$2$$$, and $$$[4, 10]$$$ under $$$3$$$, and $$$[9]$$$ under $$$6$$$.

        and at depth $$$3$$$ you have $$$[8]$$$ under $$$5$$$, and $$$[7]$$$ under $$$4$$$, and you still can put many more..

        so the answer is $$$3$$$

        Hope that helps !

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

I try to hack C but it returns this: FAIL Expected EOLN (test case 1, stdin, line 3, why?

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

Can someone explain how to prove the answer to B is just half the number of positions where $$$s_{i} = s_{i + 1}$$$ cyclically? It intuitively feels correct as we can fix at max 2 such positions in each operation but I have no clue how to prove that we always can.

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

    If there are at least $$$2$$$ positions to fix, there are always indices $$$x, y$$$ such that $$$s_x = s_{x+1} = 0$$$ and $$$s_y = s_{y+1} = 1$$$.

    Proof by contradiction: suppose wlog that $$$s_i = s_{i+1} = 0$$$ is false for each $$$i$$$.
    Let $$$z_i$$$ be the position of the $$$i$$$-th $$$0$$$. Then, the inequality $$$2(j - i) \leq z_j - z_i \leq 2(j - i) + 1$$$ holds.

    But there are two positions to fix, so $$$z_{i+1} - z_i = 3$$$ should hold for two indices $$$i = a, b$$$, $$$a < b$$$.

    Then $$$z_{b+1} - z_a = (z_{a+1} - z_a) + (z_b - z_{a+1}) + (z_{b+1} - z_b) \geq 3 + 2(a + b - 1) + 3 = 2a + 2b + 4$$$.

    But $$$z_{b+1} - z_a \leq 2(a + b + 1) + 1 = 2a + 2b + 3$$$ (contradiction).

    So $$$x, y$$$ exist, and you can fix $$$2$$$ positions by reversing either $$$[x + 1, y]$$$ or $$$[y + 1, x]$$$.

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

    My solution was also intuitive , although I didn't consider it as a cycle. I counted positions where $$$s_{i}=s_{i+1}$$$ and $$$ans = (cnt+1)/2$$$. No idea why this works either but it just seemed right and it passed. Was able to solve B in just 4 mins. Felt really good after failing terribly in the Techno Cup :)

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

    Hey I didn't participate in the round, so don't know if this solution is correct. But maybe can help with intuition.

    Keep a count of number of chunks of 1s(c1) and number of chunks of 0s(c0). When we reach n/2 chunks each of 0s and 1s, we are done. In one operation if you reverse a sub-array starting and ending in different bits you can increase both c0 and c1 by 1 potentially (potentially coz that won't happen on the ends). It can be proved that while there are more breakable chunks of 0s and 1s there are sub-arrays ending in opposite bits that break these chunks, incrementing both c0 and c1 by 1. You may need one extra operation if you have an almost alternating sequence but with just c1 = n/2 — 1 and c0 = n/2 or vice versa. With this you can see that you will need max(n/2 — c0, n/2 — c1) reversal operations.

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

What is the intended solution of B and how to prove it? I... I just believe...

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

    consider the case 111011100000

    1**1101110**0000 : flip the selected part, it becomes : 1**0111011**0000

    101**110110**000 -> 101**011011**000

    10101**10110**00 -> 10101**01101**00

    1010101**1010**0 -> 1010101**0101**0

    the selected part in each step is from the first occurrence of 11 to first zero after all ones, which by flipping reduces consecutive 1s by 1 and eventually become zero. So, the answer would be no of 1s for which (a[i]==a[i-1] && a[i]==1).

    Same goes for 0 as well and minimum of those two will be the answer.

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

If I submit two solutions for the same problem, first one can be hacked while the second one can't be. Then if after the 12-hour hacking phase, the first one gets hacked but second one is still is accepted, will my second submission be considered for total score or not ?

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

    Most likely yes: the first will incur time penalty, and the second, along with its time, will be counted towards the score. Generally, the submissions would be (re)judged as if all the hack cases were there from the start.

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

Yay solved A, beware CF for when i become red

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

nice testcases...

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

I wish I could ask "how to solve G?" instead of "how to solve A?" :) anyway, How to sole A?

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

    if((2*l)>r)-YES else-NO

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

      but why?

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

        We are basically trying to exploit the fact that for all m>n, n % m =n. Let us say l=14 and r=26

        We have to find a number x such that it gives a no larger than or equal to x/2 for all numbers from l to r, modulo x. Like 14 % x => x/2 .. 15 % x >= x/2 , up to 26 % x >= x/2 . It is clear that the number should not exceed 2*l , as on taking modulus, any number x larger than l would return l itself. Hence after x=2*l, l itself will give a remainder smaller than x/2.

        If by any means, the number r lies beyond 2*l ; we are certain there exists no solution x , as l % x < x/2 i.e. l < x/2 .

        P.S. In the above example, 28 would be an optimal answer

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

    Lets assume that $$$l = \frac{a}{2}$$$, now $$$a=2l$$$.

    If $$$(a>r)$$$, we know that all elements in $$$(l,r)$$$ are greater than or $$$\frac{a}{2}$$$ as $$$l = \frac{a}{2}$$$, therefore whatever the customer buys, he will have to buy $$$a$$$ cans which is what we wanted so answer is YES. If $$$(a<=r)$$$, He can just buy $$$a$$$ cans and he doesn't need extra cans as $$$a$$$ lies in $$$(l,r)$$$.

    Why assume $$$l = \frac{a}{2}$$$? Because it is optimal and it gives us the biggest window.

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

Did anyone solve problem C, greedily ?

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

The key education that I seem to get from these Educational Rounds is how to get my ass kicked. How did people go about spotting the pattern for B — tried so many approaches but none of them worked.

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

    It did using two pointers. I'm not good in explaining or proving things. It was mainly intuition. You can see my solution . Edit: Why downvotes?

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

    I just counted the number of consecutive 0's, and that is the answer. Because, the number of consucutive 1's/0's are present is == number of minimum swap required.

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

Can anyone please explain me why greedy will fail on problem C.

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

Hello for question D I used a greedy approach which I have seen others use. But my code WA and I have no idea why. Can someone please look: https://codeforces.net/contest/1437/submission/96922858 ? Thank you!

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

Can anyone please explain me why greedy will fail on problem C.

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

In problem e : "In one operation, you may choose two integers i and x (1≤i≤n, x can be any integer) and assign ai:=x. This operation can be done only if i does not belong to the set b." in the first example :

7 2

1 2 1 1 3 5 1

3 5

So I understand that I can never apply such operation on the elements with indices 3 and 5. So a[3] = 1 for always. Why the output is not -1?

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

Did someone else solve C in O(N*logN) with the solution for 713C in this blog? Thanks zscoder for such a useful trick.

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

in problem A possible a always be r + 1 ? why..

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

    If possible, we want to fit the whole range [L, R] within [A/2, A-1]

    We can include R for any A > R, but to also include L we have to extend it as left as we can, means we need smallest A > R

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

Here's a more formal explanation of solution to problem B. Let's say you need to make the input string S equal to T 101010.... The procedure for converting a string equal to the other target string i.e. 010101... is quite similar. Now, let's xor our input string S with the target string T. Say this string is R. It's easy to analyse that R shall have even number of ones. Now, reversing a substring in S is equivalent to reversing the same substring in R. Also, on reversing a substring of even size, with all ones, changes all the ones to zeros. So, basically, the best strategy for us is to bring all the ones closer to each other and then use one operation to change all ones to zeros. Thus, the ans is number of blocks of consecutive ones in R

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

C has a greedy tag too. How to solve it greedily?

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

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

How to approach C with DP?

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

    First sort all the dishes in increasing order, then define dp state as dp[i][t] = the minimum unpleasantness possible in taking out the first i dishes in that order within time t.

    There are two possibilities here:

    1. You can take out dish i at time t, in that case dp[i][t] = dp[i-1][t-1] + abs(t[i]-t).

    2. You don't do anything at time t, in that case dp[i][t] = dp[i][t-1].

    Pick the minimum of these two.

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

https://codeforces.net/contest/1437/submission/96883973 https://codeforces.net/contest/1437/submission/96876758 please check ... those submissions are doubtful. i think, it's a Plagarism case.

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

What is the expected time complexity for F? My solution works in O(NlogN) (only because of sorting) and I don't realy know how to solve this problem with different aproach, but N<=5000 and time limit is 4s.

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

    That's really interesting, can you describe your solution? My solution (which is the model one for this problem) uses dynamic programming with $$$O(N^2)$$$ states.

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

      Оно немного непонятным может быть, поэтому я лучше на русском)
      Я писал дп с N-1 состоянием, где dp[i] — количество способов расставить первых i рыбаков, если мы уже както *хорошо росставили остальных n-i рыбаков. Сразу стоит сказать что если a[n-1]*2>a[n], то ответ 0.

      Теперь, как мы пересчитываем dp[i]:
      Если мы хотим поставить a[i] на первую позицыю, то для начала надо росставить все числа от L[i]-того до (i-1)-го надо поставить на любые позицыи кроме первой(L[i] — такое минимальное j, что a[j]*2>a[i]). Количество способов ето зделать — (n-i)*(n-i+1)...*(n-L[i]-1). А теперь нужно еще росставить числа от 1 до L[i]-1, при том что мы уже *хорошо росставили тех кто от L[i] до R[i], а ето по опредилению — dp[L[i]-1].

      И еще мы можем не на самую первую позицыю ставить, но тогда количество способов ето зделать — (n-i)*dp[i-1]. Вот решение с етой идеей, но произведение я тут считал, так сказать, в тупую, так что там O(N^2) 96921154. А вот уже за линию — 96930477. Если непонятно(а скорее всего, учитывая что писал ето я — непонятно), я постараюсь ответить на вопросы.

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

        If someone needs the translation, I can try to do that, but I don't but I don't guarantee)

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

        Почему мы можем расставить всех от L[i] до (i-1)-го на ЛЮБЫЕ позиции? Почему это ничего не ломает в конструкции?

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

          Когда мы считаем dp[i], мы считаем что суфикс из (n-i) рыбаков росставлен так, что бы самое левое число было хотя бы в 2 раза больше a[i].

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

    Very cool. I haven't yet read your solution in detail, but I believe that the model solution that BledDest mentions with the $$$N^2$$$ states is this:

    Let's first sort the numbers. For every person $$$i$$$, we know that there is a certain prefix of people such that each element $$$j$$$ of the prefix has $$$2*a[j] <= a[i]$$$. These people can freely be placed once person $$$i$$$ is placed, since they are guaranteed to become sad due to $$$i$$$. Let' call this the sad prefix of $$$i$$$, and say it has length $$$pref[i]$$$.

    Let $$$dp[i][j]$$$ represent the number of (suffix of) emotional sequences which start with person $$$i$$$ and $$$j$$$ elements from the sad prefix of $$$i$$$ has already been used. That is, they must not appear in the generated sequence once again.

    The transitions can now be writted as: $$$dp[i][j] = (pref[i]-j) * dp[i][j+1] + sum[suf][j+1]$$$

    Here, $$$suf$$$ represents the least index of any element with value $$$>= 2*a[i]$$$. $$$sum$$$ maintains the suffix sum of the DP.

    This works because we can choose to select one of the available items in the sad prefix and then the remaining sequence generated will be $$$dp[i][j+1]$$$, or we can choose to continue to another number which will be happy.

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

Is there a greedy solution for problem C? If no can you prove it?

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

Editorial when?

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

Who else is waiting for editorial ???

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

Hi all I am unable to construct a case for which my code for problem D fails. Can anyone please help? Link to submission: https://codeforces.net/contest/1437/submission/96924627

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

.

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

B's solution was leaked on telegram . Cheaters pls go to codechef long challenge ;leave codeforces.

PS:I saw it after the contest.
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone help me in test 12 in problem E, I want a smaller case to see where the wrong is

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

can someone help me in testcase 12 in problem E, I want a smaller case to see where the wrong is.

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

Wow A and B, especially B were a lot trickier than i expected...

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

Since nobody has said this yet — I have used Hungarian algorithm for C.

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

Suppose we have alternate problem for A. That is, only customer who visited are L and R. then what will the solution?

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

    I only come up with an $$$O(\sqrt n)$$$ solution.

    Note that $$$l\%a = l - \lfloor \frac l a \rfloor * a$$$, thus the constraints become $$$l \geq (\lfloor \frac l a \rfloor + \frac 1 2) a$$$

    Now we can see for those $$$a$$$ that $$$\lfloor \frac l a \rfloor$$$ are same, you only need to consider the smallest $$$a$$$.

    For a fixed $$$l$$$, $$$\lfloor \frac l a \rfloor$$$ only have $$$2\sqrt l$$$ different values.(You can find proof and the way to iterate here) So there are $$$2\sqrt l + 2\sqrt r$$$ possible $$$a$$$, just iterate through all of them and check.

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

Drastic increase in competition on codeforces:- I just feel that in these days who have rating around 1700 would definitely be a candidate master around 8 months back, And now a days becoming a expert and retaining it becomes difficult.

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

Could anyone tell why is this logic getting hacked for the 1st problem ? HERE

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

    Use Double instead of Float. Some people used float and I hacked it. Tast case is

    1
    500000000 1000000000
    

    answer is NO but your solution result is YES

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

Stupid hacking question: If I open a solution and do not do anything after looking at it, will I lose points?

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

    No

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

    Hacking has no effect on the standings of Educational round and Div3 rounds until and unless you the one being hacked. And you created this account 20 minutes ago just to ask this question? Man i feel sorry for you :(

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

What makes you instantly feel that problem C is a dp problem? (Except the constraints).

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

    Can you tell the time for a given dish without caring about other dishes? No, the time for a dish has to be adjusted keeping in mind the values of all other dishes as well. Thus, you need to use dp. In general, if you ever get confused, just check if the decision on one element is dependent upon other elements or not. If not, you can find the answer greedily, else use dp.

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

    Because I learned 0/1 knapsack. This question is exactly similar to 0/1 knapsack.

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

      Can you please elaborate on how did you reduce problem C to binary knapsack problem?

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

        At first sort the array in non-decreasing order.
        Let, $$$dp[i][j]$$$ = the least possible unpleasant value till time $$$i$$$ considering 1st $$$j$$$ elements in the array.
        $$$dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + abs(t[j] - i))$$$
        We update dp like this in 0/1 knapsack.

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

          Yeah, I solved this in the same way. But I was not able to relate this with the knapsack problem. Anyway, thank you!

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

      Can i get the resource link from where u learned ?

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

How will the graph for problem D look like for this test case :

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

https://codeforces.net/contest/1437/submission/96958667

can anyone suggest me a correction for my code. for A

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

    Used more precise double and got AC

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

    Its not necessarily to use float or double.

    Your code can look like this

    Code

    and you will get AC (96867627)

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

96923678 1:57

96925007 1:59

I found 2 contestants with the same code

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

When will the ratings be updated??

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

Anyone explain how to solve E or explain the solve function in this submission 96887072?

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

how to solve D? https://codeforces.net/contest/1437/submission/96974806 on what test case my solution fails?

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

    You just need to make one small change. You should increase "clevel" with 1, if parent is non zero. This got accepted: 96976307

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

Can anyone please explain the jiangly's solution for problem C 96873242? He used only one state ( dp[n] ).

Update: After the explanation from comments below, I think the idea is during the i'th itereation, dp[j] stores the minimum value to place j elements before time i. In next iteration, For updating dp[j] we only need value of dp[j-1] of (i-1)'th iteration. (And since we are going right to left dp[j-1] will contain the value corresponding to time (i-1)).

Therefore, Transitions:
dp[j] (value to put j elements till i'th time) = min (dp[j] (placed j elements during (i-1) time) , dp[j-1] + abs(t[j-1]- i))
cost of placing j'th element ( 0 based indexing in t) at i time.

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

    He is traversing from right to left. So at any particular position, the left ones contain the dp values of time i-1 and all the others contain the answer for time i. Since we only need to consider smaller values hence it won't make any difference if the larger ones contains values for time i. If you traverse from left to right then it won't work cause your dp will have values for both i-1 and i.

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

      I traversed from left to right with dp[n]: https://github.com/actium/cf/blob/master/1400/30/1437c.cpp

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

        Yeah I guess in your case it will work because dpj in its ith iteration means what would be the minimum value if you place the ith element between time i to i + j. Its a bit different from that solution, there dpj in ith iteration means what would be the mimumum value if the jth element is placed at time i.

        As long as you don't mess your dp you can iterate anyway :P

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

      Thank you kumaraditya1999.
      Actium Can you please explain your approach?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
           --1--2--3--4--5--6--7--> t
        2:   1  0  =  =  =  =  =
        2:   x  1  1  =  =  =  =
        4:   x  x  2  1  =  =  =
        4:   x  x  x  2  2  =  =
        4:   x  x  x  x  3  3  =
        5:   x  x  x  x  x  4  4
        

        x means time point is reserved for a previous dish, = means the unpleasant value is unchanged

        Look at how unpleasant values are being changed. Obviously you do not need to keep all rows in the dp table, and you can shift every next row 1 position left. Then you can keep only n values and maintain them.

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

How to solve C using flows?

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

    I think it can be done with something similar to "assignment problem". And it can be done with flows.

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

I am not understanding which it is happening this or not that in first question my offline compiler"visual studio code" is giving differenet answer than that of codeforces compiler.

Can anybody help me out in this.

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

Terrible contest

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

Can someone explain me how to do C. Thanks:)

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

deleted

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

My unofficial editorial for this contest.

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

Now i am doubting if this round is rated or not?

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

can someone tell me why max time is 2*n In question C ?

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

    Edit: I initially misread the query.

    Think of the following case.

    $$$t_1 = t_2 = ... = t_n = n$$$

    It is optimal to take out the last dish at $$$t = 2n-1$$$. If you go further, you are guaranteed to leave unnecessary empty time slots behind.

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

    Consider the one dish with the smallest t[i] value. It is never optimal to take that one out of the oven after t[i]. Because if we would do, a better solution would be to take it out one minute earlier.

    So, consider the next smallest t[i_2]... again, it is never optimal to wait after t[i_2]. By induction follows that it is never optimal to take out the last one later than 2*n.

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

      hmm gotcha ! btw do you suggest writing forward Dp(updating yet-to-come states on the go) or backward dp(updating previous states on the go) ?

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

        I do whatever seems simpler to me. That depends on the problem statement.

        For complecated dp I find it most often simplest to have a function that gets all state as parameters and calls itself recursive. Then add memoization.

        Once that code is written it is often simple to write the imperative code as well.

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

When will the tutorial be uploaded?

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

is it rated??

If yes, when rating is going to updated??

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

Tutorial and rating should have been updated by now.It is way beyond limit

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

The problem D could be solved using Two pointers as well.In my below AC code , cnt0 is for cnt of the nodes of height=cureentheight-1 which has no child. And Cnt1 is for cnt of the nodes of height=currentheight which has no child. Here is my solution https://codeforces.net/contest/1437/submission/96985177

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

where is the editorial....its too late

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

This is the first time I turned blue, a memorable game! Hope everyone can have good luck and high rating!

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

For Problem C, If there is a single dish and its cooking time is say 50, shouldn't the answer be 0 as we can just wait and take it out at 50th minute? Why is it not the answer?

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

    how do u know its not the answer ??

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

    The time for each dish ranges from 1 to n. Thus, if there is only one dish, the cooking time for that dish must be 1 and the case you stated is not a valid input for the problem.

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

easy contest I dominated it in 10 minutes