### flamestorm's blog

By flamestorm, 3 weeks ago,

We hope you enjoyed the contest!

1950A - Stair, Peak, or Neither?

Idea: SlavicG

Tutorial
Solution

1950B - Upscaling

Idea: flamestorm

Tutorial
Solution

1950C - Clock Conversion

Idea: mesanu

Tutorial
Solution

1950D - Product of Binary Decimals

Idea: flamestorm

Tutorial
Solution

1950E - Nearly Shortest Repeating Substring

Idea: mesanu

Tutorial
Solution

1950F - 0, 1, 2, Tree!

Idea: flamestorm

Tutorial
Solution

1950G - Shuffling Songs

Idea: SlavicG

Tutorial
Solution
• +28

 » 3 weeks ago, # | ← Rev. 3 →   +6 thanks for the fast editorialalthough they are all empty :(
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 They are updated now with solutions
•  » » » 2 weeks ago, # ^ |   +3 still waiting for G.
•  » » » » 2 weeks ago, # ^ |   0 search hamiltonian paths
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 would recommend this blog for problem G: https://codeforces.com/blog/entry/337
 » 3 weeks ago, # |   0 A fun little exercise for G: Shuffling Songs. Consider this code that finds the longest hamiltonian path of a subset of vertices. What is the time complexity of this code? Is it $O(N^3 \cdot 2^N)$ or $O(N^2 \cdot 2^N)$ or $O(N \cdot 2^N)$? (With proper proof/arguments).
•  » » 3 weeks ago, # ^ |   0 It's O(2^n*n^2) because for each bit mask you iterate every possibile pair of songs.
•  » » » 2 weeks ago, # ^ |   0 thank u
 » 3 weeks ago, # |   0 Problems were very challenging .. liked them even though not solved them but they were good .. + lightning fast editorial
 » 3 weeks ago, # |   +2 F can be solved in O(1), so why a + b + c <= 3*10^5??
•  » » 3 weeks ago, # ^ |   0 Do you mean O(log(a)) cause I can't figure out an O(1)
•  » » » 3 weeks ago, # ^ |   +20 Depends on what you count as a primitive operation, but here's an example of a solution that can be interpreted as O(1): 253827308
•  » » » » 3 weeks ago, # ^ |   -10 can you correct the logic in this one , for 14641 i couldn't get the code right for 14641 so i edited it , though it still failed 253823896
•  » » » » 3 weeks ago, # ^ |   -9 __builtin_popcount(n) has a complexity of log(n). As you are calculating __builtin_popcount(a), your code should be considered as O(log(a))
•  » » » » » 3 weeks ago, # ^ |   +1 First of all, my code calls clz, not popcount. Secondly, it can be misleading to think of it as $O(\log)$. Explicitly looping over the bits is substantially slower because modern processors have special instructions for both clz and popcount.
•  » » » » » » 3 weeks ago, # ^ |   +20 sorry for the confusion with clz. Interesting, learnt something new, ty
•  » » » » 3 weeks ago, # ^ |   0 can you please explain what's the logic behind Padding variable ?
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I first build a complete binary tree out of nodes of degrees 0 and 2. The last level may be partially filled, and padding denotes how many nodes of degree 1 can be inserted immediately above leaves without increasing levels. After that, the second phase begins where every c insertions of nodes of degree 1 immediately above leaves increase the number of levels by 1.UPD: I thought of this variable name because padding usually comes between content (nodes of degree 2) and border (nodes of degree 0).
•  » » » » » » 2 weeks ago, # ^ |   0 but after subtracting padding, what does increase of (c-1)/c mean b/c i understand that it is 1 degree nodes ,can u please explain ??
•  » » » » » » » 2 weeks ago, # ^ |   0 It's a common way to round the division result up.
•  » » » » » » » » 2 weeks ago, # ^ |   0 ok, thank u
•  » » 3 weeks ago, # ^ |   +10 I know it existed, but I didn't find the optimization from $\mathcal{O}(a+b+c)$ to $\mathcal{O}(\log(a))$ (or $\mathcal{O}(1)$) very interesting, and the core idea is the same.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 solution you can check this solution for O(1)
•  » » » » 2 weeks ago, # ^ |   0 bro u used power function is not o(1)
•  » » » » 2 weeks ago, # ^ |   0 int ha=log2(a); is logarithmic
•  » » 3 weeks ago, # ^ |   +7 'cause it is div4 :)
•  » » 4 days ago, # ^ |   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; } For this constraint, queue solution is also accepted. Queue Solution (AC)
 » 3 weeks ago, # |   0 thanks you for the quick editorial and good round!
 » 3 weeks ago, # |   -17 Hello I am gokula kannan siva ji
