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

Автор Vladosiya, история, 20 месяцев назад, По-русски

Привет! В Mar/02/2023 17:35 (Moscow time) начнётся Codeforces Round 855 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

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

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

Штраф за неверную попытку в этом раунде будет равняться 10 минутам.

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

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

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

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо: tolbi, lunchbox, Son, sary, Wibo, yorky, nigus, tute7627, 74TrAkToR, bigfoot19982, oversolver, Be_dos, CARBINE, molney, KoT_OsKaR, Nickir, cute_hater, Crutch, vrintle, Rubikun, akulenok, medk, Jostic11, Ghassane за тестирование раунда и весьма полезные замечания. Список тестеров будет пополняться.

Всем удачи!

UPD: Разбор

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

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

I became expert for the first time around an year ago. But never got a chance to participate in an unrated div 3 contest. So this is my first unrated div 3.

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

This div3 round will be the 1800th contest of Codeforces. Congratulations!

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

....

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

"do not have a point of 1600 or higher in the rating"?

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

Whis the last two problems of the contest will be interesting.

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

looking forward to be pupil finallyy pls

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

Hope so I reach pupil this time. :-)

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

My birthday contest! I hope I can become expert. Edit: lol I'm dropping a lot

»
20 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
meme :)
»
20 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I hope being specialist after this round

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

вот блин,почему раунды див3 рейт только для людей с рейтингом меньше 1600(

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

Apparently I probably get negative delta in the last div 2 round which will put me back to specialist.

If my rating isn't update soon will this round be unrated for me ?

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

Div.3 is perfect for my first rated contest.
Looking forward to a good rating.

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

First time to test a codeforces round, The problems are nice, I recommend everyone to participate, have fun and prepare your cats!

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

muchas gracias aficiónados esto para vosotros SIUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

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

Круто! Всем удачи на предстоящем 3-ем Диве. Теперь ждём Див. 4)))

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

This will be my first div 3 contest I'm so excited

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

As a tester, Worst Contest I Have Ever Seen!..

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

hope a big postive delta I want to rank up to be Specialist:)

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

this time div3 contest will not be rated for me. Mixed feelings

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

I hope every participant to get + points and do well today <3.

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

I have to say it... drumroll.. stringforces

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

lets become pupil

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

StringForces

»
20 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
POV: you got WA in problem A
»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think first prob should be like: "the string can only contain the letters 'm', 'y', 'a' and 'v' ..."

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

never thought a day will come that I'll hate strings and string algos.

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

it's sad that I wasted too much time on D due to a small mistake again :(

I can't reach expert now.

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

the worst round of my life...

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

Great Contest!

Enjoyed solving a bunch of problems, Finally back to specialist again :D !

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

A great Div 3 as always. My best ever contest performance.

A: Pretty trivial, just remove duplicates

B: Process all the good pairs, then for letters with >= 2 occurrences use a k to make them good.

C: Standard priority queue, I took a risk and didn't prove it however. (also got a penalty because I forgot to use long long >.<)

D: Another solution I didn't prove, but I used memoization and checking for !memo[i][s[i]+2] to increment answer

E: I did casework for the easy version, then generalized it for the hard version.

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

    D has a rather simple solution by checking characters at index $$$i$$$ and $$$i + 2$$$ and if they are equal they give the same string.

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

      How do you prove it tho?

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

        not a mathematical proof, but here I go- let's suppose 2 char are equal and they are 'X' in "abcXdX". If we remove (Xd), string is abcX, and if we remove (dX), string is abcX, which is the same. . For: XdX, if we remove Xd, (X) remains, and removing dX, (X) remains. I hope this helps

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

    C is similar to IZhO 2023 Day 2 Problem 1, where you have to match bonus cards to the right (another type of) cards as well

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

    Ignore this, since the earlier message can't be deleted

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

    Wow, I didn't know something like a priority queue existed. For the easy version, I just retrieved the maximum element of the previous elements before the hero card, but that gave me a TLE for the hard version as expected. I was searching for something similar to a priority queue, but I wasn't knowledgeable enough to create something like it from scratch. I am sure it will come in handy in the future.

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

