Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2) Editorial

Hope you all enjoyed the problemset! Editorials to problems H and I are not ready yet, we will add them as soon as possible. We apologize for weak pretests and easy problems for top participants.

By the way, solution authors did not necessarily prepare the problems. The solutions were chosen at random.

UPD. Editorials for H and I are ready! Wish you all productive upsolving and high ratings!

1553A - Digits Sum

Idea: bthero Preparation: kefaa2

1553B - Reverse String

Idea: Errichto Preparation: Will not be revealed for now because we care for his/their safety.

1553C - Penalty

Idea: Errichto Preparation: BledDest

1553D - Backspace

Idea: Adel_SaadEddin, Zaher Preparation: Will not be revealed for now because we care for his/their safety.

1553E - Permutation Shift

Idea: bthero, kefaa2 Preparation: BledDest

1553F - Pairwise Modulo

Idea: kefaa2, Errichto Preparation: bthero

1553G - Common Divisor Graph

Idea: Adel_SaadEddin, Zaher, Errichto Preparation: Errichto

1553H - XOR and Distance

Idea: kefaa2 Preparation: BledDest, marX, kefaa2

1553I - Stairs

Idea: bthero, kefaa2, BledDest Preparation: BledDest, kefaa2

• 3 months ago, # ^ |

  This is what you want with coffee in the morning.Big Thanks

  • 3 months ago, # ^ |

    ← Rev. 2 →  

    -40

    The comment is hidden because of too negative feedback, click here to view it

    • 3 months ago, # ^ |

      As you can read in the main blog, um_nik was a tester. He has nothing to do with the editorial.

      • 3 months ago, # ^ |

        No offence, but I am curious: do you personally like problems B & C? It's very surprising to me that these are the best ideas an LGM, who's also involved in a number of CP activities, can come up with.

        • 3 months ago, # ^ |

          No worries, I'm happy to explain my/our reasoning.

          I certainly like B & C more than problem A. In the discussion below some CF blogs, I've already argued that math puzzles aren't that good for easy problems. But yeah, you can also say that I'm getting out of shape and my taste is getting worse. I lost my hopes after feedback from my AGC 47.

          I suggested three easy problems: something rejected as A, penalties without question marks as B, and Reverse String with as C or with as B. I would use those three in my round and I can defend that choice. In particular, I like Penalties most as it's a natural problem that I came up with during Euro Cup. "Given a binary string like 1011100000, say when the winner is already decided".

          Reverse String was rejected because it would be adjacent to the similar-styled Backspace. Penalties were too easy for the second slot (or so we thought) so somebody suggested question marks. Sadly, that change modifies the problem from cute to artificial. Testers then provided feedback that the round is too difficult for beginners. To fit the slot between Digits Sum and Penalties, we used Reverse String with .

• 3 months ago, # ^ |

  If t matches the first few characters of s, you need to judge whether the number of remaining characters of s is even. Only if the number is even can the match be true.

  • 3 months ago, # ^ |

    yaa, i missed it. thanx bwxnQAQ Now you are my friend.

  • 3 months ago, # ^ |

    A very big thanks to you buddy bwxnQAQ

  • 2 months ago, # ^ |

    Thank you very much.

  • 10 hours ago, # ^ |

    Thanks bwxnQAQ , I was scratching my head for almost 2 hours because of this silly error or not so silly idk

• 3 months ago, # ^ |

  You need to judge if the number of the remaining letters is even or not.

• 3 months ago, # ^ |

  Can u give that testcase or something similar to that, I am facing trouble regarding that t-c 19 85-th token..

  • • 2 months ago, # ^ |

      Can you told me why I am getting TLE on test 30 in Problem D? -_- I used binary search. Can it be a reason? Here is my solution :

      https://codeforces.com/contest/1553/submission/126554472

      • 2 months ago, # ^ |

        ← Rev. 2 →  

        0

        na apu,,,,,..... nlogn is efficient......... but you declare vector odd[200010] which complexity is O(n),n=size......... total complexity will be O(n*q)......... then if q=100000, it will definitely fail..............

        https://codeforces.com/contest/1553/submission/126596025

        • 2 months ago, # ^ |

          Many Thanks... I was totally confused why I am getting tle. Thanks a lot for replying..

        • 7 weeks ago, # ^ |

          can we use bitmask enumeration technique to generate all possibilities in problem C?