•  » » 3 weeks ago, # ^ |   -10 why am i geting downvoted i am gokula kannan siva ji < : (
•  » » » 3 weeks ago, # ^ |   0 don't be sad bro, I upvoted
•  » » » » 2 weeks ago, # ^ |   +3 thank you bro i appreciate it :( they are just mad for no reason
 » 3 weeks ago, # |   +5 Hey! I am solving G using DFS to find the component of largest size. Why is it giving WA on test 5. Please look at my SubmissionDetailed approach: create a graph with vertices as songs from 1 to n. Two vertices are connected if they have a common artist or genre. Using dfs, find the largest component. Is my approach Wrong??
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -7 Consider  a | b-c-d-e-f-g |___| Is this graph connected? Can you find a way to arrange all vertices in order?
•  » » » 3 weeks ago, # ^ |   +4 so how to approach this? i read about hamiltonian path! but i didnt get it! please explain
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +6 [EDIT: This solution is incorrect, check end of this comment]I also did with DFS and DSUs. The trick is do DFS from a node and find the length of the longest "path" from each of them. You can do this by returning (max path length + 1) at each node. ll dfs(ll node, vector &nb) { dfsvis[node] = true; ll plen = 0; for (auto &n : nb[node]) { if (dfsvis[n]) continue; plen = max(plen, dfs(n, nb)); } dfsvis[node] = false; return plen+1; } You will notice that I'm setting dfsvis[node] = false; while exiting the node. This ensures that every path is tried and non-optimal results aren't returned. (Think what if a node that is part of the longest path is visited before we can check for it, that's why we unvisit it)However only this solution will give a TLE when all 16 songs have same genre and writer coz you check every possible path. To counter this, I checked if the max length that I'm getting is the max possible. If it is no point in keeping checking.Now what is the max possible length? The size of the connected component! I found it using DSU, you can use other methods. To check, at each branch, I add the max length of that branch and the number of visited node and see its it's equal to the size of the connected component.Submission: 253849577 [HACKED]EDIT: This submission has been hacked and I discovered that my code has n! worst case time complexity.
•  » » » 3 weeks ago, # ^ |   0 Let's suppose vertex a and b both have first string(genre) same as first string of c then we can arrange like a-b-c-d-e-f-g.consider other case like a,d both have second string(writer) same as second string of c then we can arrange like b-c-a-d-e-f-g.so trying all possible case i guess we always find some arrangement
•  » » » » 3 weeks ago, # ^ |   0 You don't need to suppose anything. The graph I shared explicitly means that there is nothing common between vertex $a$ and any other vertex except vertex $d$. How would you find an arrangement then? Hint : It's not possible.But if you stick to your strategy of finding maximal connected component size, you'd get an incorrect answer.
•  » » » 2 weeks ago, # ^ |   0 This isn't a good counter-example since this graph cannot exist (a must have an edge with at least one of c/e, or c must have an edge to e). Add an edge between c and e, and that suffices for a graph with no Hamiltonian path under the constraints of this problem.
•  » » » » 2 weeks ago, # ^ |   0 Fair enough. The OP had an impression that their algorithm must be true for general graphs as well, hence I randomly constructed a counter example.But you're correct, given the context of this problem, there should be an edge between c and e. Fixed.
 » 3 weeks ago, # |   0 what would be the rating for problem E? just wondering
•  » » 3 weeks ago, # ^ |   0 around 1300
•  » » 3 weeks ago, # ^ |   0 realistically 1200-1300, Clist says its 1500:https://clist.by/problems/
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Maybe 1200-1300
•  » » 2 weeks ago, # ^ |   0 maybe around 1200-1300, maximum ~1500
 » 3 weeks ago, # |   0 thanks for the solutions!
 » 3 weeks ago, # |   +1 I loved the problem G. The constraints were a subtle hint already but I tried to build a graph between connected components (an edge between song $i$ and $j$ iff genre or artist is same). After looking at the graph, it was pretty evident it is a Hamiltonian Path bitmask DP. Figuring it out was very fun! Great problemset overall for Div4 users.
 » 3 weeks ago, # |   0 why is my submission for E wrong tho i tested them all? ;-; here's my submission: 253815920
•  » » 3 weeks ago, # ^ |   0 try case 1 2 aa
 » 3 weeks ago, # |   0 Can anyone explain the reasoning behind the Time complexity Anaylsis given for D? I didnt get the idea or how those cubic/quantic equations got formed.
 » 3 weeks ago, # |   0 can someone explain solution to problem E
•  » » 3 weeks ago, # ^ |   0 brute force check for every factor of n
•  » » 3 weeks ago, # ^ |   0 Notice that the answer can only be a divisor of n, so we have to calculate all the divisors.Now Try to form a new string (formed by concatenation of a prefix of s), Example s= "abba" and divisor d= 2; prefix = "ab". The new formed string will be "abab". (do the same thing with suffix ="ba") Now compare the 2 formed strings with s, if we find more than 1 difference we move on to the next divisor, else, d is our answer.Hope this helps.
•  » » » 2 weeks ago, # ^ |   0 thanks got it now
•  » » » 2 weeks ago, # ^ |   0 why do we only need to consider concatenation of a prefix or suffix?why do we ignore a potential substring in the center?sorry! i just started CF
•  » » » » 2 weeks ago, # ^ |   +1 u can take whatever 2 substrings you want but they should not be overlapping
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 No. (let d be a divisor of n) The strings must start from an index divisible by d and with length d .this comment explains in more detail
•  » » » » » » 2 weeks ago, # ^ |   0 i supposed that the lenght of substring is a divisor of n
•  » » 3 weeks ago, # ^ |   0 One straightforward optimization can be that once i crosses n/2, you can be sure that the answer is n.
 » 3 weeks ago, # |   0 I was a little disappointed with the pretest in task G. It was clearly my fault for underestimating the problem. But I was disappointed that out of 38 pretests, not a single one made simple DFS got Time Limit Exceeded in a task where you intended dp using bitfield as the correct answer.
•  » » 3 weeks ago, # ^ |   0 253766687 << Yes, here are my code with dumb approach, and it passed during competition, and hacked immediately I showed this code to other ones.
 » 3 weeks ago, # | ← Rev. 2 →   0 Explain why it is impossible to find a component in G with the maximum number of vertices. Essentially, vertices have two types of edges, those connected by author and those connected by genre. If there are > 2 edges at a vertex, then some vertices will form a cycle, where the order is no longer important.
•  » » 3 weeks ago, # ^ |   0
 » 3 weeks ago, # | ← Rev. 2 →   0 For problem D why cant we just factorize the given number and if the prime factorization contains any digit which are not binary decimal then we will multiply them together lets call it as Product and the numbers which are binary decimal we will leave them as it is. Now if the Product is binary decimal then answer is yes else no ? if the number is already a binary decimal we will simply return yes
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 Consider $12321 = 3^2\cdot 37^2$.
•  » » » 3 weeks ago, # ^ |   0 Yeah, it quickly becomes slow if n is bigger than 10^5
•  » » 3 weeks ago, # ^ |   0 I've also done it like that. First prime factorization, and if some primes are not "binary" ones then just brute force it to check if there is a way to multiply them to obtain the binary number. Prime factorization is O(sqrt(n)) and there are at most 6 primes to brute force under 100000.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 but this method is giving error on test 2 https://codeforces.com/contest/1950/submission/253788629 here is my solution
•  » » » » 3 weeks ago, # ^ |   0  int count = 0; for(int i = 0 ; i < size ; i++){ pro*=arr.get(i); if(isBinary(pro)) { pro = 1; count++; } } if(pro==1) System.out.println("YES"); else System.out.println("NO"); Instead of this, erase all binary prime factors and pass the remaining primes to the recursive function with two nested for loops, erase both elements if they multiply to a binary number and do a recursive call on remaining primes. If no elements are left in the primes vector then binary multiplies were found. here's my solution https://codeforces.com/contest/1950/submission/253817219
•  » » » » » 3 weeks ago, # ^ |   0 Got it. Thank You
 » 3 weeks ago, # |   0 Can someone please try and hack my E solution. Submission Link
 » 3 weeks ago, # | ← Rev. 3 →   +12 My solutions to problems A codeO(1) #include // Nya #define all(x) x.begin(),x.end() // Nya #define rll(x) x.rbegin(),x.rend() // Nya #define sz(x) x.size() using ll = long long; using namespace std; void Solve() { ll a,b,c; cin >> a >> b >> c; if (a < b && b < c) { cout << "STAIR\n"; return; } if (a < b && b > c) { cout << "PEAK\n"; return; } cout << "NONE\n"; } int main() { cin.tie(nullptr)->sync_with_stdio(false); ll tt = 1; cin >> tt; while (tt-->0) { Solve(); } } My solutions to problems B codeO((n * 2) ^ 2) In this problem it was possible to notice that when numbers (i/2) and (j/2) that they had to be of the same parity #include // Nya #define all(x) x.begin(),x.end() // Nya #define rll(x) x.rbegin(),x.rend() // Nya #define sz(x) x.size() using ll = long long; using namespace std; void Solve() { ll n; cin >> n; n*=2; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if ((i / 2 + j / 2) % 2 == 0) { cout << "#"; } else { cout << "."; } } cout << '\n'; } } int main() { cin.tie(nullptr)->sync_with_stdio(false); ll tt = 1; cin >> tt; while (tt-->0) { Solve(); } } My solutions to problems C codeThis code can be considered in O(1) complexity. I break this line that is given for hours and minutes if the time is on the clock less than 12 or equal to 24, then it will always be AM in other cases PM. And then look at the clock #include // Nya #define all(x) x.begin(),x.end() // Nya #define rll(x) x.rbegin(),x.rend() // Nya #define sz(x) x.size() using ll = long long; using namespace std; void Solve() { string s; cin >> s; ll hh = stoll(s.substr(0, 2)); string t = (hh < 12 || hh == 24 ? "AM" : "PM"); if (hh == 0) hh = 12; else if (hh > 12) hh -= 12; cout << (hh < 10 ? "0" : "") << hh << s.substr(2, 3) << " " << t << '\n'; } int main() { cin.tie(nullptr)->sync_with_stdio(false); ll tt = 1; cin >> tt; while (tt-->0) { Solve(); } } My solutions to problems D codeMy logic consisted of creating an array that would store all binary decimal numbers. 1. I considered if the number consists only of the digits 1 and 0 then if it consisted it displayed "YES" If not then I took the number n and divided it by all binary numbers, if the cycle cannot divide anymore then the answer is NO, otherwise if it came to the cycle n == 1 then the answer is YES #include // Nya #define all(x) x.begin(),x.end() // Nya #define rll(x) x.rbegin(),x.rend() // Nya #define sz(x) x.size() using ll = long long; using namespace std; set pr; void Rec(ll sum) { if (sum > 1e5) return; pr.insert(sum); Rec(sum * 10); Rec(sum * 10 + 1); } void Solve() { ll n; cin >> n; ll p = n; ll null = 0; ll one = 0; string s = to_string(n); while (p > 0) { null+=(p % 10 == 0); one+=(p % 10 == 1); p/=10; } if (null + one == sz(s)) { cout << "YES\n"; return; } bool ans = true; while (n > 1) { bool q = false; for (auto & it : pr) { if (it == 1) continue; while (n % it == 0) { n/=it; q = true; } } if (!q && n > 1) { ans = false; break; } } cout << (ans ? "YES\n" : "NO\n"); } int main() { cin.tie(nullptr)->sync_with_stdio(false); ll tt = 1; cin >> tt; Rec(1); while (tt-->0) { Solve(); } } My solutions to problems E codeLet's note that the length of the string k — can only be a divisor of n — the size of the string. In my logic I went by the size that it might be. Then I took cycle 2 which one might say created substrings from i to i + d i — where we are d is the divisor, which we consider to be the length . 3 in a loop I simply checked whether the string matches the condition. I remind you of the condition “Find the length of the shortest string k, such that several (possibly one) copies of k can be concatenated together to form a string the same length as s, and there is at most one different character". Complexity of the algorithm that is implemented sqrt(n) * log(n) * n #include // Nya #define all(x) x.begin(),x.end() // Nya #define rll(x) x.rbegin(),x.rend() // Nya #define sz(x) x.size() using ll = long long; using namespace std; void Solve() { ll n; cin >> n; string s; cin >> s; vector divs; for (int i = 1; i * i <= n ; i++) { if (n % i == 0) { divs.push_back(i); if (i != n / i) divs.push_back(n/i); } } sort(all(divs)); for (auto& d : divs) { bool ok = false; for (int i = 0; i < n; i += d) { bool q = true; string t = s.substr(i,d); ll len = 0; ll cnt = 0; for (int j = 0; j < n; j++) { if (t[len % d] != s[j]) { cnt++; } if (cnt > 1) { q = false; break; } len++; } if (q) { ok = true; break; } } if (ok) { cout << d << '\n'; return; } } } int main() { cin.tie(nullptr)->sync_with_stdio(false); ll tt = 1; cin >> tt; while (tt-->0) { Solve(); } } F sadly I didn’t solve it, but I had the logic for creating a binary tree, I just didn’t have time to implement it))My solutions to problems G codeIn this problem it is more difficult to implement dp than to come up with logic. In this problem you just need to go through all the permutations.Even the authors gave hints that this is due to permutations. Problem limits1 <= n <= 162^n < 2^16^ — degree #include // Nya #define all(x) x.begin(),x.end() // Nya #define rll(x) x.rbegin(),x.rend() // Nya #define sz(x) x.size() using ll = long long; using namespace std; void Solve() { ll n; cin >> n; map mp; vector> par(n); for(ll i = 0; i < n; i++) { cin >> par[i].first >> par[i].second; mp[par[i].first]++; mp[par[i].second]++; } ll cnt = 0; vector> kol(n); for (auto & [x,y] : mp) y = ++cnt + 1; for(ll i = 0; i < n; i++) kol[i].first = mp[par[i].first],kol[i].second = mp[par[i].second]; ll ans = 0; ll TwoLenMask = (1<> dp(1 + n + 1 , vector(1 + TwoLenMask + 1, -1)); function rec = [&] (ll TwoLenMask,ll len,ll n) { if(TwoLenMask == 0) return 0LL; if(len != -1 && dp[len][TwoLenMask] != -1) return dp[len][TwoLenMask]; pair cnt = {-1,-1}; if (len != -1) cnt = kol[len]; ll ans = 0; for(ll i = 0; isync_with_stdio(false); ll tt = 1; cin >> tt; while (tt-->0) { Solve(); } } 
 » 3 weeks ago, # |   0
 » 3 weeks ago, # |   0 How can this solution for D have tle,its constant time
•  » » 3 weeks ago, # ^ |   +22 💀
•  » » 3 weeks ago, # ^ |   0 And she's buying a stairway to Heaven ....
 » 3 weeks ago, # | ← Rev. 2 →   0 253803810 Can someone help me why this code for F doesn't work.. My logic was that if c=a+1, then answer is possible... So first try to find the minimum height of the binary tree that could be made with a : it will turn out to be ceil(log2(a))+(ceil(log2(a))==floor(log2(a))). Now to maintain the same no of leaf nodes c, for each of the leaf node in the above binary tree formed with a add a single child to each of the leaf...so basically for every leaf node filled at the ith level of height, the next addition will increase the height by one after all leaf in that level is given a child...this seems to be right but why doesnt my solution work? please help meedit i solved it...it was just a small issue...instead of dividing it by no of leaf node for this tree, i divided it by no of leaf node of a complete graph... answer (O(1) solution): 253841056
 » 3 weeks ago, # |   0 can someone explain me this approach for problem d ? 253830700
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 bitset<5>(i).to_string() is equivilant to bin(i)[2:] in python it returns the binary of i as a string then we use stoi (string to integer) to turn it back to an integer so we can divide with it. i used something like that in my code 253793921
 » 3 weeks ago, # |   0 In solution of E why are we only checking for prefix or sufix of length l and not and string of length from the middlee?
•  » » 3 weeks ago, # ^ |   0 because atmost 1 char can be different, so if the string is valid we can clearly see that the repeating substring completely matches with the characters of S in either a prefix or suffix or both
•  » » » 3 weeks ago, # ^ |   0 Thankss!
 » 3 weeks ago, # |   0 F can be solved in O(1) if you know the property of complete binary trees (number of nodes at each level increases by a factor of 2) and a little bit of maths.
•  » » 3 weeks ago, # ^ |   0 Indeed, here is a solution. https://codeforces.com/contest/1950/submission/253859143
 » 3 weeks ago, # |   0 253824980WHY IS THIS WRONG QUES 4
•  » » 3 weeks ago, # ^ |   0
•  » » » 3 weeks ago, # ^ |   0 You only considered good numbers divisible by 11 and 10, while not all of them have that attribute.An example of such good numbers, and very possibly the one caused you a WA, is $10201$ ($101^2$).
•  » » » » 3 weeks ago, # ^ |   0 ok thanku so much,will u share your soln plz
•  » » » » » 3 weeks ago, # ^ |   0
 » 3 weeks ago, # |   0 thanks for very fast editorial.
 » 3 weeks ago, # |   0 Why didnt Dp worked for the solution D. Its shows TLE. Here is my solution : https://codeforces.com/contest/1950/submission/253751070. PLEASE HELP
•  » » 3 weeks ago, # ^ |   0 there are no constraints on n over all test cases.
 » 3 weeks ago, # | ← Rev. 2 →   0 after knowing that c == a+1 in F the problem became very easy and solved it in 3 lines submission. the leaves are what bothered me when solving it in the first place
 » 3 weeks ago, # | ← Rev. 2 →   +1 253841056My solution in O(1) using maths...
 » 3 weeks ago, # | ← Rev. 2 →   +5 I believe on question E, instead of trying for all n, we can first compute the divisors in O(sqrt(n)) with the following: go until i * i <= n and, if n % i == 0, add to the divisors array not only i, but also n / i.
 » 3 weeks ago, # |   +5 2nd question was very bad question.I hate such type of questions
•  » » 3 weeks ago, # ^ |   0 boo hoo. grow up.
•  » » » 3 weeks ago, # ^ |   0 "Grow up"? You unironically have Andrew Tate as your profile picture.
•  » » » » 2 weeks ago, # ^ |   0 so?
 » 3 weeks ago, # |   0 How can we solve G using DSU, basically find size of largest component ?
•  » » 3 weeks ago, # ^ |   0 finding biggest component wont work! look at this
 » 3 weeks ago, # | ← Rev. 2 →   0 Can anyone share the solution for D by DP?
•  » » 3 weeks ago, # ^ |   0
 » 3 weeks ago, # |   0 Thank you so much for answering my question fast during the contest (I indeed am very bad at reading) and for providing very high quality problems (I only did C D F but they were insanely interesting).
 » 3 weeks ago, # | ← Rev. 2 →   0 Another weak pretests day? What is it with codeforces and weak pretests.... (problem E)
 » 3 weeks ago, # |   0 Prb-E, Can someone tell time complexity of my solution, my understanding says it's same as author(All numbers at most 10^5 have at most 128 divisors, so this will take ∼128⋅10^5operations, which is fast enough), but I am missing something, https://codeforces.com/contest/1950/submission/253828002
 » 3 weeks ago, # | ← Rev. 2 →   0 nvm, my assumption was wrong
 » 3 weeks ago, # | ← Rev. 2 →   0 .
 » 3 weeks ago, # |   +8 Adding my live coding + commentary here: https://www.youtube.com/watch?v=kQOWiTvgah0&ab_channel=DecipherAlgorithmswithSaptarshiI'd be glad if somebody finds it beneficial!
 » 3 weeks ago, # |   0 Hi, all why my solution G will WA 5? https://codeforces.com/contest/1950/submission/253786544 it also uses bitmask, and I think the order doesn't matter. Thanks for your help!
•  » » 3 weeks ago, # ^ |   0 Oh, I find a example for WA 5: 7 a b c b c d c e f e f g z danswer should be 1 not 0
 » 3 weeks ago, # |   0 Is it possible to solve the problem D using sieve? I'm trying to factorize the primes and then check if I can make some pairs decimal digits
•  » » 3 weeks ago, # ^ |   0 Here is a simpler solution for D : https://codeforces.com/contest/1950/submission/253868766 I thought all possible combinations of 0 & 1 less than 1e5 from which dividing the number and checking if it is divisible by these numbers the answer is okay or not. Also I divided in descending order other wise number like 1001 will cause problem as it will be divided by 11 and leave some number which is not 1. I hope it helps.
 » 3 weeks ago, # |   0 i just want to know that for e question,i submitted my code in c++17 and it got wrong answer on test2,then after contest i checked that test and it was giving right answer on my visualstudiocode compiler and then i submitted that same code in c++20 and it got accepted,now i want to know why is it so and am i responsible for this mistake of choosing compiler or is it a error from codeforces;s side
 » 3 weeks ago, # |   0 Here is a simpler solution for D : https://codeforces.com/contest/1950/submission/253868766 I thought all possible combinations of 0 & 1 less than 1e5 from which dividing the number and checking if it is divisible by these numbers the answer is okay or not. Also I divided in descending order other wise number like 1001 will cause problem as it will be divided by 11 and leave some number which is not 1. I hope it helps.
 » 3 weeks ago, # |   0 Problem G was great
 » 3 weeks ago, # |   0 tourist getting WA1 on A is really funny to me for some reason
 » 3 weeks ago, # |   0 Wrote G for 80 minutes, 3KB of non-template code, only to find I went in the wrong direction. I tried to build a bipartite，one side is Genre and the other is Writer, and check for a Euler path, but it doesn't work on example 4 When can I AK Div4......
 » 3 weeks ago, # |   0 I am newbie to competitive programming. I appeared for this contest and solved 3 problems (yay, albeit with a lot of trial error). In the contest announcement page, it showed that it was rated for participants with ratings <= 1400, so it should have been rated for me. But I don't see that being reflected on my profile page under contests. I don't know what happened. I would be glad if anyone could clear up my confusion.
•  » » 3 weeks ago, # ^ |   0 It would be updated once the open hacking phase ends.
•  » » » 3 weeks ago, # ^ |   0 Thank you for the clarification!
•  » » 3 weeks ago, # ^ |   0 After every contest there is an open hacking phase where participants try and hack each other. Only after that the system will start updating ratings . In general it takes 24 hours to update ratings . But for div 4 rounds it might take more than that
 » 3 weeks ago, # | ← Rev. 2 →   0 (found)
 » 3 weeks ago, # |   0 Is my intuition for G correct, because i am getting wrong answer in test 5, testcase 168. approach is to create a graph, and each category of artists and genre represent an edge between two adjacent nodes, ie.if two nodes have same genre or same artist then there will be edge between them. so after we create a graph we can just find the size of largest connected component and print n-c.(n is total number of nodes)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 No, being connected doesn't mean that you can make a simple path that visits all nodes.
•  » » » 3 weeks ago, # ^ |   0 can you explain why that might be the case?.Because what i am thinking is, there will always exist a valid simple path in which we can arrange the elements of that particular cc.
•  » » » » 3 weeks ago, # ^ |   0 This is the simplest counterexample I can think of: which can be created with this input: https://ideone.com/Lvl1xi
•  » » » » » 3 weeks ago, # ^ |   0 thank you very much.:)
•  » » » » » 3 weeks ago, # ^ |   0 how did you solve this question?
•  » » » » » » 3 weeks ago, # ^ |   0 Bitmask DP is probably the simplest, for example if you do top-down DP then you can set $dp[i][bitmask]$ = maximum length of the path you can further advance when you visited vertices in $bitmask$ and you're currently at vertex $i$, then it is $max(dp[j][bitmask | (1 \lt \lt j)])+1$ where $i$ and $j$ are connected by an edge.
•  » » 3 weeks ago, # ^ |   +3 It is not necessary that if a component is connected , then you can get an ordering for each vertex in that component following the rule for adjacent songs. So, instead of size of component , we need to find the longest path in each component. That gives TLE
•  » » » 3 weeks ago, # ^ |   0 ohk got it. thanks.
 » 3 weeks ago, # |   0 Can anybody help me in figuring out where my solution is wrong for "1950D — Product of Binary Decimals"https://codeforces.com/contest/1950/submission/253812424it would be great help!! thanks
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I just read through your code, consider trying to get the case 1210 = 11*11*10 to return print YES correctly.
 » 3 weeks ago, # |   +1 name of problem D was a hint about its tag. Spoiler
•  » » 2 weeks ago, # ^ |   0 ?
•  » » » 2 weeks ago, # ^ |   0 it was a troll. (DP : dynamic programming) tag of problem D.
 » 3 weeks ago, # |   0 Just 1 char from AC :sob:
 » 3 weeks ago, # |   0 Ive seen many solutions for G problem using dp + bitmask. Could someone explain why only using bitmask and trying to take all the vertices you can doesnt work? Here my solution . I just used bitmask + bfs but got wa on test 5
•  » » 2 weeks ago, # ^ |   0 How do you find the optimal way to reorder the elements?
 » 3 weeks ago, # |   0 when i don't add the condition (c ==a+1), can anyone tell me the testcase where this code fails?
 » 3 weeks ago, # |   0 Can anybody explain how this code gets AC? https://codeforces.com/contest/1950/submission/253676853
•  » » 3 weeks ago, # ^ |   0 He did a brute force and store all the binary decimals till 10^5 size, its genius, I would have never thought of it...
•  » » » 2 weeks ago, # ^ |   0 I mean, why is it correct? Is it possible to prove that this solution is correct?
•  » » » » 2 weeks ago, # ^ |   0 find all the binary decimals till 10^5 is easy, you jut have to do the combination of 0 and 1 , and then just check with the number to see if it is divisible by our stored numbers , TC should be, (O(len(stored) + (n//10)), and len(stored) is 30 ,so O(30+ N) 
•  » » » » 2 weeks ago, # ^ |   0 I've done something similar 253775386.Binary Decimal is a number with only $1$ or $0$ in its decimal notation.So, it is quite intuitive think about all possible binary decimals.For length $1$ -> $1$ $\newline$ For length $2$ -> $10, 01$ $\newline$ For length $3$ -> $100, 101, 110, 111$ $\newline$ For length $4$ -> $1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$ $\newline$ For length $5$ -> $10000, 10001, 10010, 10011, 10100, 10101, 10110, 10111,$ $\newline$ $11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111$ $\newline$ For length $6$ -> $100000$ since $n \leq 10^5$ $\newline$Now, for a given $n$ to be product of binary decimals, either it is one of the above mentioned numbers or it is a product of $2$ or more above mentioned binary decimal numbers.So, we can just recursively check whether it is divisible by any of these above mentioned numbers very easily. My Codebool check(vector &arr, int n) { if (n == 1) return true; for (auto x : arr) { if (n % x == 0) return check(arr, n / x); } return false; } 
•  » » » » 2 weeks ago, # ^ | ← Rev. 3 →   0 Guys, they wanted a proof, not a step-by-step implementation guidance meant for a toddler...For the OP: At least until $10^5$ size, I am observing that for every two distinct coprime binary decimals, their sets of prime divisors also don't intersect. I believe that to cause an unexpected division to fail this kind of solutions, the former condition must not hold.(This is by far just my observation and intuition, so take it with a grain of salt)
•  » » » 2 weeks ago, # ^ |   0 you only need 10, 11, 100, 101, 110, 111 — all the factors below the sqrt(10^5)
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Suppose you can write $n$ as a product of binary decimals, say $a_1, a_2 \cdots a_n$ (in increasing order). Now when you delete $a_n$, the rest are still guaranteed to be binary decimals. However, if you follow another strategy, say like dividing by a smaller number first, some $a_i$ may no longer be a binary decimalEdit: nvm, this isn't good enough
•  » » » 2 weeks ago, # ^ |   0 Okay, I believe I found a counterexample, suppose we have$1001 \times 1001$, now the submission would first delete $11 * 1001$ = $11011$, and the remaining factor would be $91$, so it would be $NO$ instead of $YES$, the counterexample is $1002001$, and I can't really find a smaller one
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 WOW thanks! I suppose there was a reason I couldn't prove that solution for 2 hours.
 » 3 weeks ago, # |   0 Waiting for the tutorial of G...
 » 3 weeks ago, # |   +3 I want to use DSU to solve G but failed ，who could tell me why，I want to find the biggest set f[k] and return n-size[k] thank you
•  » » 2 weeks ago, # ^ |   0 A test like this would fail you: 1 7 a x a y b y b z c z d y d t It's clear that this graph is connected, but the answer would be 1 rather than 0.
•  » » » 2 weeks ago, # ^ |   0 I also got help from the graph, but I was looking for the length of the longest path in it Can you tell me the reason for WA 3 of this code: https://codeforces.com/contest/1950/submission/253975967
•  » » » » 2 weeks ago, # ^ |   0 You are doing the DFS wrong if you want to find the longest path: vis[a] must be unset at the end of dfs() function, otherwise it would skip a lot of paths, possibly the longest included.Despite the approach of finding longest path was correct, however, a naive/exhaustive DFS will be inefficient with $n \le 16$ — as the complexity for the number of any paths in a graph would be $\mathcal{O}(n!)$, so even at the most optimistic scenario, you would encounter failure at test #44 anyway.
•  » » » » » 2 weeks ago, # ^ |   0 thanks a lot
•  » » » 2 weeks ago, # ^ |   0 thanku bro
 » 3 weeks ago, # |   0 Can anybody tell what's wrong with (G)this submission, I am getting WA on test case 3 , can't find the mistake
•  » » 3 days ago, # ^ |   0 I am getting same error on test case 3 for 150th case my solutionbut when I use max function it works?
 » 3 weeks ago, # | ← Rev. 2 →   0 A better solution: Was 2 min late for the submission in the contest... O(log(a)) TC [submission:253825565]  import sys input = sys.stdin.buffer.readline read = sys.stdin.buffer.read from math import log2 as l for _ in range(int(input())): a,b,c=map(int,input().split()) if a>0: h=int(l(a))+1 f=a+1 cf=b t=pow(2,h-1)-(((2*a+1)-(pow(2,h)-1))//2) b=int(max(b-t,0)) h=h+((b+(f-1)))//f if a+1==c : print(h) else: print(-1) else: h=b if c!=1: print(-1) else: print(h) 
 » 3 weeks ago, # | ← Rev. 2 →   0 O(logn) solution for problem f
 » 3 weeks ago, # |   0 Can anyone help me with this solution, how is this different from the one in tutorial?
•  » » 2 weeks ago, # ^ |   0 why did you assume it's a monotonic function you have too check for all factors and choose the min one
•  » » » 2 weeks ago, # ^ |   0 Thanks for the catch :)
 » 2 weeks ago, # | ← Rev. 3 →   0 can't g be solved by optimizing the code for finding the longest path in a graph problem
•  » » 2 weeks ago, # ^ |   0 The length that can be filled does not satisfy monotonic conditions, so binary search cannot be used
•  » » » 2 weeks ago, # ^ |   0 yeah but i meant can we add some conditions in the dfs code only so that we don't get tle in tc 33
•  » » » » 2 weeks ago, # ^ |   0 oh sorry, i reply wrong place, by the way i encountered the same problem as you in the competition, and the maximum complexity of dfs is n! And 16!>= 2e11
 » 2 weeks ago, # |   -109 thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33thanks for super duper fast editorial MikeMirzayanov !thanks for the greatest platform ever Codeforces and also Polygon <33
•  » » 2 weeks ago, # ^ |   0 What's wrong with you bro? Are you expressing your gratitude or making fun of him?
•  » » 2 weeks ago, # ^ |   0 What's going on here, please don't fill comment section like that.
 » 2 weeks ago, # |   0 Can any kind soul please explain all types of solutions with time complexities $O(a+b+c)$, $O(log(a+b+c))$, $O(1)$ for 1950F - 0, 1, 2, Tree! clearly and intuitively :(
 » 2 weeks ago, # |   0 I have a question. yesterday I sent in and was accepted for four problems in the Division 4 contest while now it turns out that I only sent in one. Why?
•  » » 2 weeks ago, # ^ |   0 Be patient, system testing is currently in progress. Your three others are in the line for rejudging.
•  » » » 2 weeks ago, # ^ |   0 thank you for your reply
•  » » » 2 weeks ago, # ^ |   0 what do you mean by rejudging? sorry i am new here
•  » » » » 2 weeks ago, # ^ |   0 Normally in a Codeforces contest, in-contest submissions are judged by a preliminary testset (or more commonly called pretests) to reduce server load. After the contest ends (and with an extra delay for preparation and such), all AC submissions will be rejudged in a phase called "system test" with the full testset available.For Div.3, Div.4 and Educational however, the in-contest testset is complete, yet after the contest ends, a 12-hour open hacking phase is presented for community to hack any AC submissions they felt incorrect but the original testset missed. After the hacking phase, those hacks are added to the testset, and after some more delay for preparation, system test will kick in.
 » 2 weeks ago, # |   0 Please help this suffering guy. In Problem E: Why only prefix and suffix of length of divisors of n is taken, I took all possible substring of the length of divisors of n instead of only prefix and suffix, and it will sure give TLE.
•  » » 2 weeks ago, # ^ |   0 same question, got TLE by taking all possible substrings
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Because it can be proven that if the prefix and suffix of some substring length c both don't pass that means that there must be more than 1 character for which the K-string is different than the original. You don't use any substrings in between because it is not optimal and doesn't make any sense to concatenate those substrings together some number of times to where the length of the entire string is equal to the original string because you are introducing offsetting character's to the original string from the get go. So, you don't even check those cases in the first place because anyway once you do that you are introducing wrong characters and your going in the wrong direction. for example in a string abcabcabc it makes absolutely no sense to ever check the substring "bca" because no matter how many times you concatonate this string together, the characters just offset. because "abc" != "bca".it's possible that you may have just overlooked that you compare the strings head on.
•  » » » 2 weeks ago, # ^ |   0 Wow, nice explanation thanks for your help. I really appreciate it. Codeforces community is really good.
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   0 Let's consider Problem E without the "1 mistake rule".If that were the case, it would be enough to check all of the divisors of n (let d be a divisor of n) and only test the prefix of length d.However, with the "1 mistake allowed", it's not guaranteed that the prefix is the correct pattern (perhaps the only mistake is within it). That's why we need another string to act as our pattern. You can use the next string starting from d of length d s[d:2*d] or the suffix s[n-d:]. it might be easier to spot in this test case : 8 hshahaha In the contest, I implemented this idea without proving it. It was based on intuition.
 » 2 weeks ago, # | ← Rev. 5 →   0 Thanks for the complexity analysis in D. Note that most of the 30 numbers are IGNORED so the complexity is far lower than n^0.587.If you do precomputation then its about $O(N^{1.4})$ (not a tight bound just a bigger bound than $O(N^{1+(log(2)/log(10))}$)).
 » 2 weeks ago, # |   0 Sorry, can anyone tell me where the problem is with this code? https://codeforces.com/contest/1950/submission/253805652 I made a graph and put an equal edge between both songs with at least one component, so the answer is equal to the longest path in the final graph.
 » 2 weeks ago, # |   0 why 2 segments are sufficient for problem E
•  » » 2 weeks ago, # ^ |   0 hope this helps
•  » » 2 weeks ago, # ^ |   0 Because the string after being divided into k parts has only maximum of 1 outlier. If you get a outlier in the 1st segment (hshahaha) then the 2nd segment musn't be an outlier, so it is enough.
 » 2 weeks ago, # |   0 Is G NP-complete? G can be reduced into a longest path problem, but there are additional constraints.
 » 2 weeks ago, # | ← Rev. 2 →   0 Problem D: My SolutionGiven: A number num(let)We have to Check: Whether num is product of decimal numbers which contain 0's and 1's (binary) as their digits.Explanation: ---- Below i have used binary word. It is denoting the decimal number having digit as 0 and 1. --if num = (binary1)^p1 * (binary2)^p2 * ......(binaryk)^p then answer is yes. other wise no.---- Can we generate all decimal number having binary digits? --Yes, we can because 1<=n<=10^5. --As 10^5 has 6 digits, (_ _ _ _ _ _) => (2*2*2*2*2*2)=> 2^6 => 64 (All possible different decimal numbers having binary as digit.) --So all possible binary decimals will be binary of numbers from 1 to 63 (000001 to 111111).----- Iterate over these decimal(containing binary as digits) numbers and reduce n by the power of this number contained in n.----- if atlast n=1 then answer is yes otherwise no.
 » 2 weeks ago, # |   0 Can Anyone explain the concept of 5th Question
 » 2 weeks ago, # |   0 A brute solution for D code... Your code here... #include using namespace std; #define ll long long #define fast \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); int main(){ fast; ll t; cin>>t; while(t--){ int n; cin>>n; int n1=n; vector v; while(n){ v.push_back(n%10); n/=10; } reverse(v.begin(),v.end()); int cnt1=count(v.begin(),v.end(),1); int cnt0=count(v.begin(),v.end(),0); if((cnt1+cnt0)==(int)v.size()) cout<<"YES\n"; else{ vector v1={11,10,111,101,1011,1001,1101,10001,10011,10101,10111,11111}; while(n1>1){ bool ok=false; for(auto i:v1){ if(n1%i==0){ ok=true; n1/=i; } } if(!ok) break; } if(n1==1) cout<<"YES\n"; else cout<<"NO\n"; } } } 
 » 2 weeks ago, # |   0 in Ques. E, why do we need to iterate in reverse also?
•  » » 2 weeks ago, # ^ |   0 "**acabab**"look at the above testcase: Possible length of subarray is 1,2,3 or 6.If we only consider the subarray starting from beginning, then the answer would have been 6.But considering from last, we can achieve an optimal answer of 2, where we concatenate ab 3 times to get ababab which satisfies the given condition.This condition wouldn't have satisfied if we had considered it from the beginning where we would have got acacac which differs from the given string in 2 places and won't be considered for solution. Hope that u have gotten my point.
•  » » » 2 weeks ago, # ^ |   0 thanks, got it. so it doesn't work if we increase the mistake count to 2 or above. how do we solve the general case?
•  » » 2 weeks ago, # ^ |   0 It doesn't have to be reverse it can be the string starting from d with length d(d is a divisor of n). The key point it's another string starting from an index divisible by d and with length d. We did this because we assumed that there is a mistake in the first string of length d
 » 2 weeks ago, # | ← Rev. 2 →   0 Sometimes, i feel that i don't think correct to solve the problems like D.Product of Binary Decimals, i didn't think correct and i don't know DP to think about the solution to this problem. How can i fix this problem?
•  » » 2 weeks ago, # ^ |   0 I think in term's of solution what are the different solutions can different solution have same pattern solution. Are there are finite solutions in terms of 'N' -> can this solution be pre-computerd
•  » » 2 weeks ago, # ^ |   0 I managed to solve D without DP or precomputation. Although I was unsure about getting hacked.
•  » » » 2 weeks ago, # ^ |   0 can you tell me the proof of your solution and tell me why it works ? You basically checked for any factor i of n , i and n/i should both be binary ?
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 I can't proof but can feel the intuition. The constraint is not so big. Had the constraint be 1e6 and my solution would definitely fail. Number of terms multiplied together to get N will not be very big. 11^3 * 10^2 >= N [ two factors is enough to check ]11^2 * 11^2 * 10^1 >= N [ Three factors but you can first divide by 10 to get rid of 1 term, therefore left with two terms to check ]11 * 101 * (11 or 10 at max) [ So it's easy to check. first divide by 10 then divide by 11, check if that's binary. If not look for it's two factors ]I hope you get the idea.
•  » » » 2 weeks ago, # ^ |   0 My issue is not to solve with DP or any topic, but i want to learn how to think right to solve problems like this problem
•  » » » » 2 weeks ago, # ^ |   0 Practice more. Solving math and recursive problems might help.
•  » » » » » 2 weeks ago, # ^ |   0 Thank you for help
•  » » 2 weeks ago, # ^ |   0 During the contest i didn't get D from the first try and that's ok . I actually wrote three different codes for D until it worked . And in problem E I rushed to finish it in the last 30 minutes leaving a few minutes for F. I think the biggest take way from what i said is that you should not give up until the contest is over .I also think you should approach problems from different angles and solve more problems.
•  » » » 2 weeks ago, # ^ |   0 Thank you for help
 » 2 weeks ago, # |   0 Where s the tutorial for G?
 » 2 weeks ago, # |   0 why are ratings not updated yet?
