rabaiBomkarBittalBang's blog

By rabaiBomkarBittalBang, 3 years ago, In English

We hope you liked the problems! If you’re curious about the two different problem formats, initially Tlatoani, golions, qlf9 and I were working on Omkar 3 with antontrygubO_o while MagentaCobra was working on a separate round with isaf27. We eventually decided to join forces and combine the rounds, resulting in the current Omkar 3.

1536A - Omkar and Bad Story

Idea: rabaiBomkarBittalBang

Preparation: rabaiBomkarBittalBang, Tlatoani, qlf9

Video editorial

Hint
Solution
Implementation in Java by rabaiBomkarBittalBang
Implementation in Kotlin by Tlatoani
Implementation in C++ by kefaa2
Implementation in Haskell by Tlatoani

1536B - Prinzessin der Verurteilung

Idea: MagentaCobra

Preparation: MagentaCobra

Video editorial

Hint 1
Hint 2
Solution
Implementation in Java by hu_tao
Implementation in Kotlin by Tlatoani
Implementation in C++ by 1-gon
Implementation in Haskell by Tlatoani

1536C - Diluc and Kaeya

Idea: MagentaCobra

Preparation: MagentaCobra

Video editorial

Hint 1
Hint 2
Hint 3
Solution
Implementation in Java by hu_tao
Implementation in Kotlin by Tlatoani
Implementation in C++ by smax
Implementation in Haskell by Tlatoani

1536D - Omkar and Medians

Idea: rabaiBomkarBittalBang

Preparation: rabaiBomkarBittalBang, Tlatoani

Video editorial

Solution
Linear time implementation in Java by rabaiBomkarBittalBang
Implementation in Kotlin by Tlatoani
Implementation in C++ by kefaa2
Implementation in Haskell by Tlatoani

1536E - Omkar and Forest

Idea: MagentaCobra

Preparation: MagentaCobra

Video editorial

Hint 1
Hint 2
Solution
Implementation in Java by hu_tao
Implementation in Kotlin by Tlatoani
Implementation in C++ by kefaa2
Implementation in Haskell by Tlatoani

1536F - Omkar and Akmar

Idea: golions

Preparation: golions

Video editorial

Hint 1
Hint 2
Hint 2 Solution
Solution
Implementation in Java by golions
Implementation in Kotlin by Tlatoani
Implementation in C++ by kefaa2
Implementation in Haskell by Tlatoani
| Write comment?
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +108 Vote: I do not like it

Problem E is very similar to 2013 USAJMO Problem 2.

»
3 years ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

Great contest,thanks.Especially love idea of C

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I love the idea of C, too! It takes me many time to think of the solution, even longer than D.

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

"*fanfare* You're been pranked." — Hu Tao

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

There should be a Bugaboo named "Omkar and hard contest"

»
3 years ago, # |
Rev. 2   Vote: I like it -32 Vote: I do not like it

The "editorial" for C is horrible, It doesn't explain anything

Maybe video is better but the text version sucks

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    main observatin is : lets say you want to cut a prefix in some parts, and lets say the ratio of each part is a : b, then if you sum up each part (and hence get the current prefix) then still the ratio of 'D' : 'K' remains same (a : b). So you just count the values from left to write and just count how many ratio so far you have equal to the current value, cuz the current ratio is the only ratio that is possible for each cut.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      That's something I expected from the editorial

      "Draw a line and notice" doesn't seem like a legit editorial to me. Editorial is supposed to give some intution. Don't know why I'm getting downvoted

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Well thats the beauty of the community, many times downvoting/upvoting is random.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The above editorial Haskell implementation of Problem A : 1536A - Omkar and Bad Story — Omkar and Bad Story by Tlatoani is giving compilation error.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Hi, it seems like the spacing got messed up while putting it in the editorial. Haskell is very whitespace dependent. I'll try to fix it, but you can make it compile yourself by realigning the spacing.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    It should be fixed now, thanks for letting me know.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem B solution with linear substring search can be easily optimized (and kotlin implementation has already done it) from $$$O(\Sigma^3\cdot n)$$$ to $$$O(n^2)$$$. The key idea is to generate all the strings (of lengths 1, 2, 3) in lexicographic order and check each of them immediately. The number of strings we have to check doesn't exceed $$$n$$$, therefore, time complexity is $$$O(n^2)$$$.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sorry I didn't do CP in a while. Wouldn't your solution be O(t*n*n) which is O(10^9)? With the solution on the editorial you can get O(t*18000)

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      If I am not completely mistaken, my solution is $$$O(n^2)$$$ per testcase, $$$O(\sum\limits_{i = 1}^{t}n_i^2) \le O((\sum\limits_{i = 1}^{t}n_i)^2)$$$, so it would pretty fit in the time limit due to ($$$\sum\limits_{i = 1}^{t}n_i \le 1000$$$)

      Wrong update
      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ah right, I didn't see that part: "The sum of n over all test cases will not exceed 1000". Thanks.

        I still think the solution in the editorial is better and is O(n), the one in C++ for example, but maybe I'm missing something

        UPD: actually with that constraint on n I guess it actually doesn't matter

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ah, yes, C++ solution has better time complexity, you are right. The update about editorial complexity is wrong, so my initial comment is only about linear string search (whenever we want to check, whether one string is substring for another or not, we use simple search without any precalculations).

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks For Hints and Video Editorials orz

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

