Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### flamestorm's blog

By flamestorm, 4 months 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

 » 4 months ago, # | ← Rev. 3 →   +6 thanks for the fast editorialalthough they are all empty :(
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 They are updated now with solutions
•  » » » 4 months ago, # ^ |   +3 still waiting for G.
•  » » » » 4 months ago, # ^ |   0 search hamiltonian paths
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 would recommend this blog for problem G: https://mirror.codeforces.com/blog/entry/337
•  » » » 2 months ago, # ^ |   0 in problem E why we are checking strings of length l from either prefix or suffix why it cannot be any substring with length l from middle or anywhere else in the string ?? can someone please answer this
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 notice this, there can be atmost 1 difference since we can just check both prefix and suffix, we already have two choices, if first doesnt work then check second, if both doesnt work then a high lenght of the string is required
 » 4 months 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).
•  » » 4 months ago, # ^ |   0 It's O(2^n*n^2) because for each bit mask you iterate every possibile pair of songs.
•  » » » 4 months ago, # ^ |   0 thank u
 » 4 months ago, # |   0 Problems were very challenging .. liked them even though not solved them but they were good .. + lightning fast editorial
 » 4 months ago, # |   +2 F can be solved in O(1), so why a + b + c <= 3*10^5??
•  » » 4 months ago, # ^ |   0 Do you mean O(log(a)) cause I can't figure out an O(1)
•  » » » 4 months 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
•  » » » » 4 months 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
•  » » » » 4 months 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))
•  » » » » » 4 months 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.
•  » » » » » » 4 months ago, # ^ |   +20 sorry for the confusion with clz. Interesting, learnt something new, ty
•  » » » » 4 months ago, # ^ |   0 can you please explain what's the logic behind Padding variable ?
•  » » » » » 4 months 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).
•  » » » » » » 4 months 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 ??
•  » » » » » » » 4 months ago, # ^ |   0 It's a common way to round the division result up.
•  » » » » » » » » 4 months ago, # ^ |   0 ok, thank u
•  » » 4 months 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.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 solution you can check this solution for O(1)
•  » » » » 4 months ago, # ^ |   0 bro u used power function is not o(1)
•  » » » » 4 months ago, # ^ |   0 int ha=log2(a); is logarithmic
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 can someone please explain why my code fails in task F https://mirror.codeforces.com/contest/1950/submission/262901913
•  » » 4 months ago, # ^ |   +7 'cause it is div4 :)
•  » » 3 months ago, # ^ |   0 For this constraint, queue solution is also accepted. Queue Solution (AC)
 » 4 months ago, # |   0 thanks you for the quick editorial and good round!
 » 4 months ago, # |   -17 Hello I am gokula kannan siva ji
•  » » 4 months ago, # ^ |   -10 why am i geting downvoted i am gokula kannan siva ji < : (
•  » » » 4 months ago, # ^ |   0 don't be sad bro, I upvoted
•  » » » » 4 months ago, # ^ |   +3 thank you bro i appreciate it :( they are just mad for no reason
 » 4 months 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??
•  » » 4 months 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?
•  » » » 4 months ago, # ^ |   +4 so how to approach this? i read about hamiltonian path! but i didnt get it! please explain
•  » » » » 4 months 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.
•  » » » 4 months 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
•  » » » » 4 months 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.
•  » » » 4 months 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.
•  » » » » 4 months 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.
 » 4 months ago, # |   0 what would be the rating for problem E? just wondering
•  » » 4 months ago, # ^ |   0 around 1300
•  » » 4 months ago, # ^ |   0 realistically 1200-1300, Clist says its 1500:https://clist.by/problems/
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Maybe 1200-1300
•  » » 4 months ago, # ^ |   0 maybe around 1200-1300, maximum ~1500
 » 4 months ago, # |   0 thanks for the solutions!
 » 4 months 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.
 » 4 months ago, # |   0 why is my submission for E wrong tho i tested them all? ;-; here's my submission: 253815920
