### rabaiBomkarBittalBang's blog

By rabaiBomkarBittalBang, 9 days ago,

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

Preparation: rabaiBomkarBittalBang, Tlatoani, qlf9

Video editorial

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

# 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

# 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

# 1536D - Omkar and Medians

Preparation: rabaiBomkarBittalBang, Tlatoani

Video editorial

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

# 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

# 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

• +252

 » 9 days ago, # |   +18 Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
 » 9 days ago, # |   +108 Problem E is very similar to 2013 USAJMO Problem 2.
 » 9 days ago, # | ← Rev. 2 →   +25 Great contest,thanks.Especially love idea of C
•  » » 8 days ago, # ^ |   +2 I love the idea of C, too! It takes me many time to think of the solution, even longer than D.
 » 9 days ago, # |   +27
 » 9 days ago, # |   +1 "*fanfare* You're been pranked." — Hu Tao
 » 9 days ago, # |   +11 There should be a Bugaboo named "Omkar and hard contest"
 » 9 days ago, # | ← Rev. 2 →   -32 The "editorial" for C is horrible, It doesn't explain anythingMaybe video is better but the text version sucks
•  » » 9 days ago, # ^ |   +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.
•  » » » 8 days ago, # ^ |   +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
•  » » » » 8 days ago, # ^ |   +11 Well thats the beauty of the community, many times downvoting/upvoting is random.
•  » » 9 days ago, # ^ |   0 This helped me to develop the logic https://www.geeksforgeeks.org/split-the-binary-string-into-substrings-with-equal-number-of-0s-and-1s/
 » 9 days ago, # |   +8 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, # ^ |   +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.
•  » » 9 days ago, # ^ |   +18 It should be fixed now, thanks for letting me know.
•  » » » 8 days ago, # ^ |   +13 Thanks.
 » 9 days ago, # |   +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)$.
•  » » 9 days ago, # ^ |   0 I did the same as n is very small .
•  » » 8 days ago, # ^ |   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)
•  » » » 8 days ago, # ^ | ← 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 updateAnd editorial solution is $O(\sum\limits_{i = 1}^{t}n_i \cdot \Sigma^3)$, where $\Sigma = 26$ — the alphabet size. It isn't much worse than mine, but I decided to write about my trick here.
•  » » » » 8 days ago, # ^ | ← 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 somethingUPD: actually with that constraint on n I guess it actually doesn't matter
•  » » » » » 8 days ago, # ^ |   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).
 » 9 days ago, # |   0 came up with video editorial . I loved this change :)
 » 9 days ago, # |   +13 Thanks For Hints and Video Editorials orz
 » 9 days ago, # |   0 Great work guys, the video editorials are exceptional! Hope you'll be doing more contests soon :))
 » 9 days ago, # |   +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?
•  » » 9 days ago, # ^ | ← Rev. 2 →   +18 You don't have to doesn't mean you can't.
•  » » » 8 days ago, # ^ |   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.
•  » » » » 8 days ago, # ^ |   +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.
•  » » » » » 8 days ago, # ^ |   0 Alright, thanks for the explanation.
 » 9 days ago, # |   +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 :(
 » 9 days ago, # |   +5 hey apple
•  » » 8 days ago, # ^ |   0 knife!!
 » 9 days ago, # |   +20 For problem C, there is a property of ratio: if a1/b1 = a2/b2then 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.
•  » » 8 days ago, # ^ | ← 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$
 » 9 days ago, # |   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 ?
•  » » 9 days ago, # ^ |   +1 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 →   0 In problem B, can you help why I got TLE ? Here is my submission: https://codeforces.cc/contest/1536/submission/118685076My 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 thThen 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, # ^ |   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++).
•  » » » » » 4 days ago, # ^ |   0 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 : Advicewhen 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++)
 » 9 days ago, # |   +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
•  » » 9 days ago, # ^ |   +7 Yes you are right, the error is fixed — thank you for letting us know!
 » 9 days ago, # |   +16 Great to see one of my favorite YouTubers (hu_tao) help make some of these problems!
•  » » 8 days ago, # ^ |   +11 Glad to hear it! Hope you enjoyed the problems
 » 9 days ago, # |   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 :)
 » 9 days ago, # |   +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 # ?)