"If a is already nice, you don't have to add any elements." So if we print all the elements from 0 to 100 where did we check if the array given is already nice or not.

I used the concept of GCD to solve this and tell if it's already nice or not and then make changes if it isn't nice. Pls, tell is my approach incorrect or did I miss on something in the question?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +18 Vote: I do not like it

    You don't have to doesn't mean you can't.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please elaborate on this? I am new to CP so I thought that this line meant that we had to check if the array is nice or not.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        That line was given to confuse some people .That line means that its not necessary to always add some number. If you print all number between 0-100 then it does not matter whether your array was nice or not ,printed array will always be nice.

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

my solution of 'b' failed in the system test case just bcoz of a 'typo', now I and the person who didn't attempt the b is on the same page, nyc :(

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

hey apple

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

For problem C, there is a property of ratio: if a1/b1 = a2/b2

then a1/b1 = a2/b2 = (a1 + a2)/(b1 + b2).

Using this, for each prefix i just maintain the total occurrences of 'D' and 'K', and we get the only possible ratio in which we should partition the prefix. To the answer, add the occurrences of this particular ratio till i.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    You didn't mention how it helps. It helps in following way. Suppose you want to have answer for prefix p. Then you have $$$(D_p, K_p)$$$ ratio. For any set of splits, for any cut at position $$$i$$$ using fact above you have $$$(D_i, K_i)$$$ same ratio. But it's easy to notice that if you didn't cut at any other place with same ratio, you can do it, because ratio to closest cuts is still $$$(D_p, K_p)$$$ using fact above, but rephrase it a bit: $$$a_1/b_1 = a_2/b_2 \rightarrow (a_1-a_2)/(b_1-b_2) = a_1/b_1$$$

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What does it mean There are at most n+n−1+n−2=3n−3 possible substrings of length 3 or shorter in the input. in the editorial of problem B ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There are $$$n$$$ substrings of length 1, $$$n-1$$$ substrings of length 2, and $$$n-2$$$ substrings of length 3.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      In problem B, can you help why I got TLE ? Here is my submission: https://mirror.codeforces.com/contest/1536/submission/118685076

      My basic idea : I created three sets (names are as follows one, two, three) each storing all possible strings of length (1,2 and 3) lexicographically. Then from the given string str I generated all strings of length 1,2 and 3 and stored all of them in another set called th

      Then I iterated trough all elements of set th and if any of these strings stored in th, if found in set one, two or three, I deleted that element from that set (this means that such string is already there in the given string str thus I deleted from the set which contains it besides set th)

      Lastly I checked if one isn't empty, the set of strings of size 1, then print *one.begin().

      Else if two isn't empty, the set of strings of size 2, then print its *two.begin().

      Else print *three.begin().

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Although the solution contains the right ideas, I think the way it's implemented (using a set) is just too slow. The generation of all possible substrings using a set is 26 log 26 + 26^2 log 26^2 + 26^3 log 26^3, which is roughly 250,000. And you do this for every test case, regardless of how large/small n is, giving roughly 2.5 * 10^8 operations on initialization code alone.

        Despite being suboptimal, admittedly, I might have guessed this would still pass. The timing might be close or I might also be missing something.

        Tangentially: it would be helpful if the formatting was more consistent, specifically tabs/spaces, which render differently. Also, when iterating through the alphabet, it's helpful to use the character's literal value rather than memorizing magic numbers e.g. for (char c = 'a'; c <= 'z'; c++).

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

