### Noobish_Monk's blog

By Noobish_Monk, 4 weeks ago, translation,

Thanks K1o0n for being the mvp of this round.

1992A - Only Pluses

Preparation: K1o0n

Tutorial
Solution (Python)

1992B - Angry Monk

Idea: Noobish_Monk

Preparation: K1o0n

Tutorial
Solution (C++)
Solution (Python)

1992C - Gorilla and Permutation

Idea: K1o0n

Preparation: K1o0n

Tutorial
Solution (Python)

1992D - Test of Love

Idea: ArSarapkin

Preparation: K1o0n

Tutorial
Solution (greedy)
Solution (DP)

1992E - Novice's Mistake

Idea: Noobish_Monk, K1o0n

Preparation: K1o0n

Tutorial
Solution (Python)

1992F - Valuable Cards

Idea: Noobish_Monk

Preparation: Noobish_Monk

Tutorial
Solution (C++)

1992G - Ultra-Meow

Idea: Noobish_Monk, K1o0n

Preparation: K1o0n

Tutorial
Solution (C++)
• +45

 » 4 weeks ago, # | ← Rev. 3 →   -19 Thanks for the fast text editorial!
 » 4 weeks ago, # |   0 Thanks for the fast text editorial! :D
 » 4 weeks ago, # |   0 Thanks for editorial
 » 4 weeks ago, # |   0 tks for the tutorial :D
 » 4 weeks ago, # |   0 Could you also solve problem D by using game theory logic and designing an array that will mark spots that are winning and others that are losing, so an array w[d+1] for which w[d] is winning, for every i that path[i]=='C' w[i]=losing ... I tried to solve it during the contest with this approach, but failed on implementation so I want to know if the approach is valid to polish the implementation or to try a different approach.
•  » » 4 weeks ago, # ^ |   0 just simulate the game + greedy :)
•  » » » 4 weeks ago, # ^ |   0 ok tnx
•  » » » 4 weeks ago, # ^ |   0 Sounds like what I did but since I'm noob so test 2 failed, unfortunately
•  » » 4 weeks ago, # ^ |   0 Seems like you are looking for a dp solution, one of which is described in the tutorial. However it turns out you need to keep more information than a binary value in that array because of the swimming constraint
•  » » » 4 weeks ago, # ^ |   0 Yes, but in an implementation with a vector> I could keep winning state, if 1 a char('c',...), and swimming or jumping constraint, which I could update correctly so the game conditions are satisfied.
•  » » » » 4 weeks ago, # ^ |   0 I think my submission can help you understand the implementation details. I keep in each index a $pair$ indicating whether we can reach that cell or not, and $min$ water cells swam till now.Transitions are the same as editorial
•  » » » » » 4 weeks ago, # ^ |   +3 i just simulate his optimal moves (greedy). i am him.
•  » » » » » » 4 weeks ago, # ^ |   0 Ah yes I see what he meant now. small advice: try to adjust your indentation to $4$ spaces instead of $8$ as it's more readable, and name your variables for easier idea understanding (It took me much to understand your code) and also to help you in debugging matters
•  » » » » » » » 4 weeks ago, # ^ |   +1 noted!
•  » » » » » 4 weeks ago, # ^ |   0 Thank you :)
•  » » 4 weeks ago, # ^ |   0 I did it with graphs XD
•  » » » 4 weeks ago, # ^ |   +1 :)
 » 4 weeks ago, # |   0 Notice that n∗a−b is strictly less than 10^6 , i.e., it has no more than 5 digits.Please edit that to 6 digits. Thanks!
•  » » 4 weeks ago, # ^ |   +5 that (the editorial) is correct. strictly less than 10^6 means <= 99999 -> max 5 digits :)
•  » » » 4 weeks ago, # ^ |   +7 Oh sorry, my bad :')
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   +15 10^6 == 1,000,000 less than 10^6 is 999,999 which is 6 digits. Niko-Bellic is right.
•  » » » » » 4 weeks ago, # ^ |   +4 I actually started questioning myself for a moment xD
•  » » » 4 weeks ago, # ^ |   0 u trippin
•  » » » » 4 weeks ago, # ^ |   0 oh shoot :))) so sorry. ahhh
•  » » 3 weeks ago, # ^ |   0 aap toh badmaash hain ji
 » 4 weeks ago, # |   0 A simpler implementation for F