How to solve F?

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

    I'm getting WA3, but I still hope the direction is right, correct me if it's wrong;

    I came to using https://www.geeksforgeeks.org/count-pairs-given-xor/ so 25 unique characters, for each word, we go from a character 'a' to 'z' and set 1 if the number of occurrences of a character in the word is odd, and set 0 otherwise.

    then we try to exclude every character from 'a' to 'z' and consider all other 25 characters, we said that each character should occur an odd number of times, in binary it's all 1s, so we count the number of pairs with xor equal to all 1's

    but getting wa3

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

      Been trying the same. Seems like there was a case of overcounting. Also, in the problem, $$$i = j$$$ can never contribute to the answer.

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

      When the character is not present then it's also 0 becuase it occur even number of times. How are you checking if there are exactly 25 characters? are you checking this case too?

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

    You can Use bit manipulation with DP.
    See you have N strings. For each string count the number of all characters present them if all the characters from 'a' to 'z' is present in the string than this string is of no use for us.
    So we consider all the strings where unique characters are less than 26. For each string we will create a val initially with 0. If some character x comes odd times than we will add (1<<(x-'a')) to val. Now we can use a DP of say type like this
    vector<unordered_map<int, int>> dp(128). For each character ch not present in the current string we will increase the value of dp[ch][val] by 1.
    As the number of strings are 2*10^5 the number of values are also can be at max 2*10^5. Now similarly for each string again we will check for all the characters that are not present in the string we will consider them not present in the second string as well and for remaining characters if some character is present odd number of times in current string than it should be present even number of time in other string and vice versa.
    This way we get a value same way we calculated while creating the DP. For that value and absent character we will add that value to our answer.
    At the end for each string we had added each value twice. So print ans/2.

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

Nice Div. 4 Contest

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

Is it possible to calculate the hash when swapping one character with another? I used the polynomial rolling hash algorithm, but my code fails on Test #5 in Problem D, not sure what exactly that I did was wrong. Can someone give me a clue why my intuition was wrong?

Submission

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

    I guess it's because of the anti-hash testcases, made to elevate the probability of collisions. And I couldn't find a way to use two different hashes for the computation.

    Gave this question a 15 min thought and realized it's just observation and 3-5 lines of code.

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

How to solve D?

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

    D can be solved by checking characters at index $$$i$$$ and $$$i+2$$$ and if they are equal they give the same string.

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

Wasted 30 minutes in D because I thought hashing would work..

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

    I did hash ... xD

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

    Could you please elaborate on what do you mean by hashing. I have somewhat basic knowledge of what hashing means, just curious what was your approach.

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

      lets say a string is: $$$abcde$$$.
      At first the hash value is like this:
      $$$a*X^0 + b*X^1 + c*X^2 + d*X^3 + e*X^4$$$
      if you remove $$$bc$$$ from the string then it becomes:
      $$$a*X^0 + (d*X^3 + e*X^4) / X^2 = a*X^0 + d*X^1 + e*X^2$$$
      let this value be $$$y$$$. so we just have to count the number of distinct $$$y$$$ for all adjacent pair of characters.

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

    Same, even I wasted 20-30 mins thinking of prefix-suffix hashing...

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

    Double hashing worked for me (although it was a pain doing it lol)

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

      Yeah it was a pain. Could you maybe take a look at my submission?

      195675499

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

        Sorry for the late reply! But I regret to tell you that you were correct for most of the parts, and there was just a tiny little flaw! The problem with your code is that using 2 maps would cause issues, for example

        string1 = (3, 5) string2 = (3, 6)

        This case m1[3] and m2[5] is true after registering string1. When your code comes across with string2, it will not try to record it, since m1[3] is already true!

        Therefore, a correct implementation is to merge hash1 and hash2 into 1 single number. (i.e. hash = hash1*(1e9)+hash2) Then, simply use 1 map is sufficient. Here is the amended code of yours (Submission ID : 195846862)

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

