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

Автор rabaiBomkarBittalBang, 3 года назад, По-английски

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
Разбор задач Codeforces Round 724 (Div. 2)
  • Проголосовать: нравится
  • +257
  • Проголосовать: не нравится

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

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

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

Problem E is very similar to 2013 USAJMO Problem 2.

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

Great contest,thanks.Especially love idea of C

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

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

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

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

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

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

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

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

Maybe video is better but the text version sucks

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

    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 года назад, # ^ |
        Проголосовать: нравится +25 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

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

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

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

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

    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 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Thanks For Hints and Video Editorials orz

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

"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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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

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

      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 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

hey apple

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

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

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

      In problem B, can you help why I got TLE ? Here is my submission: https://codeforces.net/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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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

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

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 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    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 года назад, # ^ |
      Проголосовать: нравится +54 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        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 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

              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 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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 года назад, # ^ |
                    Проголосовать: нравится +8 Проголосовать: не нравится

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

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

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

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

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

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 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I used BFS for problem B :)))

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone share any tips on how to understand editorials?

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

    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 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

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

C video Editorial is very nice

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

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 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

    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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem A is lame tbh

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

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

Please check these two Submissions for Problem 'C' :-
1.) https://codeforces.net/contest/1536/submission/118643260
2.) https://codeforces.net/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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

C question approach was damm good

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

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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