•  » » 2 weeks ago, # ^ |   0 They are
 » 2 weeks ago, # |   0 Is it possible to solve G using bitmask dynamic programming?
•  » » 2 weeks ago, # ^ |   0 Yes, you don't even need to think about it as a graph.
•  » » » 2 weeks ago, # ^ |   0 My state will be dp(pos,last,mask) from every state I'll increment pos by taking or not taking that element. last will determine what my last taken position was. mask will keep track what positions are already taken. Do you think it can be solved like this?
•  » » » » 2 weeks ago, # ^ |   0 Too slow, you don't need to care about the position, mask and last placed is enough.
•  » » » » » 2 weeks ago, # ^ |   0 But without pos, how I'll reach base case which is pos == n? Can you please explain a little bit?
•  » » » » » » 2 weeks ago, # ^ |   0 base case is when the mask is all ones, that means you processed all songs
•  » » » » » » » 2 weeks ago, # ^ |   0 But how will I count the number of songs that I deleted?
•  » » » » » » » » 2 weeks ago, # ^ |   0 That will be the value of the dp.
 » 2 weeks ago, # | ← Rev. 2 →   0 1950G — Shuffling Songs Tutorial unavailable. Someone please explain the solution in the meantime.253971845 -> This is my solution which got TLE in test case 39.
 » 2 weeks ago, # |   0 Thank you very much for this round! Maybe I could have solved more problems (at least one more), but I finally became a pupil! This is great!
 » 2 weeks ago, # |   0 i just want to know that for e question,i submitted my code in c++17 and it got wrong answer on test2,then after contest i checked that test and it was giving right answer on my visualstudiocode compiler and then i submitted that same code in c++20 and it got accepted,now i want to know why is it so and am i responsible for this mistake of choosing compiler or is it a error from codeforces's side,also i dont think i used anything in my code which would not have worked in c++17 according to me.someone please help