•  » » 4 weeks ago, # ^ |   0 Could you please explain your solution?
•  » » » 3 weeks ago, # ^ |   +1 let $x$ be the number that will make our current segment good, means that if there is numbers in our segment such that $a_i \cdot a_j \cdot \cdot \cdot a_l = x$, the segment will be counted as good, however the problem wants only bad segments so we need to make sure that we can't have $x$notice that in order to have $x$ all of $a_i \cdot a_j \cdot \cdot \cdot a_l$ need to be divisors of $x$let $s$ be a set that contains any number that will make our segment good so initially it will be $s =$ { $x$ }now we iterate over the numbers, and check if this number is in $s$, if it's in $s$ then this number will make our segment good if we contain it with our current segment, we don't want that as we only want bad segments, so we need start a new segment and increase our $ans$ by $1$ and reset $s$ if the number is not in $s$, we need to work with it because lets say or $s =$ { $4$ , $8$ }, and we find $a_i =$ $2$ , that means we need $4$ or $8$ but we got $2$, what if we got another $2$ after some time ? that would be $2$ $\cdot$ $2 =$ $4$ which is a number that we are looking for, so we need to iterate over $s$ and check if ($s_i \mod a_i == 0$ ) then we add $s_i \div a_i$ to $s$so $s$ will be $s =$ { $2$ , $4$ , $8$ } and then when we get to the second $2$ we will check if its in $s$ and so on ...the lower bound is to fast things up as we may not need to iterate over all $s$ but to start from a number thats $a_i \le s_i$if its still not clear please copy my code and try to work with it and test it with samples
•  » » » » 3 weeks ago, # ^ |   0 Understood perfectly, Thanks for your nice explanation.
•  » » » » 3 weeks ago, # ^ |   0 How? i've been trying to understand how this approach doesn't exceed the time limits for hours. isn't its complexity O(n x number of divisors of x)? In that case doesn't it exceed 10^7 as no. of divisors of x can go uptil 100 and n can go up till 10^5?
•  » » » » » 3 weeks ago, # ^ |   +1 As I know, $10^7$ fits within even 1s
 » 4 weeks ago, # |   0 Is it possible for ~9k+ people to solve D in DIV 3 ?
•  » » 4 weeks ago, # ^ |   0 people are more genius than we think
•  » » » 4 weeks ago, # ^ |   0 or maybe im more dumb ? :(
•  » » 4 weeks ago, # ^ |   0 Yes, it was much easier than normal Div. 3 D.
•  » » 4 weeks ago, # ^ |   0 yes
•  » » 4 weeks ago, # ^ |   +3 All thanks to telegram
 » 4 weeks ago, # |   0 F solution should contain 17 lines of code.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 I agree. F seems easier than E, although I couldn't reach either of them during the contest. Afterwards, it took me about 10min to figure out a solution for F, while E required a fair amount of mathematical reasoning.The hardest part of F was understanding the problem statement. xD
 » 4 weeks ago, # | ← Rev. 2 →   +3 A simpler solution to F: 270026683 with a time complexity $O(n d(x) log(d(x)))$The set avoid stores values that should not occur in the current segment. For example, let x = 12, a = [2, 3, 2, ...]. Initially the set contains 12. When encountering 2, we put 6 into set, because 6*2=12; encountering 3, we put 4 and 2 into set, because 4*3=12 and 2*3*2=12. After that when encountering another 2, we find that it is already in set, so we need to split here, and reset the set with {12, 6}.
•  » » 4 weeks ago, # ^ |   0 My solution complexity is just $O(n d(x))$
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 Sorry for misreading the tutorial. Then it's a shorter but less efficient solution lol (but I think mine can also be optimized with the same trick or by using unordered_set
•  » » 4 weeks ago, # ^ |   0 oh yeahhhhhhhhh. i should've think simpler
 » 4 weeks ago, # |   0 E can be solved in constant time just iterating over the number of digits of n*a-b 270038095
