Vladosiya's blog

Codeforces Round #855 (Div. 3)
By Vladosiya, history, 22 months ago, translation, In English

Hello! Codeforces Round 855 (Div. 3) will start at Mar/02/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank: 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 for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

  • Vote: I like it
  • +196
  • Vote: I do not like it

Comments Comments (178)
| Write comment?
»
22 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I hope this div.3 will help people increase their rating . Good Luck to all!

    # Codeforces Round #855 (Div. 3)
    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 2   Vote: I like it -29 Vote: I do not like it

      THE Worst Contest I Have Ever Seen!..

      I was solving some NP problems and I saw this contest. I thought it could have some nice problems and it will be worth the time that I spent. But I am regretful of entering this contest. My time has gone in a useless way.

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I became expert an day ago. unrated div 3 make me feel a little sad.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i took part in only three rated rounds. Unrated div 3 make me feel a little sad.

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hh，div3 will be unrated >1600,upperclassmate had missed extension meeting(

        → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how long it took to you to become expert?

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    but you can register new id to get happy rating.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      I believe in no alt supremacy.

      → Reply
»
22 months ago, # |
  Vote: I like it +72 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

....

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

looking forward to be pupil finallyy pls

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope so I reach pupil this time. :-)

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it
meme :)
→ Reply
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I hope being specialist after this round

→ Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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 ?

→ Reply
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +18 Vote: I do not like it

muchas gracias aficiónados esto para vosotros SIUUUUUUUUUUUUUUUUUUUUUUUUUUUUU

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +21 Vote: I do not like it

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

Spoiler
→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

lets become pupil

→ Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

StringForces

→ Reply
»
22 months ago, # |
  Vote: I like it +9 Vote: I do not like it
POV: you got WA in problem A
→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

I can't reach expert now.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest!

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you prove it tho?

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      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?

      → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Nice Div. 4 Contest

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I did hash ... xD

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      lol, my solve function has 11 lines

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      195675499

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

        → Reply
»
22 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Girl in a jacket .

→ Reply
»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

stringforces

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

i think it was nice for speedrunners

→ Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice problems like always. orz ITMO University team

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it
  1. bad testcases of problem A.
  2. see my this solution is 195584757 wrong for mmeo but it's still accepted
→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

195704952

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
    }
}
→ Reply
»
22 months ago, # |
  Vote: I like it +47 Vote: I do not like it

As a tester, I was late xD

→ Reply
»
22 months ago, # |
← Rev. 6   Vote: I like it +19 Vote: I do not like it

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
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Could you explain how to find the tree hashcode?

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    thanks for this <3

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 3   Vote: I like it +6 Vote: I do not like it

      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)).

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

(But without coding)

Talk is cheap.jpg

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

      → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +17 Vote: I do not like it

D is very cute!
G: About rooted tree hashing

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)$$$.

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        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!

        → Reply
»
22 months ago, # |
  Vote: I like it -20 Vote: I do not like it

This contest was easy.

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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]

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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!

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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://codeforces.net/contest/1800/submission/195634085

    → Reply
»
22 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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://codeforces.net/contest/1800/submission/195719096

This fails — https://codeforces.net/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 :)

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Or rather just use vectors when working with finite set of integers/chars

      → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the proof of C?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1592B - Hemose Shopping

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

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    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!

    → Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
22 months ago, # |
← Rev. 4   Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you, i will keep this in mind and try to solve this problem again when i have time

      → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

→ Reply
»
22 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In your C++ solution, you forgot to check if map[i] == 0 before incrementing values for vec[i]. I believe you want to put values for the 0 bits in odd_freq.

    → Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

in problem A , bad tests -_-

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope this will make me expert

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the editorial be out?

→ Reply
»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

image
size up picture

→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

late editorial :sadge:

→ Reply
»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to prove the greedy solution of problem C?

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Why has this contest been removed from rating upgrades?

→ Reply