For problem F, you say there will be choose(x, n)-x ways to place the empty cells but I think it should be choose(x, n-x). Could you please check it out?

Thanks for the great round :D

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yes you are right, the error is fixed — thank you for letting us know!

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Great to see one of my favorite YouTubers (MagentaCobra) help make some of these problems!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I just noticed that many people forgot to print the value of k in the first bugaboo which made for a lot of Wrong answer on pretest 1. I thought I was the only one :)

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Where does it say problem E must have at least one zero? (why do we need to subtract 1 if the grid only contains # ?)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    There are no valid grids with no zeros.

    Assume there is a valid grid with no zero. Then there exists a smallest number $$$x$$$ on this grid, with $$$x>0$$$. The problem states, that for each $$$x>0$$$ there has to be a neighbour strictly smaller than $$$x$$$. Contradiction, $$$x$$$ is already the smallest value!

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

D looks kind of unsolveable to me. I don't see how I could ever get into a state in which I would be able to solve something like that.

What is the key point to find a solution? Randomly let the mind flow...somehow?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Idea: just check if $$$b_i$$$ is a valid median for each $$$i$$$ (by using information from the previous indices, like in dp). How does the array $$$a$$$ look like? You know that

    • $$$b_{i-1}$$$ is the median of $$$a_1, \dots, a_{2i-3}$$$
    • $$$b_{i}$$$ is the median of $$$a_1, \dots, a_{2i-1}$$$

    Put this information together: $$$b_i$$$ should be close to the median of $$$a_1, \dots, a_{2i-3}$$$. More specifically, if $$$c$$$ is a sorted copy of $$$a$$$, $$$c_{i-2} \leq b_i \leq c_i$$$. This means that it's impossible to have $$$b_j$$$ between $$$b_{i-1}$$$ and $$$b_i$$$ ($$$j < i-1$$$).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    I got to the solution after trying out all the samples and coming to these key observations.

    • Whenever we move to new element of b, 2 elements of our choice can be added to array a
    • If we add 2 elements less than current median, median shifts one spot right and vice versa. This means that we can only shift median 1 position to left or right.

    Now consider the sorted array $$$a_1, .. , a_i, .. ,a_n$$$ and $$$a_i$$$ is the median and we can need the new median to be $$$x$$$. Once we add x (and something else) to a, $$$x$$$ is placed at right if $$$x>a_i$$$ or left if $$$x<a_i$$$ in sorted array.

    Now from the observations it should be fairly obvious that for x to be median, it has to be immediately left or right of $$$a_i$$$ in the sorted array, and for that to happen there should be NO element that occurs in between $$$a_i$$$ and $$$x$$$ and this is exactly the solution.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is it always necessary, when we add a new element of b which is x, to be a new element? Can't x be an old element of a?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        Yes, it can. If you consider the case where $$$x>a_i$$$ and x already occurs previously, it just means that there is already an element x immediately to the right of median $$$a_i$$$, in this case adding any 2 elements $$$>=x$$$ would make x the new median.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Just to make sure that I've understood well, it's a MUST to remove the duplicates from array a right? Otherwise those duplicates would block some other new x to be median..

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            I didn't get you. We dont remove anything anytime. for each element of b we pass, we add 2 elements to a

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              I mean like if,

              b = 2,2,...... so on

              rather than a = [. . 2 2 . . .],

              this would be better right? a = [. . . 2 . . .]

              *Supposing dot to the left as negative infinity and dot to the right as positive infinity

              Using the previous occurrence of median if available rather than again adding same value in the array a.

              So my question now is, are there any edge cases where it would fail if we don't do this..

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Yes, using the previous value would be better if it exists. And yes if we add the same value again, there might be cases it fails because median can only move one spot. So while building array a, it might be a good idea to add (x,+-inf) if x doesnt exist or else (+-inf,+-inf) if x already exists.

                But in the problem, we dont care about the construction of array a itself.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  Yeah! Thank you very much. Your answer made the problem seem so much simpler!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    congrats for reaching Expert..you are quite active in comments, so I know you

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Luckily , the people who did A in brute force has passed the system tests.If test 32 was added before the main tests i am sure that many people have got TLE. Great luck for the people:))

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bruteforce solution is working: 118671903. 1) You should use unordered_* structures (default map/set will fail 118656942). 2) Your code of bruteforce solution is not optimal: at each iteration you create new array newV and copy it (you can modify one vector, which you have read), do not use endl (use '\n' -- it works faster), freq[t]++ -> frec.insert({t, 1}) (we have distinct integers), freq[absdiff]++ -> frec.insert({absdiff, 1}) (we don't have absdiff in map), if (freq[absdiff] == 0) -> if (freq.find(absdiff) == freq.end()), use int instead of long long where you can (int works faster), use [] instead of at ([] works faster)...

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Unordered Structures have the complexity of O(n) in the worst case.

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

thank you for the video editorial. would be great if this was present for all contests

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell what is the best method to generate strings like a,b,c.....z,aa,ab,ab.....az,ba,bb..... and so on in problem B and store in a vector? What is the easiest method? Please share your piece of code

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can check this 118663531. Here, complexity of convert_int2string(int n) is log_26(n).

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I did iterate the length of the string, then foreach len I start with a new "aa..".

    Then use an increment method with virtually O(1) like this:

    Spoiler
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For B, can anyone please tell why I'm getting wrong output in codeforces but correct in other IDEs? (Lang: Java)

Ideone: https://ideone.com/UZYIEW

Codeforces: 118692722

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You assume Unix-style line-endings. In Unix there is only \n in line ending. But in codeforces for some reason \r\n. Thus, when you read number it stops at \r and when you read string you get empty string because it read \n straight ahead.

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

golions can you please link this tutorial to the actual contest page materials ?

»
3 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I think B ratings has to be 1000 Or less not 1200 because simple brute force O(n^3) was also working so i dont see a reason it is of 1200 rating

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I used BFS for problem B :)))

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The problems are full of some cool observations and thinking, and I enjoy it a lot. Especially pD though I couldn't figure it out in the round :D