•  » » 2 weeks ago, # ^ |   +3 Your solution is mind-blowing to me. Great Job! Can you give some idea behind the proof, that, no other solutions would exist besides these for the cases?
•  » » » 2 weeks ago, # ^ |   0 If you have the number of digits of n*a-b, then you can have the difference between a and b, then you can replace b in function of a, and calculate a from n*a-b.
 » 4 weeks ago, # |   0 This is my First Contest.. And I'm able to solve only A, and try B after the contest and i solved B.Is I'm the Only one who solve A with recursion?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Many people are not able to solve a single question in your first contest. You did well for your first. Also, recursion is not needed in the first one. So you might be the only one:)
 » 4 weeks ago, # |   0 Pretests were too weak. My solution of F got an FST with TL but passed pretests with time of 200ms, and in B there wasn't a pretest with big enough a
 » 4 weeks ago, # |   0 what are the conditions to get MLE like if we make a vector of 10^10 or if we make a 2-3 vectors of 10^5 like which type of dps can we make what is make value of n for an 2DP and 3DP if anyone can tell or refer me to a post telling these
•  » » 4 weeks ago, # ^ |   0 umm, can you restate? hard to read.
•  » » » 4 weeks ago, # ^ |   0 He's asking how much memory you can allocate before MLE. A vector of size 10e10 would definitely MLE, 2-3 vectors of 10^5 would be fine, 2DP would be around max 5000, and 3DP would be around max 500.
•  » » » » 3 weeks ago, # ^ |   0 oh why so less for a 2dp but its way to less
•  » » » » » 3 weeks ago, # ^ |   0 I don't understand what you're saying.
 » 4 weeks ago, # | ← Rev. 2 →   0 I solved D using 0-1 BFS. Each cell can go to no more than 10 cells next to it ( except if it contains a crocodile). So if the next cell is water the cost is 1 otherwise the cost is 0. Then after calculating the shortest path from cell 0 , the answer is YES if the cost is less than or equal k and NO otherwise.Here is my submission:https://mirror.codeforces.com/contest/1992/submission/269951020
•  » » 4 weeks ago, # ^ |   0 a bit overkill tbh...
 » 4 weeks ago, # |   0 oops i had G left with 30 minutes to spare but was too lazy to read it im math main so coudlve (maybe?) reached pupil :(
 » 4 weeks ago, # |   +11 I WANT JUSTICE.My contest submission : 269977715Same code submission: 270045857My submission getting runtime error but other submission accepted, this whole thing ruined my contest rating.Please do something about this.
•  » » 4 weeks ago, # ^ |   0 Same Code submission: 270185546Accepted Again.Please rejudge my contest solution, and change my standings in leaderboard.PLEASE AUTHORS.
•  » » 4 weeks ago, # ^ |   0 I wouldn't tunnelvision on rating. You can see here https://leetcode.com/u/echen5503/ that I had a contest with negative delta(submitted solution 2 min after contest end), then the next contest where I did well was unrated. If you are skilled enough to do it once, you can probably do it again in a later contest. GL on expert.
 » 4 weeks ago, # |   0 In problem C, numbers between $m$ and $k$ affect neither $f$ nor $g$, so their permutation is irrelevant. In fact, you don't even need $k$ to solve the problem: just iterate from $n$ down to $m+1$, then from $1$ to $m$.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 In fact, test case 3 of problem C has bad input format (maybe extra spaces in somewhere), which causes my submission 269935508 got a wrong WA in fst. If reading tokens one by one, it (270282247) gots a AC.Even little probability, if Noobish_Monk, K1o0n can take a look and rejudge, I will give much appreciate for that.