•  » » 4 months ago, # ^ |   0 try case 1 2 aa
 » 4 months 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.
 » 4 months ago, # |   0 can someone explain solution to problem E
•  » » 4 months ago, # ^ |   0 brute force check for every factor of n
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   0 thanks got it now
•  » » » 4 months ago, # ^ | ← Rev. 2 →   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
•  » » » » 4 months ago, # ^ |   +1 u can take whatever 2 substrings you want but they should not be overlapping
•  » » » » » 4 months 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
•  » » » » » » 4 months ago, # ^ |   0 i supposed that the lenght of substring is a divisor of n
•  » » 4 months ago, # ^ |   0 One straightforward optimization can be that once i crosses n/2, you can be sure that the answer is n.
 » 4 months 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.
•  » » 4 months 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.
 » 4 months 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.
•  » » 4 months ago, # ^ |   0
 » 4 months 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
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 Consider $12321 = 3^2\cdot 37^2$.
•  » » » 4 months ago, # ^ |   0 Yeah, it quickly becomes slow if n is bigger than 10^5
•  » » 4 months 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.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 but this method is giving error on test 2 https://mirror.codeforces.com/contest/1950/submission/253788629 here is my solution
•  » » » » 4 months 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://mirror.codeforces.com/contest/1950/submission/253817219
•  » » » » » 4 months ago, # ^ |   0 Got it. Thank You
 » 4 months ago, # |   0 Can someone please try and hack my E solution. Submission Link
 » 4 months 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(); } } 
 » 4 months ago, # |   0
 » 4 months ago, # |   0 How can this solution for D have tle,its constant time
•  » » 4 months ago, # ^ |   +22 💀
•  » » 4 months ago, # ^ |   0 And she's buying a stairway to Heaven ....
 » 4 months 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
 » 4 months ago, # |   0 can someone explain me this approach for problem d ? 253830700
•  » » 4 months 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
 » 4 months 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?
•  » » 4 months 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
•  » » » 4 months ago, # ^ |   0 Thankss!
 » 4 months 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.
•  » » 4 months ago, # ^ |   0 Indeed, here is a solution. https://mirror.codeforces.com/contest/1950/submission/253859143
 » 4 months ago, # |   0 253824980WHY IS THIS WRONG QUES 4
•  » » 4 months ago, # ^ |   0
•  » » » 4 months 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$).
•  » » » » 4 months ago, # ^ |   0 ok thanku so much,will u share your soln plz
•  » » » » » 4 months ago, # ^ |   0
 » 4 months ago, # |   0 thanks for very fast editorial.
 » 4 months ago, # |   0 Why didnt Dp worked for the solution D. Its shows TLE. Here is my solution : https://mirror.codeforces.com/contest/1950/submission/253751070. PLEASE HELP
•  » » 4 months ago, # ^ |   0 there are no constraints on n over all test cases.
 » 4 months 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
 » 4 months ago, # | ← Rev. 2 →   +1 253841056My solution in O(1) using maths...
 » 4 months 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.
 » 4 months ago, # |   +5 2nd question was very bad question.I hate such type of questions
•  » » 4 months ago, # ^ |   0 boo hoo. grow up.
•  » » » 4 months ago, # ^ |   0 "Grow up"? You unironically have Andrew Tate as your profile picture.
•  » » » » 4 months ago, # ^ |   0 so?
 » 4 months ago, # |   0 How can we solve G using DSU, basically find size of largest component ?
•  » » 4 months ago, # ^ |   0 finding biggest component wont work! look at this
 » 4 months ago, # | ← Rev. 2 →   0 Can anyone share the solution for D by DP?
•  » » 4 months ago, # ^ |   0
 » 4 months 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).
 » 4 months ago, # | ← Rev. 2 →   0 Another weak pretests day? What is it with codeforces and weak pretests.... (problem E)
 » 4 months 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://mirror.codeforces.com/contest/1950/submission/253828002
 » 4 months ago, # | ← Rev. 2 →   0 nvm, my assumption was wrong
 » 4 months ago, # | ← Rev. 2 →   0 .
 » 4 months 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!
 » 4 months ago, # |   0 Hi, all why my solution G will WA 5? https://mirror.codeforces.com/contest/1950/submission/253786544 it also uses bitmask, and I think the order doesn't matter. Thanks for your help!
