rabaiBomkarBittalBang's blog

By rabaiBomkarBittalBang, 9 days 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 hu_tao 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: hu_tao

Preparation: hu_tao

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

Preparation: hu_tao

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

Preparation: hu_tao

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
 
 
 
 
  • Vote: I like it
  • +252
  • Vote: I do not like it

»
9 days 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).

»
9 days ago, # |
  Vote: I like it +108 Vote: I do not like it

Problem E is very similar to 2013 USAJMO Problem 2.

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

Great contest,thanks.Especially love idea of C

  • »
    »
    8 days 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.

»
9 days ago, # |
  Vote: I like it +27 Vote: I do not like it
»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
9 days ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
9 days 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

  • »
    »
    9 days 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.

    • »
      »
      »
      8 days 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

      • »
        »
        »
        »
        8 days 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.

»
9 days 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.

  • »
    »
    9 days 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.

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

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

»
9 days 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)$$$.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same as n is very small .

  • »
    »
    8 days 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)

    • »
      »
      »
      8 days 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
      • »
        »
        »
        »
        8 days 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

        • »
          »
          »
          »
          »
          8 days 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).

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

came up with video editorial . I loved this change :)

»
9 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks For Hints and Video Editorials orz

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Great work guys, the video editorials are exceptional! Hope you'll be doing more contests soon :))

»
9 days 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?

  • »
    »
    9 days 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.

    • »
      »
      »
      9 days 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.

      • »
        »
        »
        »
        9 days 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.

»
9 days 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 :(

»
9 days ago, # |
  Vote: I like it +5 Vote: I do not like it

hey apple

»
9 days 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.

  • »
    »
    9 days 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$$$

»
9 days 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 ?

  • »
    »
    9 days 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.

    • »
      »
      »
      8 days 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://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().

      • »
        »
        »
        »
        8 days 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++).

        • »
          »
          »
          »
          »
          5 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thnx a lot for responding back. I inferred two thins :- first :-

          firstly, I should have generated all possible strings only once before running through each testcase (major mistake)

          secondly, I will use your advice :

          Advice
»
9 days 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

  • »
    »
    9 days 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!

»
9 days ago, # |
  Vote: I like it +16 Vote: I do not like it

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

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

    Glad to hear it! Hope you enjoyed the problems

»
9 days 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 :)

»
9 days 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 # ?)

  • »
    »
    9 days 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!

»
9 days ago, # |
Rev. 2   Vote: I like it -27 Vote: I do not like it

hmm

»
9 days 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?

  • »
    »
    9 days 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$$$).

  • »
    »
    9 days 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.

    • »
      »
      »
      9 days 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?

      • »
        »
        »
        »
        8 days 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.

        • »
          »
          »
          »
          »
          8 days 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..

          • »
            »
            »
            »
            »
            »
            8 days 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

            • »
              »
              »
              »
              »
              »
              »
              8 days 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..

              • »
                »
                »
                »
                »
                »
                »
                »
                8 days 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 days 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!

  • »
    »
    9 days 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

»
9 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Dayum , yesterday it was problem A of codejam round 3, and today it is problem A of div 2 round that fucked me up. I really need to practice more problem A's : )
Problem D was cool, C's solution has a much easier to understand solution instead of developing intuition through geometry. E was ......kinda funny. Gotta say, the scoring distribution actually suggested an easier round. But the problems A and B really drained up a lot of stuff from my freaking brain.

»
9 days 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:))

  • »
    »
    9 days 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)...

    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
9 days 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

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

wow so quick editorial is out

»
9 days 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

  • »
    »
    9 days 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).

  • »
    »
    8 days 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
»
9 days 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

  • »
    »
    9 days 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.

    • »
      »
      »
      8 days ago, # ^ |
        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://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().

»
9 days 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 ?

»
9 days 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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell the dp approach to C?

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I used BFS for problem B :)))

»
8 days 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!

»
8 days 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
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share any tips on how to understand editorials?

  • »
    »
    8 days 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.

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

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

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C video Editorial is very nice

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Omkar and not so quick editorial.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

HI,can anybody tell me where i am going wrong in attempting problem C?Thanks.Code for C

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem A

Consider a test case of n=3 with array elements 3 6 9

the tutorial approach will give output as yes and numbers from 0 to 9

but since the array is already like shouldn't the answer be NO

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't need to add new elements to the array if it is already nice.. But it doesn't say you can't add new elements even if the array is already nice.

»
8 days 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);
    }
}

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    insteasd of storing you can check if the substring is present or not , if not print --> break;

  • »
    »
    8 days 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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey! I have small doubt. In your solution for B, ~~~~~ string sub = s.substr(i, j — i + 1); ~~~~~ Why did you choose to generate substrings of length 1 to n? Isn't it sufficient to just check for lengths 1, 2 and 3?

»
8 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem c. Why am i getting TLE on test case 3 ,My submission

»
8 days 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://codeforces.com/contest/1536/submission/118686508

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the help ,I guess only way is through set.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A is lame tbh

»
8 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    8 days 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?

    • »
      »
      »
      8 days 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.

      • »
        »
        »
        »
        8 days 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.

»
8 days ago, # |
  Vote: I like it -16 Vote: I do not like it

Please check these two Submissions for Problem 'C' :-
1.) https://codeforces.com/contest/1536/submission/118643260
2.) https://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 ...

»
8 days 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??

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

    KKKDDK DKK

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess you are thinking each partition should contain equal number of K and D.. We just care about ratio. So in the test case you mentioned,

    KKKDDK DKK

    would be valid (with ratio D:K = 1:2 in each partition).

»
8 days 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!...

»
8 days 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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A one of the example input is : n=2, a= [3, 4] my output for this test case is :

YES k=4 b= [3,4,1,2] I think array b is nice , but it is wrong answer according to codeforces. can anyone explain? thanks.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey Can anyone explain me the C++ implementation of problem B? Thanks in advance

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell me the concept behind the problem A , i didnt get much how it is possible .

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the DP solution for C?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I have solved problem A using a different method but I am curious why isnt this working?

Here, it says that the input contains 9 but the output does not. All the difference conditions mentioned are being met. Why the wrong answer?

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

    In test case 1 your k value is '9' while you are printing 10 numbers from ( 0 to 9) , judge is only taking k values ( from 0 to 8 ) . similarly with other test cases . here by 'k' I mean the value you printed just after printing "YES"

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh sorry, it was a very silly mistake.

      Thanks

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C question approach was damm good

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain why the nCk implementation in problem F works? (c++)

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

For B why do we need to generate length of 3 substring as length of 2 would suffice right as there are 26^2 different strings of length 2 we would have not exhausted all of them in a given string of length 1000. Can someone explain this to me?

  • »
    »
    29 hours ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    • The number of possible substrings of length 1 = 26 (number of alphabets)
    • The number of possible substrings of length 2 = (26 * 26) = 676 (which is less than 1000)
    • The number of possible substrings of length 3 = (26 * 26 * 26) = 17576 (which is more than 1000)

    We are generating substrings of size 3, because number of substrings of size 2 is only 676, and the max input size is 1000. So there's a possibility of existence of substring of size 3. And that's why we've to generate till substrings of size 3.