•  » » » 3 weeks ago, # ^ |   0 I looked in my generator, in fact there are no extra spaces, but there is a newline character in the end of file as it is in all the problems if it matters to you. Sadly I/we can't rejudge your submission. Sorry. Fun fact, I submitted your solution myself with no changes , it got OK. xD. I guess you're just unlucky...
•  » » » » 3 weeks ago, # ^ |   0 Thanks for your reply. It's the most sad story during my cf life. 2 problems got fst. C is mysterious wrong verdict, and F is tle due to Node.js.
 » 4 weeks ago, # |   0 Can anyone please help me correct this solution to problem DGot WA on 845th test of test case 2. Code#include using ll = long long; using dl = double long; using namespace std; const ll MOD = 1e9 + 7; bool f(int i, int m, int k, string& s, vector& dp) { //Base cases int N = s.length(); if(i >= N) return true; if(s[i] == 'C') return false; if(dp[i] != -1) return dp[i]; if(s[i] == 'W'){ if(k > 0) return dp[i] = f(i + 1, m, k - 1, s, dp); else return false; } else{ bool flag = false; for(int j = 1; j <= m; j++){ if(f(i + j, m, k, s, dp)){ flag = true; break; } } return dp[i] = flag; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; while (t--) { int n, m, k; cin >> n >> m >> k; string s; cin >> s; s = 'L' + s + 'L'; vector dp(s.length() + 1, -1); if(f(0, m, k, s, dp)){ cout << "YES" << endl; } else{ cout << "NO" << endl; } } return 0; } 
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Test9 5 1LWLLCWCCWanswer is "YES". Your code gives "NO".
•  » » » 4 weeks ago, # ^ |   0 I think It's because you're changing k in the dp state but not storing in the dp array.
•  » » 4 weeks ago, # ^ |   0 it is not enough to set dp[i] = true/false .it should be the minimum distance he can swim to reach n+1 from i
 » 4 weeks ago, # |   0 Can Someone explain me why this submission of mine (For problem F) does not give a TLE , i mean while implementing i was considering some sort of a test case which could break this algo , maybe the set runs out of overflow , or traversing the set takes too long , or something like that Here is the Link to the submission. Link
 » 4 weeks ago, # | ← Rev. 2 →   0 good contest , thanks for fast editorial !the problem D was bit different !here is my solution to the problem ( greedy , c++ ) — 269977837
 » 4 weeks ago, # | ← Rev. 2 →   +1 prblm D with iterative DP: Your text to link here...
 » 4 weeks ago, # |   0 My alternate approach for E:Let $ans = n\cdot a-b$ for some pair of integers $(a, b)$. We know the number of digits in $ans$ is equal to $|ans| = |n|\cdot a-b$ and for all $n > 1$, $n > |n|$ (here again $|n|$ is the number of digits in n). Now, $ans$ can be reformulated as:$ans = (n-|n|)\cdot a + |n|\cdot a-b$Simplifying this we get;$a = \frac{ans - |ans|}{n - |n|}$$b can be computed in O(1) once we calculate a. So traversing over all possible ans gives the answer in practically O(1) (not sure about the complexity).My implementation •  » » 3 weeks ago, # ^ | ← Rev. 3 → 0 The complexity is actually O(log^2(n*a - b)) for a\neq 1. I also did the same thing. •  » » » 3 weeks ago, # ^ | 0 I got the O(\log n) part in my calculations, which I decided to report as practically O(1) because of the bounds on n in the task. How did you get the O(\log a) part though? •  » » » » 3 weeks ago, # ^ | ← Rev. 2 → +3 I just looped through all possible values of n*a-b which take O(log(n*a-b)) time. Then, the process of computing the number of digits also take that time. (can be optimized a bit though)  » 4 weeks ago, # | ← Rev. 3 → 0 My solution for problem F is very similar to the tutorial logic but still I'm getting TLE. Can anyone point out the reason. 270213270 •  » » 4 weeks ago, # ^ | 0 Sure. Your "possible" vector should be turned into a set because you are processing the same factors over and over again. https://mirror.codeforces.com/contest/1992/submission/270260270 •  » » » 4 weeks ago, # ^ | 0 Got it, thanks. Initially I also used a map which got accepted but following the tutorial I tried optimizing my solution but missed this edge case. 270268923 •  » » » » 3 weeks ago, # ^ | ← Rev. 2 → 0 Oh nice. This one is n*d(n) instead of nd(n)log(d(n))  » 4 weeks ago, # | 0 Could someone please explain that how 270218105 gets accepted but 270217104 got TLE ? •  » » 4 weeks ago, # ^ | 0 I figured out the problem in the TLE submission. I had assumed that the products of 2 divisors of x such that the product < x will still be a divisor of x. This is clearly wrong (consider x to be 24, the divisors to be 2 and 8, 16<24 but 16 is not a divisor of 24). Thus, my curr vector contains unnecessary numbers increasing its size outside of the permissible bound. •  » » » 13 days ago, # ^ | 0 You saved me! I had worked for many hours to find where mine went wrong.  » 4 weeks ago, # | 0 anyone please explain r array here in G solution •  » » 3 weeks ago, # ^ | 0 It's for reverse factorials. They are calculated this way:r_n = inv(f_n)$$r_i = r_{i+1} \cdot (i+1)$
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Can't we take f[n]*(inv(f[r]*f[n-r]))
•  » » » » 3 weeks ago, # ^ |   0 Yeah but that's $O(log MOD)$ for every binomial coefficient, which results in longer runtime
•  » » » » » 3 weeks ago, # ^ |   0 Ohk thanks.
 » 4 weeks ago, # |   +3 I'm not getting it how the greedy is working in problem D?? As if everytime we get the log and try to jump as further as possible then in O(N) how can we be sure that we will not get any crocodile in such jump?? And if we do get the crocodile or we get the water but we have spent all the k's then how we'll make the informed decision about that in just O(N) time ??