•  » » 2 weeks ago, # ^ |   0 pow is a dangerous function in C++ since its precision is really bad, combining with the rounding-down nature of integer casting it might corrupt the prime check procedure. Probably 64-bit processing in CF's C++20 made it a bit more precise so you passed, but C++17 32-bit didn't.A safer / more stable way for square root alone should be sqrt. You can also try checking for i * i <= n, but careful for overflow (normally if the step is just i++ I'm still confident that such overflow won't happen).
 » 2 weeks ago, # |   0 Can anyone help me? I use dsu(Disjoint set union) to solve problem G, but I don’t know why it always goes Wrong answer on test 5. I spent a long time thinking about it, but I had no idea why.Here is my code:253955348
•  » » 2 weeks ago, # ^ |   0 DSU is a wrong approach. A test like this would fail you: 1 7 a x a y b y b z c z d y d t Correct answer should be 1.
•  » » » 2 weeks ago, # ^ |   0 Thank you very much, you are absolutely right. I don't fully understand the question, that's stupid.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 It's okay, everyone makes mistakes. Keep yourself up and do better next time.Glad that I could help.
•  » » » » » 2 weeks ago, # ^ |   0 so sorry to ask but can you please check my submission for G. thank you. something is wrong
•  » » » » » » 13 days ago, # ^ |   0 Since it's a Hamiltonian walk, you should know where that walk is currently stopping at — instead of trying to link an edge to any vertex in the subset — your DP is lacking an attribute for the last vertex of your path.Bonus: comparing raw strings will TLE eventually (around test 33). Try to optimize that later.
•  » » » » » » » 13 days ago, # ^ |   0 I am sorry so what should i do :(
•  » » » » » » » 13 days ago, # ^ |   0 Hamiltonian walk and cycle are different??
•  » » » » » » » 13 days ago, # ^ | ← Rev. 2 →   0 hey!!! it got accepted apparently i just changed the position of for loops and it gave me AC :), thank you!
•  » » » » » 2 weeks ago, # ^ |   0 i was following 4. Check for existence of Hamiltonian walk from this blog:https://codeforces.com/blog/entry/337
 » 2 weeks ago, # | ← Rev. 3 →   0 in problem D when i am using this: for(ll i=2e5;i>=10;i--){ if(isBD(i)){ vd.pb(i); } }to pre calculating binary numbers then it works correct for all test cases,but when i am doing for(ll i=10;i<=2e5;i++) it is producing wrong output on the last test case (1001) ,can anyone explains why the first one is fetching correct answer?this is my approach 254040093
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 I had the same implementation and it was outputting wrong answer on 1001 . so i just added if n in BD : print"YES" the reason is that 1001 is divisible by 1, 7, 11, 13, 77, 91, 143, 1001 notice how if you divide by 11 you won't be able to prove it's fine because you'll be left with 91 .another trick is to sort the array of binary decimals in non-ascending order and for(ll i=2e5;i>=10;i--) does that in your code.But i still don't get why this answer works . I hope someone can explain it .
 » 2 weeks ago, # |   0 For question g, is it wrong to use the length of the longest path in the graph?