•  » » 4 months 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
 » 4 months 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
•  » » 4 months ago, # ^ |   0 Here is a simpler solution for D : https://mirror.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.
 » 4 months 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
 » 4 months ago, # |   0 Here is a simpler solution for D : https://mirror.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.
 » 4 months ago, # |   0 Problem G was great
 » 4 months ago, # |   0 tourist getting WA1 on A is really funny to me for some reason
 » 4 months 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......
 » 4 months 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.
•  » » 4 months ago, # ^ |   0 It would be updated once the open hacking phase ends.
•  » » » 4 months ago, # ^ |   0 Thank you for the clarification!
•  » » 4 months 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
 » 4 months ago, # | ← Rev. 2 →   0 (found)
 » 4 months 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)
•  » » 4 months ago, # ^ | ← Rev. 2 →   +1 No, being connected doesn't mean that you can make a simple path that visits all nodes.
•  » » » 4 months 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.
•  » » » » 4 months ago, # ^ |   0 This is the simplest counterexample I can think of: which can be created with this input: https://ideone.com/Lvl1xi
•  » » » » » 4 months ago, # ^ |   0 thank you very much.:)
•  » » » » » 4 months ago, # ^ |   0 how did you solve this question?
•  » » » » » » 4 months 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.
•  » » » » » 4 weeks ago, # ^ |   0 really nice explination. I worked this problem for a long time, but got wrong for the same reason
•  » » 4 months 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
•  » » » 4 months ago, # ^ |   0 ohk got it. thanks.
 » 4 months ago, # |   0 Can anybody help me in figuring out where my solution is wrong for "1950D — Product of Binary Decimals"https://mirror.codeforces.com/contest/1950/submission/253812424it would be great help!! thanks
•  » » 4 months 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.
 » 4 months ago, # |   +1 name of problem D was a hint about its tag. Spoiler
•  » » 4 months ago, # ^ |   0 ?
•  » » » 4 months ago, # ^ |   0 it was a troll. (DP : dynamic programming) tag of problem D.
 » 4 months ago, # |   0 Just 1 char from AC :sob:
 » 4 months 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
•  » » 4 months ago, # ^ |   0 How do you find the optimal way to reorder the elements?
 » 4 months ago, # |   0 when i don't add the condition (c ==a+1), can anyone tell me the testcase where this code fails?
 » 4 months ago, # |   0 Can anybody explain how this code gets AC? https://mirror.codeforces.com/contest/1950/submission/253676853
•  » » 4 months 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...
•  » » » 4 months ago, # ^ |   0 I mean, why is it correct? Is it possible to prove that this solution is correct?
•  » » » » 4 months 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) 
•  » » » » 4 months 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; } 
•  » » » » 4 months 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)
•  » » » 4 months ago, # ^ |   0 you only need 10, 11, 100, 101, 110, 111 — all the factors below the sqrt(10^5)
•  » » 4 months 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
•  » » » 4 months 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
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 WOW thanks! I suppose there was a reason I couldn't prove that solution for 2 hours.
 » 4 months ago, # |   0 Waiting for the tutorial of G...
 » 4 months 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
•  » » 4 months 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.
•  » » » 4 months 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://mirror.codeforces.com/contest/1950/submission/253975967
•  » » » » 4 months 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.
•  » » » » » 4 months ago, # ^ |   0 thanks a lot
•  » » » 4 months ago, # ^ |   0 thanku bro
 » 4 months 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 months ago, # ^ |   0 I am getting same error on test case 3 for 150th case my solutionbut when I use max function it works?
 » 4 months 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) 
 » 4 months ago, # | ← Rev. 2 →   0 O(logn) solution for problem f
 » 4 months ago, # |   0 Can anyone help me with this solution, how is this different from the one in tutorial?