•  » » 4 weeks ago, # ^ |   0 The thing is, with a jump you can get past any crocodile, as long as you land in either a log or water. If there is such a log, then it is best to land at the farthest possible one; otherwise, if there is water at the end of the jump, then it is best to land there, so long as there is available $k$ at that moment.
•  » » » 4 weeks ago, # ^ |   0 Thank you for your suggestion but it's still confusing to me. I found another approach using BFS which is also in order of O(N) which is less than DP.
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 A better way to look at this is, let's say you have many logs that you can jump on: -L--L-LL...... lets call last log as F If you choose any log but the last one, then any of these logs will eventually, after some jumps, have to surpass that last log (F). They can't surpass it by more than (m-1) steps. So picking the final log from the start would have granted you these (m-1) steps plus an extra one.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 if we have two logs that you can jump on one at index 1 and the other at index 8 it's always better to jump at index 8 lets say m is equal to 8 now when you jump at 1 you have 2 3 4 5 6 7 8 and 9 as options to jump on but if you jump at 8 you still have the 9 and you have now more options 10,11 ... there is no point in picking the earlier log because picking the farthest will give you more options and It will not make you miss anything
 » 4 weeks ago, # | ← Rev. 2 →   0 could anyone plz help me with my soln 270036296 of problem D . i don't know why i am getting wrong output.
 » 4 weeks ago, # |   0 In tutorial for F they said Let's prove that it works. In any optimal division, if we take the first segment of non-maximum length, we will not violate the criteria if we transfer one element from the second segment to the first. Therefore, the given greedy algorithm is correct. What does this even mean?
•  » » 3 weeks ago, # ^ |   +3 It's short for "proof by induction". If we have some split in segments, where the length of the first one isn't maximal, we can move one element from the second and it would still be a correct split, while the number of segments could've only gotten less. Doing this process with every segment is the proof for greedy
 » 4 weeks ago, # |   +29 The editorial for A doesn't prove that incrementing the smallest number is optimal when we repeat the process 5 times. It only proves that it's optimal for 1 time.