• 3 months ago, # ^ |

  I think you mean solutions, as I am not aware of any solution. The thing is, mine was nowhere close even with pragmas and the 64-bit compiler.

  • 3 months ago, # ^ |

    My passes pretty comfortably within the TL. Unfortunately, I was not able to debug this quickly enough during the contest.

    Submission

    • 3 months ago, # ^ |

      ← Rev. 2 →  

      +55

      My solution with a time complexity of passed all the pretests using and then passed all the system tests using .

      Note: this is not a comment talking about creative solutions, but a comment talking about how to use some ordinary data structure to compensate stupidity, so please forgive me if this sounds not so inspiring...... QwQ

      Just sharing some thoughts...... QwQ

      If you use enumerate all of the possible results of , you will end up with a condition in which you need to maintain a sequence allowing you to perform to operations:

      • Updating one single element in the sequence(we will simply call this "update").
      • Query the sum of a continuous prefix of the sequence(we will simply call this "query").

      And the length of the sequence is , the total number of "update"s is , while the total number of "query"s is .

      You choose a power of near , in my case I chose , and divide the sequence into several blocks, each have a length of .

      You maintain two sequences, and , in which means the sum of elements in the -th, -th, ......, and the -st block, while means the sum of elements in the -th position, -th position, -th position, ......, and the earliest position that still belongs in block .

      It's not hard to see the answer to any queries to position is , meanwhile can be calculated quickly enough using the bitwise >> operation.

      When an update occurs, if the update is a plus at position , you just enumerate all the blocks ,...... and add to the of those; and within block , you just enumerate all the positions and add to the of those.

      This data structure handles each update in time, each query in time, or constant time, and it also has a pretty excellent constant factor.

      My implementation(may be very ugly QAQ) is here: Submission #123330049 — Codeforces

      Thank you very much for your time reading this! I really appreciate it.

      • 3 months ago, # ^ |

        It is amusing that this is kind of a "two-layer" segment tree, and if you change it into three layers, the time complexity handling updates will reduce to while not changing the time complexity of queries(since its adds up pieces of information instead of ).

        That means that you can actually chose ANY constant number and make the time complexity — ......

        But in practice I've only seen choosing and a large proportion of them ...... QwQ

        • 3 months ago, # ^ |

          Shouldn't the complexity be ?

          • 3 months ago, # ^ |

            Thanks for your correction, but I meant to say that It costs time to use the data structure to handle EACH update operation, and time to use the data structure to handle EACH query operation QwQ.

            • 3 months ago, # ^ |

              requires for both updates and queries.

• 3 months ago, # ^ |

  Suppose you have a connected component of size . It will surely be a cycle. You can easily show that this cycle can be fixed using swaps, but not less. In total this will sum up to operations.

  Also you could try mixing elements between different cycles, but you will see it does not help either. This is not a formal proof, just a simple explanation built on pure intuition and logic.

  • 3 months ago, # ^ |

    Thanks for the intuition. I derived the contradiction of minimality for the case of swapping vertices between two components. And as for the swaps, I guess proof is redundant, seems logical to me. :)

    Also thanks to Errichto for his comment.

• 3 months ago, # ^ |

  You need swaps to transform into . Swapping two values (e.g. the first two) puts one element in proper position. This happens for swaps and then the last swap puts the last two elements in proper positions.

• 3 months ago, # ^ |

  Could U give a brief solution on your idea?

  • 3 months ago, # ^ |

    ← Rev. 2 →  

    +1

    In short, I'm searching for all prefixes of and reverse of the remaining part in .

    Spoiler

    Edit:
    1. is the length of .
    2. All searches are done in as the two substrings to be searched add up to a length .
    3. -based indexing is used.

    • 3 months ago, # ^ |

      Got it,thx so much.

• 3 months ago, # ^ |

  ← Rev. 2 →  

  +1

  Suppose x is the starting position, y is the rightmost position you covered and z is the leftmost position you covered. For every pair of x and y, z is unique (if it exists)(because length of t is fixed). Now you can easily compare by hashing.

• 3 months ago, # ^ |

  ← Rev. 2 →  

  0

  here : 123296482

  some explanation

• 3 months ago, # ^ |

  solution i think my dp solution is n2 .correct me if i am wrong.

  • 3 months ago, # ^ |

    123306389 my dfs solution is truly similar to yours.I think that the dp array in your solution isn't necessarry and it may not work because we keep going right and then keep going left.So we cannot get repetitive (i,j,flag),right? of course i think our solutions are O(n²) and it may work even faster in tests.

• 3 months ago, # ^ |

  Not so hard, as is really easy to think and code.

  Many people thought they can work out ，but they failed. That's no need.

  • 3 months ago, # ^ |

    ← Rev. 4 →  

    -15

    But why passes as it is operations but it should be maximum of around per second, right?

    Edit — Found this

    • 3 months ago, # ^ |

      it's around I think, CF's judging machines are fast, and I think is also standard for ICPC

    • 3 months ago, # ^ |

      ← Rev. 2 →  

      0

      it's not strict n^3 it's lesser than n^3 / 2 and even n^3 alone runs easily under a second

    • 3 months ago, # ^ |

      I think it's because is quadratic in worst case

  • 3 months ago, # ^ |

    Ya, same happened with me!