•  » » 8 days ago, # ^ | ← 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!
•  » » » 8 days ago, # ^ |   +8 Thanks, now I understand!
 » 9 days ago, # | ← Rev. 2 →   -27 hmm
 » 9 days ago, # |   +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?
•  » » 8 days ago, # ^ |   +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$).
•  » » 8 days ago, # ^ |   +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 •  » » » 8 days ago, # ^ | 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? •  » » » » 8 days ago, # ^ | +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. •  » » » » » 8 days ago, # ^ | 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.. •  » » » » » » 7 days ago, # ^ | ← 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 •  » » » » » » » 7 days ago, # ^ | ← Rev. 2 → 0 I mean like if, b = 2,2,...... so onrather 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 infinityUsing 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.. •  » » » » » » » » 7 days ago, # ^ | 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. •  » » » » » » » » » 7 days ago, # ^ | +8 Yeah! Thank you very much. Your answer made the problem seem so much simpler! •  » » 8 days ago, # ^ | +14 congrats for reaching Expert..you are quite active in comments, so I know you  » 9 days ago, # | ← Rev. 2 → 0 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.  » 8 days ago, # | +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:)) •  » » 8 days ago, # ^ | 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)... •  » » » 8 days ago, # ^ | 0 Unordered Structures have the complexity of O(n) in the worst case.  » 8 days ago, # | +6 thank you for the video editorial. would be great if this was present for all contests  » 8 days ago, # | 0 wow so quick editorial is out  » 8 days ago, # | 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 •  » » 8 days ago, # ^ | 0 You can check this 118663531. Here, complexity of convert_int2string(int n) is log_26(n). •  » » 8 days ago, # ^ | ← 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: Spoilerbool inc(string &s) { for(int idx=s.size()-1; idx>=0; idx--) { if(s[idx]<'z') { s[idx]++; for(int idx2=idx+1; idx2  » 8 days ago, # | ← 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/UZYIEWCodeforces: 118692722 •  » » 8 days ago, # ^ | 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. •  » » » 8 days ago, # ^ | 0 In problem B, can you help why I got TLE ? Here is my submission: https://codeforces.cc/contest/1536/submission/118685076My 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 thThen 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, # | +15 golions can you please link this tutorial to the actual contest page materials ?  » 8 days ago, # | -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  » 8 days ago, # | 0 Can anyone tell the dp approach to C?  » 8 days ago, # | +1 I used BFS for problem B :)))  » 8 days ago, # | +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 :DBTW the video explanation is easy to understand compared to only texture explanation, I love it!  » 8 days ago, # | 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 codestruct segtree{ vectorarr; int size = 1; segtree(int n){ while (size < n) size*=2; arr.resize(2*size - 1,0); } void add( int ind, int v){ add_(ind,v,0,0,size); } void add_(int ind, int v, int x, int lx, int rx){ if (rx - lx <= 1) {arr[x] += v; return;} int mid = (lx+rx)/2; if (ind < mid){ set_(ind, v,x*2 + 1,lx,mid); } else { set_(ind, v,x*2 + 2,mid,rx); } arr[x] = f(arr[x*2 + 1],arr[x*2 + 2] ); } int sum(int l, int r){ return sum_(l,r,0,0,size); } int sum_(int l, int r, int x, int lx, int rx){ if ((lx <= l && rx <= l) || (rx >= r && lx >= r)){ return 0; } if (l <= lx && r >= rx){ return arr[x]; } int mid = (lx + rx)/2; return sum_(l,r,x*2 + 1, lx, mid)+sum_(l,r,x*2 + 2, mid, rx); } }; void solve(){ int n; cin >> n; vi arr(n); rvec(arr); // just reading vector vi sarr = arr; sort(sarr.begin(),sarr.end()); mapmp; int now = 0; int bef = sarr[0]; mp[sarr[0]] = 0; for (int i = 0; i < n; i++){ if (sarr[i] != bef){ bef = sarr[i]; now++; mp[sarr[i]] = now; } } vectornarr(n); for (int i = 0; i < n ; i++){ narr[i] = mp[arr[i]]; } segtree tree(n); tree.set(narr[0],1); for (int i = 1; i < n; i++){ int mi = min(narr[i],narr[i-1]); int ma = max(narr[i],narr[i-1]); if (ma != mi){ if (tree.sum(mi+1,ma) > 0){ cout << "NO" << endl; return; } else { tree.add(narr[i],1); } } } cout << "YES" << endl; }   » 8 days ago, # | 0 Can someone share any tips on how to understand editorials? •  » » 8 days ago, # ^ | ← 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. •  » » » 5 days ago, # ^ | 0 Thank you for your advice! •  » » 8 days ago, # ^ | +2 If you don't understand something, at least ask questions.  » 8 days ago, # | 0 C video Editorial is very nice  » 8 days ago, # | 0 Omkar and not so quick editorial.  » 8 days ago, # | 0 HI,can anybody tell me where i am going wrong in attempting problem C?Thanks.Code for C  » 8 days ago, # | 0 In Problem A Consider a test case of n=3 with array elements 3 6 9the tutorial approach will give output as yes and numbers from 0 to 9but since the array is already like shouldn't the answer be NO •  » » 7 days ago, # ^ | 0 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 → 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); } }  •  » » 8 days ago, # ^ | 0 insteasd of storing you can check if the substring is present or not , if not print --> break; •  » » 8 days ago, # ^ | ← Rev. 4 → +1 It is n^3, but I assume the constant is relatively smallIf 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, # ^ | 0 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 → 0 It is sufficient as you said but ... I mindlessly used ... •  » » » » 8 days ago, # ^ | 0 Oh okay thanks!  » 8 days ago, # | ← Rev. 2 → 0 Problem c. Why am i getting TLE on test case 3 ,My submission  » 8 days ago, # | 0 Why my solution for D is Giving Time limit Exceeded.I guess it taking linear time only. Please help https://codeforces.cc/contest/1536/submission/118686508 •  » » 8 days ago, # ^ | +5 vector 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, # ^ | 0 Thanks for the help ,I guess only way is through set.  » 8 days ago, # | 0 Problem A is lame tbh •  » » 8 days ago, # ^ | 0 Why? Very decent problem  » 8 days ago, # | +10 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, # ^ | 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? •  » » » 8 days ago, # ^ | 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. •  » » » » 8 days ago, # ^ | 0 Oh sorry, it's actually allowed. I had wrong restriction on$n\$ in my mind.
•  » » » » » 7 days ago, # ^ |   0 I See!
 » 8 days ago, # |   -16 Please check these two Submissions for Problem 'C' :-1.) https://codeforces.cc/contest/1536/submission/1186432602.) https://codeforces.cc/contest/1536/submission/118699081Logic 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 ...
 » 7 days ago, # |   0 In Problem C, I am getting wrong answer on the 9th number for the first 9 character prefix of the stringthe substring is KKKDDKDKK It contains 3 Ds and 6 Ks. Jury's answer says 2.How can it be divided into 2 partitions??