•  » » 4 weeks ago, # ^ |   -13 Yes, I agree that at the end they should have written: "Let's run this algorithm 5 times and get the answer to the problem.". But they did everything else, because at the beginning they announced that a<=b<=c, which means that the variables must be sorted initially, which means if you just do this algorithm 5 times everything will work.
•  » » » 4 weeks ago, # ^ |   +11 If my understanding is correct, that's not what he is saying. I think his point is that just because you take the locally optimal choice every time doesn't necessarily mean that you will get the globally optimal result. For this problem, it is true. That's not the case for every problem.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   -14 There are only 4 stages of this algorithm which are: 1. a = b = c (a==b,b==c) 2. a = b < c (a==b,b
•  » » » » » 3 weeks ago, # ^ |   +11 Imma be honest. I have no idea what you are talking about.
•  » » 4 weeks ago, # ^ |   +27 I came up with some proof but it doesn't sound very easy for D3A. Please tell me if you know a simpler proof. On the positive side, the following proof works for any number of operations and more than three numbers.Consider two sequences $p$ and $q$ where $p$ is the result of the greedy algorithm from the editorial and $q$ is any other sequence obtained via the same process described in the statement. I claim that $p' \prec q'$ ($p'$ minorizes $q'$) where $p'$ and $q'$ are versions of $p$ and $q$ sorted in non-increasing order. This is rather intuitive because the greedy algorithm from the editorial achieves the minimum possible sum of the first $k$ elements in sorted order for any $k$, corresponding to minorization. Consider a function $f(x) = -\log x$ on domain $[1, +\infty)$. It is convex because its second derivative $d^2/dx^2 (-\log x) = 1/x^2 > 0$ on our domain. According to Karamata's Inequality we now conclude that $\sum_i (-\log p_i) \le \sum_i (-\log q_i)$, which is equivalent to $\sum_i \log p_i \ge \sum_i \log q_i$. Exponentiate both sides to obtain $\prod_i p_i \ge \prod_i q_i$.
•  » » » 3 weeks ago, # ^ |   +34 Yeah this is overcomplicated, but the idea to take logs is very good.If we generalize to wanting to maximize the product $a_1 a_2 \dots a_k$ at the end ($a_i \ge 0$), this is equivalent to maximizing $\log a_1 + \log a_2 + \dots + \log a_k$ (we can say $"\log 0" = -\infty$).Now if we consider the function $d(n) = \log(n + 1) - \log n$, this function is strictly decreasing over $n$. Since $d(a_i)$ is the benefit we get from incrementing $a_i$, it's clear that a straightforward greedy approach of always choosing the smallest first is the right way to go.
•  » » » 3 weeks ago, # ^ |   0 Can it be proved by AM-GM inequality ? GM<=AM and equality occurs only if all of the numbers are equal , so we should always try to increase the lowest number.
•  » » 3 weeks ago, # ^ |   -23 Proof by AC
•  » » 3 weeks ago, # ^ |   +8 even without proving, it's still possible to solve in 6^3 * 1,000 time: for c1 in range(6): for c2 in range(6-c1): for c3 in range(6-c2-c1): ans = max(ans, (a+c1)*(b*c2)*(c+c3)) 
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 I believe it's possible to solve this problem for any number $n$ of initial values and any number $m$ of operations, in $O(m + n \log n)$ using a greedy approach.First, sort the initial values and append some huge number. Let $i$ denote the index of the current number, modulo $k$, where $k$ is the index of the next greater number. While $a_i$ is less than $a_k$, increment $a_i$ and then $i$. When $a_i$ becomes equal to $a_k$, increment $k$ and keep iterating until all operations are used. Finally, compute the answer.
•  » » » » 3 weeks ago, # ^ |   0 You can actually solve it in just nlogn. https://mirror.codeforces.com/contest/1992/submission/270395681
»
4 weeks ago, # |
-8

in question D he has to swim k units right? #include

# include

using namespace std; typedef long long ll;

ll f(vector &ar, int n, int k, int m) { if (n == 0) return k == 0 ? 0 : -1; ll min_steps = LLONG_MAX; bool found = false; for (int i = 1; i <= m; i++) { if (n — i < 0) break; if ((ar[n — i] == 'W' && k > 0) || ar[n — i] != 'W') { int new_k = k; if (ar[n — i] == 'W') new_k--; ll steps = f(ar, n — i, new_k, m); if (steps != -1) { min_steps = min(min_steps, steps + 1); found = true; } } } return found ? min_steps : -1; }

int main() { ll t; cin >> t; while (t--) { ll n, m, k; cin >> n >> m >> k; vector ar(n + 1, '0'); for (ll i = 1; i <= n; i++) { cin >> ar[i]; } ll check = f(ar, n, k, m); if (check == -1) cout << "NO" << endl; else cout << "YES" << endl; } return 0; } this is giving worng on test 2 idk why...the k is 2 but available only 1 W so how can k be equal ?so it shud be no ryt?

•  » » 4 weeks ago, # ^ |   0 He is allowed to use $k$ or less.
 » 4 weeks ago, # |   0 can someone tell me what is problem in my codehttps://mirror.codeforces.com/contest/1992/submission/270266835
 » 3 weeks ago, # | ← Rev. 2 →   0 Is a segment always a continuous array(subarray)?for F, input : 4 84 2 2 4optimal division should be 4 4, 2 2as per the editorial its 4, 2 2, 4.help please.
•  » » 3 weeks ago, # ^ |   +1 yes it is always a subarray
 » 3 weeks ago, # |   0 in problem G's solution, shouldn't m be MEX and not MEOW
•  » » 3 weeks ago, # ^ |   0 I am also confused on the same, I believe m should be MEX
 » 3 weeks ago, # |   0 The problem D can be solved by just iterating through the string right?
 » 3 weeks ago, # |   0 Problem: 957ECan someone explain why is this code taking so long to execute even when I've made some modifications in the range for b ?? #include using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; vector str(10001); str[1] = to_string(n); // concatanate the string n, upto a times for(int i=2; i<=10000; i++) str[i] = str[i-1] + str[1]; vector > arr; for(int a =1; a<=10000; a++){ // becuase the value, a*n-b is always upto 6 digits (10^6) // As a, b <= 10^4 and n <= 100, so a*n <= 10^6, so a*n-b <= 10^6 // so, can we also short the loop for b, based on this information ??? // define the minB and maxB based on the value of a*n int minB = max(1, a*n - 10000); int maxB = min(10000, a*n); for(int b =minB; b<= maxB; b++){ string s = str[a]; if(b < s.length()){ s = s.substr(0, s.length()-b); if(s.length() <= 6){ long long k = stoll(s); // now the equation become an - b = k if(a*n - b == k) arr.push_back(make_pair(a, b)); } } } } cout << arr.size() << endl; for(int i=0; i