•  » » 2 weeks ago, # ^ |   0 No, it's right
 » 2 weeks ago, # |   0 sorry for the confusion with clz. Interesting, learnt something new, ty
»
2 weeks ago, # |
0

# include<bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while (t--) { int a,b,c; cin>>a>>b>>c; bool case1=(a<b&&b<c); bool case2=(a<b&&b>c);

if (!case1&&!case2)
{
cout<<"NONE"<<endl;
}
if (case1)
{
cout<<"STAIR"<<endl;
}
if (case2)
{
cout<<"PEAK"<<endl;
}
}
return 0;

}

I think this code for A without else looks better

 » 2 weeks ago, # |   0 Here is an elaganto solution with T(N) = O(log(N)), S(N) = O(1) for 1950F — 0, 1, 2, Tree! void solve() { int a, b, c; cin>>a>>b>>c; int height = -1; if(a > 0){ // a will have a + 1 slots or children int slots = a + 1; if(slots == c){ // Calculating a's height int as_height = 0; for(int a_copy = a; a_copy; a_copy>>=1, as_height++); if(b == 0){ height = as_height; } // If putting a's results in a complete tree else if((slots & (slots - 1)) == 0){ int bs_height = ceil((double)b/slots) - 1; height = as_height + bs_height + 1; }else{ // If putting a's is not producing a complete tree // Then how many slots are there above the base as_children /* a / \ a _ <==== This is left slots /\ Here, 1 is the number of empty slot */ int left_slots = (1<<(int)(log2(slots) + 1)) - slots; if(b > left_slots){ int b_left = b - left_slots; int bs_height = ceil((double)b_left/slots) - 1; height = as_height + bs_height + 1; }else if(b <= left_slots){ height = as_height; } } } }else{ if(c == 1){ height = b; } } // print(a, b, c, height); cout<
 » 2 weeks ago, # | ← Rev. 3 →   0 Why my solution works? Submission I submitted this solution in hurry and it got AC. I removed every divisor of n which is also a binary_decimal number from n, and in the end if the n is reduced to 1, then print "YES" else "NO".I did it in greatest -> smallest binary_decimal number order which passed the soln. smalletst -> greatest binary_decimal number order can't work. Failing TC : 1001.Where 11*91 = 1001Basically, it was just a fluke, which went good.I want to know How can i verify correctness of such wierd claims in a live contest?
 » 2 weeks ago, # |   0 Someone please help with problem G(im new to dp): 254308462
 » 2 weeks ago, # |   0 Waiting for editorial of G.....
 » 2 weeks ago, # |   0 Let's say we have a point (x,y) on a coordinate system. What are the possible rotations of the point?
 » 2 weeks ago, # | ← Rev. 2 →   0 I have a beautiful recursive approach for Question D https://codeforces.com/contest/1950/submission/253808823Let F(n)=b1*b2*b3*..*bk , where b1,b2,..bk are binary decimal numbers . Then F(n)=b1*F(n/b1)Thus if we find a binary decimal factor of n then if F(n/b1) is a product of binary decimal numbers then n also is .
 » 2 weeks ago, # |   0 It's been 4 days, still no tutorial for G?