Girl in a jacket .

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

stringforces

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

i think it was nice for speedrunners

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

In problem $$$E2$$$ why $$$k$$$ may be larger than $$$n$$$ !?

I wasted 15 minutes because of that (I assumed that $$$k≤n$$$), and I'm sure many people failed because of that case.

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

    If you read statement carefully they mentioned there is no boundation on the value of k. Also there was no relation mentioned in the statement as well between n and k.

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

Nice problems like always. orz ITMO University team

»
20 месяцев назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
  1. bad testcases of problem A.
  2. see my this solution is 195584757 wrong for mmeo but it's still accepted
»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice round with a variety of themes!

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

how can i optimized this solution for problem E1 https://mirror.codeforces.com/contest/1800/submission/195690945 I have used brute force approach to check

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

    There are two types of letter positions:

    • unreachable by any swap (eg. third in 5-letter word)

    • possible to do a swap with some other letter

    So for the first category they have to be the same, position-by-position (as they cannot be swapped). For the second category only total number of each letter must match — because they can be permuted in every possible way (I didn't prove it formally, but just assumed and it worked). There was no need of finding the chain of swaps leading to correct one

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

here answer me how WE COULD SOLVE THE PROBLEM C WITH NOT KNOWING THE QUEUE

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

Can Someone Please Point Out Why My Code Fails For F?

195704952

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

My casework solution for E1 lol, it actually helped me realize the general solution for E2 and only needed a few tweaks.

void solve(){
    int n, k;
    cin >> n >> k;
    string a, b;
    cin >> a >> b;
    string x = a, y = b;
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    if(x != y){
        cout << "NO" << endl;
        return;
    }
    if(a == b){
        cout << "YES" << endl;
        return;
    }
    if(a.length() >= 6){
        cout << "YES" << endl;
        return;
    }
    if(a.length() <= 3){
        cout << "NO" << endl;
        return;
    }
    if(a.length() == 4){
        swap(a[0], a[3]);
        if(a == b) cout << "YES" << endl;
        else cout << "NO" << endl;
        return;
    }
    if(a.length() == 5){
        if(a[2] == b[2]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}
»
20 месяцев назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

As a tester, I was late xD

»
20 месяцев назад, # |
Rev. 6   Проголосовать: нравится +19 Проголосовать: не нравится

A: Implementaion.

B: For each pair of lowercase and uppercase we count their occurence, let they be cnt1 and cnt2, then it contribute min(cnt1, cnt2) to the answer we can get initially, and abs(cnt1-cnt2)/2 to the answer we can get by operation, so the answer is sum(min(cnt1, cnt2)) + min(k, sum(abs(cnt1-cnt2)/2)).

C: We can maintain a priority queue. We scan the array from left to right, when s[i]>0 we push it into the priority queue, and pop an element and add it to the answer when some s[i]=0.

D: Let f(i) be the string after removing s[i] and s[i+1], then f(i)==f(j) (i<j) is equivalent to s[t]==s[t+2] for all t in range [i, j-1]. Therefore, let the initial answer be n-1, and each t that s[t]==s[t+2] will contribute -1 to the answer.

E: First check the trivial case when s and t are different after sorted. For a pair of (s[i], s[i+1]), if i>=k, we can swap them by:

(s[0], ..., s[i-k], ..., s[i], s[i+1], ..., s[n-1]) --> swap (i-k, i) -->

(s[0], ..., s[i], ..., s[i-k], s[i+1], ..., s[n-1]) --> swap(i-k, i+1) -->

(s[0], ..., s[i+1], ..., s[i-k], s[i], ..., s[n-1]) --> swap(i-k, i) -->

(s[0], ..., s[i-k], ..., s[i+1], s[i], ..., s[n-1])

Similar for i+1+k<n. So if every pair of chars can be swaped like this, which means n>=2*k+1, we can re-arrange the string arbitrarily. If n=2*k, we can swap (s[k-1], s[k]) like this:

(s[0], ..., s[k-1], s[k], ..., s[2*k-1]) --> swap(0, k) -->

(s[k], ..., s[k-1], s[0], ..., s[2*k-1]) --> swap(0, k-1) (we can re-arrange [0, k-1] arbitrarily since we can swap every pair in this range) -->

(s[k-1], ..., s[k], s[0], ..., s[2*k-1]) --> swap(0, k) -->

(s[0], ..., s[k], s[k-1], ..., s[2*k-1])

Finally, if n<2*k, there are some chars in the middle can't be moved, but we can re-arrange every movable chars like steps above. So we need to check every unmovable positions of s and t.

F: Bitmask. Let mask1(s)= the letters occurs odd times in s, mask2(s)= the letters occurs any times in s. Then (s, t) is a good pair is equvalent to popcount(mask)==25 && mask&mask2(s)==mask2(s) && mask&mask2(t)==mask2(t), where mask=mask1(s)^mask1(t). Therefore we can calculate the contribution of every mask[i]=(1<<26)-1-(1<<i) for i in range [0, 25] using a map.

G: Tree hashing. If the root has even number of childs, the hashcode of subtrees of these child must appear in pairs, and if the root has odd number of childs, there must exist a child with symmetric subtree, and the hashcode of other subtrees appear in pairs.

Some explanation about tree hashing
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Could you explain how to find the tree hashcode?

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

    Any good materials for tree hashing? I figured out hashing should solve this task but I had a hard time finding materials for it.

    I did implement tree-hashing for the first time in my life by using some StackOverflow answer https://stackoverflow.com/a/58502389/6946362. But I had no confidence if it won't fail due to some hash conflicts.

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

    thanks for this <3

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

    in problem D why are you checking only two strings only lets say string is abcde possible strings are cde ade abe abc you are only comparing string 1 ,string 2 & string 2 , string 3 & string 3 ,string 4 why are you not comparing string 1 with string 4,why only adjacent strings only?

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

      Because in string abcd, if ab==cd (f(2)==f(0)), then ab==ad==cd (f(2)==f(1)==f(0)) must hold, so we only need to check adjacent pairs: (f(i), f(i+1)).

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

    Could you please elaborate on your F solution? How do you calculate this Therefore we can calculate the contribution of every mask[i]=(1<<26)-1-(1<<i) for i in range [0, 25] using a map. in O(n) complexity?

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

      Let's fix mask and ignore all s[i] with mask2(s[i])&mask != mask2(s[i]). Let i<j, then mask1(s[i])^mask1(s[j])=mask is equivalent to mask1(s[i])=mask1(s[j])^mask, then #{i<j: (i, j) is a good pair} = #{i<j: mask1(s[i])=mask1(s[j])^mask) = occurence of mask1(s[j])^mask in range [0, j-1]. So we can use a map to store occurences of each mask1.

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

    Thanks. I followed your description of F and upsolved it.

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

    I implemented G according to your solution but it's getting WA on test 3. Could you or anyone else help me find the bug please?

    Spoiler

    UPD: I ACed using the seed that you were trying and optimizing the hash function.

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

First time to solve all the problems in Div.3 ^_^

(But without coding)

Talk is cheap.jpg

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

Finally solve till E2 :) .... Dream comes true lmao

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

I think this round's problems where a little too easy for div 3 lol, but I love it. I think I'm hitting Specialist for the first time after this round too, so that's great

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

    Bro can you plz explain briefly the idea behind your graph implementation for E1?

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

      I think it's straightforward. Since you can swap any two characters as long as their indices have a difference of k or k+1, that means that a character can make its way to any spot that's "connected" to its current spot via the k and k+1 index difference. So you can create an adjacency list for every index (which contains at most 4 other indices by the way, meaning that you can even get rid of the adjacency list if you feel like it's unnecessary) and use it to find all the "connected components" where a character can possibly go with depth-first search (dfs). Then all you have to do is iterate over each character of the target string and check if there's at least one available character in the first string which can reach this specific spot via a connected component. Also I know this solution is a little overkill for this problem, but it's the first thing I thought of and I didn't want to waste too much time thinking about another one during the contest. I hope I explained it well

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

Thanks for strong E2 pretests! WA on test 20 was really helpful

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

D is very cute!
G: About rooted tree hashing

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

    You don't need hashing, there is deterministic and simplier solution: for each vertex let's calculate the number, which represents equivalence class by isomorphic relation. To do so, we calculate these numbers for all childs, put them into a vector, sort it, then using smth like std::map<vector, int> we can determine the equivalency class for current vertex.

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

      But how to ensure right time complexity? We need to compare the whole vector and the worst time complexity for this kind of map is $$$O(n\log n)$$$.

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

        Oh I understand. The sum of time spent on map is $$$O(\sum_v \deg(v)\log n)=O(n\log n)$$$ so the amortized time complexity is still $$$O(\log n)$$$. Nice solution!

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

This contest was easy.

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

Solution to E without any implementations

  1. We have to make $$$s$$$ equal to $$$t$$$. Let's use Meet-in-the-middle
  2. Let's make $$$s$$$ and $$$t$$$ minimum lexicographical as possible. If after that $$$s=t$$$ answer is YES and NO otherwise.

[solution]

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

I solved C1 with DP and I couldn't convince myself how PQ works on this problem. Take the case:

5

5 4 2 0 0

I see why it works now because we only have to return count but technically what happens if you simulated is that the first hero picks card 0 and the last two cards are discarded. I think if you had to return the cards that each hero picked in the answer, PQ wouldn't work right?

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

    Yes, that was my concern too. But since we don't have to return the order of the picks, then we just need to prove that some optimal picking order exists such that you can use all of the max values before the 0s. I didn't prove it, but I didn't see why some optimal picking order shouldn't exist which implies the priority queue sum is optimal.

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

    I think we could store pairs <value, card order no> in priority queue. PQ solution will then tell us which cards should be used. After that filtering, our task becomes trivial as we know exactly which cards will be used. We can recreate each hero pick on the second run with selecting only those filtered bonus cards (by using stack)

    It is what I came up with, it might be possible of doing it in a single run through cards

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

E can also be solved with DSU. It can be done by merging all positions with distances k and k + 1 between them and checking for each connectivity component if set of letters on corresponding positions in s and t are the same: 195646722

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

    I also thought it seemed similar to the classic number of swaps to sort problem. I wasn't completely sure so I wrote a casework solution instead but cool to see it works!

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

    it's just 2 lines of code.. just need to check if each index maps to a valid index incase it's not similar to the character at the same location in the other string. you check my submission here -https://mirror.codeforces.com/contest/1800/submission/195634085

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

Good contest! A-F were smooth :)

Although I was able to solve A-F however I'm still trying to wrap around the fact that why would initialising the unordered_map elements make a difference.

This works -https://mirror.codeforces.com/contest/1800/submission/195719096

This fails — https://mirror.codeforces.com/contest/1800/submission/195719053

The only difference b/w the 2 being that in the working code I have initialised all characters to 0. Aren't unordered_map elements given a default value 0 when not present? I also tried explicitly checking for the members but no luck!

I would be grateful and really appreciate if someone could help me with this.

Thanks in advance :)

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

    You are iterating through the frequency map with a for auto loop. When you check for a key that doesn't exist, it is created with a default value of 0. But creating a key while iterating through the map with a for loop is undefined behavior.

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

    don't know how should i react knowing that I'm not alone :/ this thing cost me the entire round, I wasn't able to figure out how this could be wrong. I thought to move to other problems but B got my mind and i got stuck at it for long time. I tried many times changing the code lil bit but it didn't help and made me write a whole different code after wasting a amount of time in which i should've solved all the other problems i solved in the round. After the contest, I again came back to this, added few lines and got AC just to find out that it was all due to the uninitialized map............. Lesson learnt -> always initialize maps :)

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

What's the proof of C?

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

Can anyone explain why this approach works for D? I did testing on random strings in compare with brute force solution and could not find test that would break the solution.

int ans = 0;
pair<char, char> last;
for (int i = 0; i < s.size() - 1; ++i) {
    pair<char, char> cur = { s[i], s[i + 1] };
    if (cur.first > cur.second)
        swap(cur.first, cur.second);
    if (cur != last)
        ++ans;
    last = cur;
}
»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

1592B - Хемосе в магазинах Similar to E1 and E2 But I did not solve them, although I solved this problem more than a year ago

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

Isn't G a little bit easy for its position?

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

    Depends on the person I would say. Idea definitely wasn't hard to find but implementation and execution might be hard if you're new to the concept. In my case I found the idea when there were 20 minutes left but had no idea how to correctly implement it.

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

1592B - Hemose Shopping

Similar to E1 and E2 But I did not solve them, although I solved this problem more than a year ago

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

    Don't care about how many problems you solved bro. Keep your focus on learning and pushing your limits forward.

    Personally, I learnt from E even though I solved it (virtually), I learnt from other solutions which used DSU. Some people also solved D using hashing.

    I also found problem G interesting and I'm going to learn tree hashing.

    What a great round!

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

    Thanks a lot for sharing the old question, had good practice solving multiple questions of the same type.

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

Antihash tests? My solutions with unordered_map/cc_hash_table passed (task G), but gp_hash_table got TL on testcase3. And after making my own hash all is OK. UPD after systests. cc_hash_table gave TL. But unordered_map is fine

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

SO HAPPY !! Got a sub 1k rank for the first time ! Loved the questions

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

flunked very hard on E1 and E2, stuck for over 1.5 hours and could not solve them..

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

    In my opinion, if a problem refers to many operations, sometimes it would be beneficial to consider the group/semigroup/set generated by these operations. May consider the properties of these operations, e.g., Do they commute? Are they invertible? Are they periodic (i.e., there exists an positive integer $$$n$$$ such that $$$a^n=1$$$)? Are they associative?

    Sometimes drawing a graph helps.

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

Forgot to use long long for answer in C1 and C2, and I kept thinking I was using the wrong approach, so I couldn't solve either of them. Gonna fall to newbie now :(

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

Regarding problem F, the time constraint for this problem is pretty tight,and the judge's behaviour is hence arbitrary. Check these submissions,195747465 and 195747315. I have submitted the exact same code twice, getting accepted verdict in one submission. Could someone suggest a faster algo, and hack this solution if this is'nt the intended one.

UPD: made it faster using hashing, fits well into the time limit now.

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

So interesting the problems are in this contest,I love this contest!but I think pretest in A maybe weak.

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

why my solution for problem A got hacked? qwq

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

For F task I got AC in java but getting wrong answer when i convert in to C++. Please help, i am new to C++

AC 195755004

WA 195754099

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

in problem A , bad tests -_-

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

Has the system test finished? When will the rating update?

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

Why was that div3 round unrated for me? I'm under 1600...

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

hope this will make me expert

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

When will the editorial be out?

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

late editorial :sadge:

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

How to prove the greedy solution of problem C?

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

    Let's start with simplifying the problem. For each hero card we want to pick one booster card that appears before it. We may not use the same card twice. Heroes are interchangable because in the end it doesn't really matter which one gets which card. So, we traverse through the deck from top to bottom. Everytime we find a booster card we put it in a priority queue which shows the current best booster we can give to a hero. When we encounter a hero, we give them the top booster from the priority queue. We can do that because, at the end, we will have used a booster card at most H times where H is the amount of the heroes in the deck. Each of the cards is used in a legal manner (as when we consider a hero our priority queue only contains the cards that appeared prior to it). That means that if we choose the take operation for each of the cards we used in our final solution and the discard operation for everything else, we don't have to worry about the fact that you put the cards on top of the bonus deck beacuse we will have at most H cards and each hero will get one of them (Basically, we don't get any "garbage cards" that we don't want to use in the bonus deck. That means that the order in the bonus deck doesn't matter as we don't really care which hero gets which card as long as it's legal)

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

Why has this contest been removed from rating upgrades?