•  » » 4 months ago, # ^ |   0 why did you assume it's a monotonic function you have too check for all factors and choose the min one
•  » » » 4 months ago, # ^ |   0 Thanks for the catch :)
 » 4 months ago, # | ← Rev. 3 →   0 can't g be solved by optimizing the code for finding the longest path in a graph problem
•  » » 4 months ago, # ^ |   0 The length that can be filled does not satisfy monotonic conditions, so binary search cannot be used
•  » » » 4 months 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
•  » » » » 4 months 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
 » 4 months 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
•  » » 4 months ago, # ^ |   0 What's wrong with you bro? Are you expressing your gratitude or making fun of him?
•  » » 4 months ago, # ^ |   0 What's going on here, please don't fill comment section like that.
 » 4 months 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 :(
 » 4 months 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?
•  » » 4 months ago, # ^ |   0 Be patient, system testing is currently in progress. Your three others are in the line for rejudging.
•  » » » 4 months ago, # ^ |   0 thank you for your reply
•  » » » 4 months ago, # ^ |   0 what do you mean by rejudging? sorry i am new here
•  » » » » 4 months 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.
 » 4 months 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.
•  » » 4 months ago, # ^ |   0 same question, got TLE by taking all possible substrings
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   0 Wow, nice explanation thanks for your help. I really appreciate it. Codeforces community is really good.
•  » » 4 months 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.
 » 4 months 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))}$)).
 » 4 months ago, # |   0 Sorry, can anyone tell me where the problem is with this code? https://mirror.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.
 » 4 months ago, # |   0 why 2 segments are sufficient for problem E
•  » » 4 months ago, # ^ |   0 hope this helps
•  » » 4 months 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.
 » 4 months ago, # |   0 Is G NP-complete? G can be reduced into a longest path problem, but there are additional constraints.
 » 4 months 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.
 » 4 months ago, # |   0 Can Anyone explain the concept of 5th Question
 » 4 months 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"; } } } 
 » 4 months ago, # |   0 in Ques. E, why do we need to iterate in reverse also?
•  » » 4 months 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.
•  » » » 4 months 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?
•  » » 4 months 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
 » 4 months 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?
•  » » 4 months 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
•  » » 4 months ago, # ^ |   0 I managed to solve D without DP or precomputation. Although I was unsure about getting hacked.
•  » » » 4 months 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 ?
•  » » » » 4 months 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.
•  » » » 4 months 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
•  » » » » 4 months ago, # ^ |   0 Practice more. Solving math and recursive problems might help.
•  » » » » » 4 months ago, # ^ |   0 Thank you for help
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   0 Thank you for help
 » 4 months ago, # |   0 Where s the tutorial for G?
 » 4 months ago, # |   0 why are ratings not updated yet?
•  » » 4 months ago, # ^ |   0 They are
 » 4 months ago, # |   0 Is it possible to solve G using bitmask dynamic programming?
•  » » 4 months ago, # ^ |   0 Yes, you don't even need to think about it as a graph.
•  » » » 4 months 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?
•  » » » » 4 months ago, # ^ |   0 Too slow, you don't need to care about the position, mask and last placed is enough.
•  » » » » » 4 months ago, # ^ |   0 But without pos, how I'll reach base case which is pos == n? Can you please explain a little bit?
•  » » » » » » 4 months ago, # ^ |   0 base case is when the mask is all ones, that means you processed all songs
•  » » » » » » » 4 months ago, # ^ |   0 But how will I count the number of songs that I deleted?
•  » » » » » » » » 4 months ago, # ^ |   0 That will be the value of the dp.
 » 4 months 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.
 » 4 months 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!
 » 4 months 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