BTW the video explanation is easy to understand compared to only texture explanation, I love it!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think implementation of D using coordinate compression and sum segtree is more elegant.
If we have arr[i] = a, and a[i+1] = b, then segtree.sum(a+1, b-1) should be zero. If its false then answer is "NO", otherwise we do segtree.add(a, 1).

-10^9, 10^9, its big range for segtree, but we can simply compress it.

my code
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share any tips on how to understand editorials?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    I think a difficult thing about editorials is that you're required to give a formal proof which might not give insight about how to solve the problem. For example, for D and E the proofs probably take longer than the problems themselves, since there are some nontrivial steps in the proofs that aren't really required to solve the problem (I had no idea how to prove my solution for E was correct when I solved it, as my thought process had to do with visualizing what grids looked like and I "felt" my solution was correct rather than having 100% confidence). I think a better way to get an idea of what motivation actually goes into solving a problem is by watching video solutions, as people good at explaining problems typically also explain their thought process. I wasn't involved with making the video solutions for this contest so I'm not sure how much they speak about motivation, but you could try those out, and then if you still don't understand there are countless others on Youtube.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    If you don't understand something, at least ask questions.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C video Editorial is very nice

»
3 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

In Problem B, I mindlessly used the below piece of code to store all the substrings in a set which I think is O(n^3), right? Then why didn't my submission got TLE?

s is the input string!!