•  » » 7 days ago, # ^ | ← Rev. 2 →   +3 KKKDDK DKK
•  » » 7 days ago, # ^ |   0 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).
•  » » » 7 days ago, # ^ |   0 thanks, got it
 » 7 days ago, # |   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!...
 » 7 days ago, # |   0 in problem 2 substring of length two is sufficient right?? since 26*26> 1000
•  » » 7 days ago, # ^ |   +6 lol.. 26*26 < 1000 ..
•  » » 7 days ago, # ^ |   +3 damn math ;)
 » 7 days ago, # |   0 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, # |   0 Hey Can anyone explain me the C++ implementation of problem B? Thanks in advance
 » 7 days ago, # |   0 can someone tell me the concept behind the problem A , i didnt get much how it is possible .
 » 7 days ago, # |   0 What is the DP solution for C?
 » 6 days ago, # |   0 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?
•  » » 6 days ago, # ^ | ← Rev. 3 →   0 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"
•  » » » 6 days ago, # ^ |   0 Oh sorry, it was a very silly mistake.Thanks
 » 5 days ago, # |   0 C question approach was damm good
 » 4 days ago, # |   0 can someone please explain why the nCk implementation in problem F works? (c++)
 » 4 days ago, # | ← Rev. 3 →   0 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?
•  » » 16 hours ago, # ^ | ← Rev. 3 →   0 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.