• 3 months ago, # ^ |

  read um_nik's code and dry run on a few cases u will understand.

  • 3 months ago, # ^ |

    ← Rev. 2 →  

    0

    Is it possible to solve D using binary search?

    I implemented it, it's giving WA on test case 6.

    6th test case is too long, not possible to check what went wrong in my code :{

• 3 months ago, # ^ |

  Proof works with induction.

  The base case is that k==2, then one swap fixes both elements. Else k>2, and swapping two elements fixes at most one of them, leaving us with a cycle of size k-1. It is easy to see that swapping two elements without fixing one does not give a better solution.

• 3 months ago, # ^ |

  So do you submit a solution to A and get pretests passed and then stare at the whole solution till the contest ends, because maybe it will not pass system tests?

• 3 months ago, # ^ |

  ← Rev. 2 →  

  0

  @sa_so_ in both for loops u have used n and n-i But may be in some loop it might be 'm'

• 3 months ago, # ^ |

  Because tutorial of D is not available.

  • 3 months ago, # ^ |

    Thanks

• 3 months ago, # ^ |

  ← Rev. 6 →  

  +1

  Solution for D

  The tutorial for D is most likely not written yet or its written and is undergoing some edits. Whatever the case, the tutorial is still not out and available yet.

  • 3 months ago, # ^ |

    thanks

  • 3 months ago, # ^ |

    Very well explained.Thanks

  • 3 months ago, # ^ |

    ← Rev. 2 →  

    0

    why we have to move right to left ,i tried an approach where i am are moving from left to right and if difference between some part is even we can delete it

    but it is giving wrong answer my code

    can you please tell which case i am missing?

    or can you tell me how i can think of approach of moving pointer from right to left?

    • 3 months ago, # ^ |

      You can just reverse strings right after reading them from the input and then do left to right processing in the rest of your code. That's what I did myself during the contest. If the standard C++ library doesn't offer a native way to reverse strings, then it makes sense to have such function somewhere in your collection of code templates.

      The main idea is that in many cases it is possible to do some cheap pre-processing of the input data to make the problem easier. Sometimes it's sorting of the input data, sometimes it's reversing the order of elements, etc.

• 3 months ago, # ^ |

  Why can not I see the tutorial of the problem D

  My random guess is that maybe the official solution for D was not originally intended to be greedy?

  I first tried to implement my solution as a recursive DP with a two-dimensional state array of 1-bit boolean states, but this is obviously not a good fit for the problem constraints and needed improvements. Still I used this code as a reference implementation to generate a lot of testcases. I thought that maybe a single-dimensional DP state array (storing something like the best index or whatever) could do the job. But then noticed that just a simple greedy modification doesn't seem to fail any of the generated testcases. This was a facepalm moment for me. Spent so much time on something that turned out to have just a greedy solution! The letter D was really deceiving. However observing many system tests failures and hacks after the contest made me change my mind to some extent. The time spent on thoroughly testing solutions locally was not a completely wasted effort after all.

• 3 months ago, # ^ |

  I have the same problem as you. Have you found where the wrong is? Tell me about it, please.

  • 3 months ago, # ^ |

    Looking at test 99 I came up with a way to escape the time limit, I check the string s, if the string t contains a character that the string s doesn't, make the word print "no" and return, good luck

    • 3 months ago, # ^ |

      ← Rev. 2 →  

      0

      I got it, thank you.

• 3 months ago, # ^ |

  Hello, which problem are you talking about here?

  As for the penalty, For every submission you get a non-AC verdict on tc != 1 during the contest, you get a penalty of 10mins, that is your solution is considered to be 10mins late after the actual AC verdict.

  • 3 months ago, # ^ |

    I am asking about problem C. Can you help me why is the answer 9 in last test case of problem

    • 3 months ago, # ^ |

      ← Rev. 5 →  

      0

      Explaination

      • 3 months ago, # ^ |

        thank you :)