•  » » 2 weeks ago, # ^ |   0 Consider a graph there $i$-th vertex has two values $(g_i, w_i)$. We can move from $i$ to $j$ only if $g_i = g_j$ or $w_i = w_j$. Now a simple path in that graph is some permutation we want to get (if vertex is not in our path, we will delete it). We want to delete as many as possible, so we have to find maximum simple path in that graph.
•  » » » 2 weeks ago, # ^ |   0 i have done using graph only , could you tell what is wrong with it? https://codeforces.com/contest/1950/submission/254107386 , i have found the longest path in the graph and substracted it from the total number of edges
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 got it
 » 2 weeks ago, # |   0 https://codeforces.com/contest/1950/submission/254107386 could anyone help me with this (G question) , my logic is that i have made a graph with vertices having edge on having same genre or same writer or both , and then find the longest path in the graph , but it is giving wrong answer in testcase 3 at 163rd token :/
 » 2 weeks ago, # | ← Rev. 2 →   0 Can anyone help me for Question E, here is my solution Python code. It is giving TLE but I think the time complexity is O(128*N). Also the same code of C++ version is getting accepted code.
 » 10 days ago, # |   0 what is the difference between (a
 » 5 days ago, # |   0 Is it possible to solve 1950G - Shuffling Songs without DP? SlavicG flamestorm mesanu