•  » » 4 months 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).
 » 4 months 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
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   0 Thank you very much, you are absolutely right. I don't fully understand the question, that's stupid.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 It's okay, everyone makes mistakes. Keep yourself up and do better next time.Glad that I could help.
•  » » » » » 4 months ago, # ^ |   0 so sorry to ask but can you please check my submission for G. thank you. something is wrong
•  » » » » » » 4 months 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.
•  » » » » » » » 4 months ago, # ^ |   0 I am sorry so what should i do :(
•  » » » » » » » 4 months ago, # ^ |   0 Hamiltonian walk and cycle are different??
•  » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 hey!!! it got accepted apparently i just changed the position of for loops and it gave me AC :), thank you!
•  » » » » » 4 months ago, # ^ |   0 i was following 4. Check for existence of Hamiltonian walk from this blog:https://mirror.codeforces.com/blog/entry/337
 » 4 months 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
•  » » 4 months 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 .
 » 4 months ago, # |   0 For question g, is it wrong to use the length of the longest path in the graph?
•  » » 4 months ago, # ^ |   0 No, it's right
 » 4 months ago, # |   0 sorry for the confusion with clz. Interesting, learnt something new, ty
»
4 months 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

 » 4 months 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<
 » 4 months 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?
 » 4 months ago, # |   0 Someone please help with problem G(im new to dp): 254308462
 » 4 months ago, # |   0 Waiting for editorial of G.....
 » 4 months ago, # |   0 Let's say we have a point (x,y) on a coordinate system. What are the possible rotations of the point?
 » 4 months ago, # | ← Rev. 2 →   0 I have a beautiful recursive approach for Question D https://mirror.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 .
 » 4 months ago, # |   0 It's been 4 days, still no tutorial for G?
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   0 i have done using graph only , could you tell what is wrong with it? https://mirror.codeforces.com/contest/1950/submission/254107386 , i have found the longest path in the graph and substracted it from the total number of edges
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 got it
 » 4 months ago, # |   0 https://mirror.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 :/
 » 4 months 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.
 » 4 months ago, # |   0 what is the difference between (a
•  » » 3 months ago, # ^ |   0 Try a scenario where a < b and b >= c and see for yourself.
 » 3 months ago, # |   0 Is it possible to solve 1950G - Shuffling Songs without DP? SlavicG flamestorm mesanu
 » 3 months ago, # |   0 Could anybody tell me why my code fails? Idea of the solution is to create a graph where each node is a song and there is an edge between two songs if they have the same genre or writer. Then we can find the size of the largest connected component in the graph and the answer will be n — size of the largest connected component. This is because we can rearrange the songs in the largest connected component in any way we want and the rest of the songs will be removed. public static int dfs(int u, List> graph, bool[] visited) { visited[u] = true; var size = 1; foreach (var v in graph[u]) { if (!visited[v]) { size += dfs(v, graph, visited); } } return size; } public static void Main(string[] args) { var t = int.Parse(ReadLine()); while (t-- > 0) { var n = int.Parse(ReadLine()); var songs = new List<(string, string)>(); for (var i = 0; i < n; i++) { var input = ReadLine().Split(); var g = input[0]; var w = input[1]; songs.Add((g, w)); } var graph = new List>(); for (var i = 0; i < n; i++) { graph.Add(new List()); for (var j = 0; j < n; j++) { if (songs[i].Item1 == songs[j].Item1 || songs[i].Item2 == songs[j].Item2) { graph[i].Add(j); } } } var visited = new bool[n]; var mx = 0; for (var i = 0; i < n; i++) { if (!visited[i]) { var size = dfs(i, graph, visited); mx = Math.Max(mx, size); } } Console.WriteLine(n - mx); } } 
•  » » 3 months ago, # ^ |   0 I am glad to give you an example which your solution will be failed. 1 5 a e b e c e b f d f If we just consider "connected component" the answer will be 0, however we must get a continuous chain to make sure a correct shuffle. In this example, answer will be 1, as we choose to remove the song  and get a correct shuffle.
 » 2 months ago, # |   0 E was a genius question, Thanks :)
 » 4 weeks ago, # |   0 I did, 1950E using string hashing, (i learned that concept few days ago, so i tried it over here), And it worked...... :)