bool got(string s, string t, int i, int j, bool goingRight) {
    if (j == t.size()) return 1;
    if (i < 0 || i == s.size()) return 0;
    if (s[i] == t[j]) {
        if (goingRight)
            // then right and left both can be explored
            return got(s, t, i + 1, j + 1, 1) || got(s, t, i - 1, j + 1, 0);
        // otherwise you can go left only
        return  got(s, t, i - 1, j + 1, 0);
    }
    return 0;
}
void argon17()
{
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < s.size(); ++i) {
        // try at every index
        if (got(s, t, i, 0, 1)) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

• 3 months ago, # ^ |

  It's complexity

  • 3 months ago, # ^ |

    For each character, we are exploring right as well left characters, so it should be O(n^2).

• 3 months ago, # ^ |

  i noticed that too.haha i wonder if they will be in danger if their handles are shown?

• • 3 months ago, # ^ |

    I think this guy AURRUM can help,he also got wrong answer on test 14 and he got it accepted now

    • 3 months ago, # ^ |

      thx bro

• 3 months ago, # ^ |

  my solution was even simpler but had almost the same idea 123325031

  • 3 months ago, # ^ |

    This is the solution for D, I am asking for B. I got the idea of O(n^3) approach given in the tutorial, just curious what's wrong with my approach.

• 3 months ago, # ^ |

  ← Rev. 2 →  

  0

  A very simple test for D would be the following:

  babcde
  bab
  NO

  It is no, because whatever you do, you cannot delete your remaining odd number of symbols(in this case ) without affecting the other letters, simply because not adding another two symbols requires two(duh), and an odd number is obviously not a multiple of two.

  That's the reason why solutions that worked from 1 to n failed, but those working from n to 1 passed. You can delete as many symbols from the beginning as you like, but this doesn't work for the end, you need to check whether the length from the position of your last taken character till the end of array is an even number. Only then it is possible.

• 3 months ago, # ^ |

  Sorry it's O(n^3), my brain got stuck.

• 3 months ago, # ^ |

  ← Rev. 2 →  

  0

  It's lowercase in your output dude, here's the picture.

• 3 months ago, # ^ |

  Your output is lowercase, I think the checker converted it to uppercase.

int t ; 
cin >> t ;
while( t -- ){
    string s ;
    string t ; 
    cin >> s >> t ;
    int indx = s.size() - 1 ;
    int test = 1 ;  
    string sk ; 
    for( int j = t.size() - 1 ; j >= 0 ; j -- ){
        for( int i = indx ; i >= 0 ; i -- ){
         if( s[ i ] == t[ j ] && ( indx - i ) % 2 == 0 ){
             sk = sk + s[ i ] ;
          indx = i - 1 ;
          break ;  
          }
        }
    }
    reverse( sk.begin() , sk.end() ) ; 
    //cout << sk << endl ; 
    if( sk == t ) cout << "YES\n" ; 
    else cout << "NO\n" ;
}

• 3 months ago, # ^ |

  ← Rev. 5 →  

  0

  Thanks for your solution.

• 3 months ago, # ^ |

  ← Rev. 2 →  

  0

  Interesting numbers should be numbers whose last digit is 9, not multiples of 9. So there are 10 in total.

  • 3 months ago, # ^ |

    okayy..I mistook as summing all digits until I get a single digit thank you!

• 3 months ago, # ^ |

  For n=100, the possible interesting numbers are actually 9,19,29,39,49,59,69,79,89,99, which results in the answer becoming 10. other than 9,99 none of the numbers you mentioned are interesting, for example 18 : sum of digits is 9 18+1 = 19 : sum of digits is 10 which violates that S(19) < S(18) and therefore is not an interesting number. Similarly for the other numbers you mentioned. Hope this helped!

• 3 months ago, # ^ |

  Lol.I did the same thing. I initially did 200 times and got an unnecessary TLE because that.

• 3 months ago, # ^ |

  ← Rev. 3 →  

  0

  We first observe that if we type backspace, 2 characters in the origin text will be deleted. If the difference of the lengths between the origin text and the expected text is odd, then we must delete at least one character at the beginning of the origin text (which is what this int p = (n - m) & 1; and for (int i = p;...) does). Then, if the character at s[i] == t[q], we can go and check the next. If not, then we must delete this mismatch. At mentioned at the beginning, we have to delete the both characters starting from the mismatch, which is what the variable k does. Now, at the end, if the index q == the length of expected text m, we have found a way. Otherwise, we cannot transform the origin text to the expected.

  And just saw the official editorial is also avaliable now.

• 3 months ago, # ^ |

  If the sum of many numbers is n, only three of them can be greater than n/3.

  • 3 months ago, # ^ |

    Thanks, I will read tutorial again, but can you explain why these 3 value of k are turned out to be only 0, 1, 2, 3?

    • 3 months ago, # ^ |

      I don't understand your question. Are you asking about some particular test? You might want to watch the video explanation too, it's in the first comment below the blog.

      • 3 months ago, # ^ |

        I got the solution completely, thank you so much, man...I don't know whether it will benefit me in the future or not to get problems solved using editorials and looking at other's code.

        • 3 months ago, # ^ |

          It will benefit you. Upsolving is much more important than solving problems during the contest.

• 3 months ago, # ^ |

  me too

• 3 months ago, # ^ |

  If we move the chip position in the order 0, 1, 2, 1, 0 we get cabac.

  • 3 months ago, # ^ |

    Oh, I can't believe I missed that. I was considering the order 0, 1, 2, 3, and couldn't understand how I could get the 'c' from this. Thank you so much.