cin >> s
rep(i, 0, n) {
    rep(j, i, n) {
        string sub = s.substr(i, j - i + 1);
        my_set.insert(sub);
    }
}

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    It is n^3, but I assume the constant is relatively small

    If you count all the characters in all the substrings, that's on the order of (n^3 / 6). Given that n <= 1000, we have some very feasible number of operations, at least for c++

    I'm more curious whether it is possible to hack it with MLE. It should be I believe

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my solution for D is Giving Time limit Exceeded.I guess it taking linear time only. Please help https://mirror.codeforces.com/contest/1536/submission/118686508

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    vector<int> is not some kind of magic. If you insert into beginning it will take time of order of vector size, if you insert in the middle, it will take size/2. Just because it needs to move ahead every element from place where new element will be inserted.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A is lame tbh

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I think for 1536C - Diluc and Kaeya complexity should be $$$O(n \log n)$$$ in both cases. Otherwise how do we get gcd(a,b) in $$$O(1)$$$?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    AC Submission, I did it without using gcd, instead I used double(except x/0) for ratio, and on top of it I used double as key for unordered_map. I did this for the first time and to my surprise got AC! Using double can cause some computation error, right? And can we even use double as key for hashmap?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't know what kind of comparison it use under hood, but I guess two double is treated equal if their binary representation is identical. And, looks like there is no n/m, n'/m' which is close enough (around 1e-14) to make them round to same double. (double can't store number precise so it has to be rounded) From top of my head I can guess only pair (1e5-1)/1e5 and (1e5-2)/(1e5-1) with difference around 1e-10, not even mention that this ratio is not allowed within problem restrictions.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh sorry, it's actually allowed. I had wrong restriction on $$$n$$$ in my mind.

»
3 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Please check these two Submissions for Problem 'C' :-
1.) https://mirror.codeforces.com/contest/1536/submission/118643260
2.) https://mirror.codeforces.com/contest/1536/submission/118699081
Logic is same in both but in 1st submission, I used ratio (in double) as key and in 2nd, I used pair as key of unordered map.
1st one got accepted but 2nd one is giving TLE.
Please Check them ...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem C, I am getting wrong answer on the 9th number for the first 9 character prefix of the string

the substring is KKKDDKDKK

It contains 3 Ds and 6 Ks. Jury's answer says 2.

How can it be divided into 2 partitions??

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest's sytle is so strange than others.Almost every problem I had to find the law behind the title ,it's very easy if we find the law ,but if we cann't find the law ,it's very puzzling!...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem 2 substring of length two is sufficient right?? since 26*26> 1000

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C question approach was damm good

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe something wrong has happened to Problem tags of Problem F...

chinese remainder theorem combinatorics constructive algorithms fft games geometry math meet-in-the-middle string suffix structures *2600

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Consider the line re = *(upper_bound(vals.begin(), vals.end(), cur)); and the line using re = *vals.upper_bound(cur); where vals is a std::set. The first one TLEs and the second one passes well under the TL. The submission links are : AC submission and the TLE submission

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The "1536C — Diluc and Kaeya", I have tried solving using GoLang and getting TLE but the same solution in CPP succeed. Is the recommendation is to not use CPP or have I missed something in this GOLang code.

package main
 
import (
	"fmt"
)
 
type DKTouple struct {
	DCount int64
	KCount int64
}
 
func main()  {
	var testCase int32
	fmt.Scanf("%d\n", &testCase)
 
	for ix := int32(0); ix < testCase; ix ++ {
		solve()
	}
}
 
func solve() {
	var inp string
	var len int32
	fmt.Scanf("%d\n", &len)
	fmt.Scanf("%s\n", &inp)
 
	_mapRatioToIndex = make(map[DKTouple]int64)
	var dCount, kCount int64
	for ix := int32(0); ix < len ; ix++ {
		if inp[ix] == 'D' {
			dCount++
		} else {
			kCount++
		}
 
		x, y := ratio(dCount, kCount)
 
		if ix != len - 1 {
			fmt.Printf("%d ", maxPartitionCountOptimal(DKTouple{DCount: x, KCount: y}))
		} else {
			fmt.Printf("%d\n", maxPartitionCountOptimal(DKTouple{DCount: x, KCount: y}))
		}
	}
}
 
// GCD via Euclidean algorithm
func GCD(a, b int64) int64 {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}
 
func ratio(x, y int64) (int64, int64) {
	if x == 0 {
		return 0, 1
	}
 
	if y == 0 {
		return 1, 0
	}
 
	gcd := GCD(x, y)
	return x/gcd, y/gcd
}
 
var _mapRatioToIndex map[DKTouple]int64
func maxPartitionCountOptimal(dkTouple DKTouple) int32 {
	val, ok := _mapRatioToIndex[dkTouple];
 
	if  !ok {
		_mapRatioToIndex[dkTouple] = 1
		return 1
	}
 
	_mapRatioToIndex[dkTouple] = 1 + val
	return int32(1 + val)
}