•  » » 3 weeks ago, # ^ |   0 probably because u r concatenating n a times and each time it may require allocating new memory
•  » » 3 weeks ago, # ^ |   0 don't implicitly generate the string, you are creating a massive array: ['a', 'aa', 'aaa', 'aaaa', 'aaaaa', ......] which has size of A^2. Remember that strings are internally char arrays.Instead, only generate the first 6 characters. Here's my solution for reference: https://mirror.codeforces.com/contest/1992/submission/270266899
 » 3 weeks ago, # |   0 Problem F was really good, given the combination of the use of the greedy idea and the $dp$ approach to find subsequence products. Learnt something new!
•  » » 3 weeks ago, # ^ |   0 can u explain the dp approach of problem f?
•  » » » 3 weeks ago, # ^ |   0 I was referring to the same approach mentioned in the editorial. Let me elaborate it here for you.The greedy idea is to always extend our segment to the right as long as possible until it remains "bad" that is, no subsequence in the segment multiplies to $x$. This was proved in the editorial that it works, but to know when to stop extending the segment, we need to perform a dynamic programming that will tell us what all factors of $x$ have been produced by some subsequence in our current segment. Now, we maintain a set of numbers $\text{products}$ that can be obtained by multiplying the numbers of some subsequence in the segment that we are currently extending. Now, to know if we can include the current element $a[i]$ or not in the segment, we need to check if this can create a product of $x$. This can simply be done by checking if $a[i] \mid x$ i.e. $x$ is divisible by $a[i]$; and the product $\frac{x}{a[i]}$ exists in $\text{products}$. If both of the above conditions are true, then we need to end the current segment here and start a new segment from $i$ (thus making the set empty)Otherwise, we will update our set of products by iterating through it and for each product $p$ in it, we will insert the new product $p\cdot a[i]$ into the set. Note that this might involve duplication of products, so we must update the set using another temporary new set. Details can be found in this submission, which runs in approx. $1$ s. The complexity of the solution is $O(n\sqrt[3]{x})$ as $x$ has at most $\sqrt[3]{x}$ divisors.
 » 3 weeks ago, # |   0 Can anyone explain the proof of F? Why does this greedy algorithm work. I am stuck in understanding that why taking as much as possible will produce minimum number of bad segments?
•  » » 2 weeks ago, # ^ |   0 Consider the first two segments. If the first one isn't as long as it can be, we can move one element from second segment to the first and both segments are still {bad}. Second segment might become empty, no new segments appear, so by moving element to the first segment we can't mke our answer worse. After we added as many elements to the first segment as possible, we can erase it from the array and use the same logic for next segments. That's why greedy works
•  » » » 12 days ago, # ^ |   0 Thanks, I was thinking that Segments may not be continuous that's why I couldn't understand.
 » 3 weeks ago, # |   0 How a Specialist come up with these ideas?
 » 3 weeks ago, # | ← Rev. 3 →   0 Can someone explain why in problem G with \$2k
•  » » 13 days ago, # ^ |   0 Oh forget that we need calculate the sum of MEX so we need to multiply with m.
 » 2 weeks ago, # |   0 Text editorial is very intuitive..!!!
 » 9 days ago, # | ← Rev. 2 →   0 Sorry for late comment, but why doesn't my solution pass? I think I'm missing an edge case.
 » 8 days ago, # | ← Rev. 2 →   0 I did problem E using binary searching for finding value of b, and iterated on a from 1 to 1e4.273309283
 » 7 days ago, # | ← Rev. 2 →   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } here is my code https://mirror.codeforces.com/contest/1992/submission/273669300 for problem D iam getting wrong answer Yes in case 5 1 1 LLWWW , but iam running this case in local editor its giving No , what iam doing here someone please help .