### MrPaul_TUser's blog

By MrPaul_TUser, history, 7 weeks ago,

1593A - Elections

Idea: MikeMirzayanov

Tutorial
Solution

1593B - Make it Divisible by 25

Idea: MikeMirzayanov

Tutorial
Solution

1593C - Save More Mice

Idea: ITMO student team

Tutorial
Solution

1593D1 - All are Same

Idea: MikeMirzayanov

Tutorial
Solution

1593D2 - Half of Same

Idea: MikeMirzayanov

Tutorial
Solution

1593E - Gardener and Tree

Idea: MikeMirzayanov

Tutorial
Solution

1593F - Red-Black Number

Idea: MikeMirzayanov

Tutorial
Solution

1593G - Changing Brackets

Idea: nastya_ka

Tutorial
Solution

• +54

 » 7 weeks ago, # |   0 Thanks
 » 7 weeks ago, # |   0 Can someone explain the solution to F pls
•  » » 7 weeks ago, # ^ |   -60 Yeah, sure, why not? here lol
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   +3 F is a dynamic programming problem. You can use taken amount red digits count the rem of red number mod a the rem of black numer mod b to describe a state.The taken amount is phase of the dp. If you use enumeration method to find all states, the amount of states is $2^{40}$. But if you use dp to descibe all states, the amount of states is only $40^4$.Here is my code, written in Python3, but it get TLE. https://codeforces.cc/contest/1593/submission/132439261Here is the same code rewritten by C++, it get AC. https://codeforces.cc/contest/1593/submission/132442220I think the python code is more clearly than C++ code.
•  » » » 6 weeks ago, # ^ |   0 Cool! Thanks
 » 7 weeks ago, # |   +5 d2 is really intresting.
•  » » 5 weeks ago, # ^ |   0 Can you please explain the solution ?
 » 7 weeks ago, # |   +3 It seems that in the tutorial for A, the answer should be max(0, max(b,c) + 1 — a) (as in the solution code), instead of min(0, max(b,c) + 1 — a).
 » 7 weeks ago, # |   +16 We don't need that extra array to recover answer string. We can store masks in DP and recover the answer from that. Submission with comments : 131983798
•  » » 7 weeks ago, # ^ |   +3 Thanks a lot! Cool explanation.
 » 7 weeks ago, # |   0 Your dp is so messy.(F) -__- Good problemset btw.
 » 7 weeks ago, # |   0
•  » » 7 weeks ago, # ^ |   +3 Thank you very much, I was having a bug for a long time and I had no idea what it could be (눈‸눈)
•  » » » 7 weeks ago, # ^ |   0 Feeling nice to hear that it helped.
 » 7 weeks ago, # | ← Rev. 3 →   0 For the E problem, will the standard graph bfs not work? I pushed all the leaves ( adjacency list size == 1 ) to a queue and assigned them a distance of 1 ( distance = number of times the operation has to be performed to cut off that node ). Then I performed a bfs assigning increasing distance. Answer is simply all the nodes whose distance is greater than k. This is failing though. Please if somebody could help me out. Thanks in advancehttps://codeforces.cc/contest/1593/submission/132264294UPD : I changed the visited logic to an in-degree logic while preserving the bfs (AC : 132341078). Hope somebody finds this helpful. Thank you dedsec_29
•  » » 7 weeks ago, # ^ |   0 Once you mark a node visited, your code will never update its distance. But this is incorrect. You have to mark a node visited only when it becomes a leaf. If you mark it before it becomes a leaf, d[i] will no longer denote iterations after which the node is no longer part of tree
•  » » » 7 weeks ago, # ^ |   0 "If you mark it before it becomes a leaf, d[i] will no longer denote iterations after which the node is no longer part of tree."Can you justify this with a counter-example please? I tried a lot of manual cases (Sample cases passed too), every time the node gets marked as visited, it is correctly assigned the distance from the closest leaf. Say the distance of the node is 3 from the closest leaf and k=3, so that node will be cut off at the end of all k operations, right? Or am I missing something? Thanks again.
•  » » » » 7 weeks ago, # ^ |   0 Take this test case for example:1 8 2 1 2 2 3 3 4 4 5 5 6 6 7 8 3 Your output: 2 Correct output: 3 Your code deletes node 3 as you mark the distance 2 for it, but it will be deleted in the 3rd iteration, so d[3] should be 3, not 2
•  » » » » » 7 weeks ago, # ^ |   +1 Oh.. Yeah I found my mistake. Thank you so much.
•  » » 6 weeks ago, # ^ |   0 Thanks man
•  » » » 13 days ago, # ^ |   0 You're welcome :)
 » 6 weeks ago, # | ← Rev. 2 →   0 Can Someone help with the time complexity of this code: https://codeforces.cc/contest/1593/submission/132395142 for problem D2. I have used dp table for calculating the maximum gcd possible when I consider exactly n/2 numbers( because I have to make atleast half elements equal) dp[i][cnt][last] stores set of GCDs that are possible after considering cnt number of elements upto ith position in the array with index of previous selected element as last. It got submitted with 15ms runtime. According to me, the time complexity of this code is O(n^5 * (log(max(Ai)) + log(n))). I want to know whether I am wrong with the time complexity or test cases are not strong enough ! Reason behind asking this question Before I implemented this idea, I tried to calculate the time complexity of the algorithm, and as you can see from the above code, the three outer for loop will contribute n*n*n(n^3) times to the time complexity and the inner most for loop can iterate n*n times in the worst case( because n*n pairs possible with distinct differences). And with that there comes additional factors due to __gcd() function and inserting elements to the set. Hence total time complexity should be O(n^5 * (log(max(Ai)) + log(n)) ) After calculating the time complexity, I thought this should result in TLE, but still I implemented this to check the correctness of the idea and try to optimize it further if possible. After getting sample test case passed, I submitted it to check how it performs with all test cases. To my surprise it passed all tests within 15ms.
 » 6 weeks ago, # |   0 I'm Stuck at E. I don't know why my code is failing. Can someone please help?? link to the code
•  » » 6 weeks ago, # ^ |   0 Your code is so complex. You should explain your idea.
•  » » » 6 weeks ago, # ^ |   0 I'm applying a multisource BFS from all leaf nodes. Vis[i] stores the number of operations it takes to remove the node i. then at last I count all the nodes which are left after performing k operations.
»
6 weeks ago, # |
Rev. 2   0

can someone pls correct my code(make it divisible by 25)

# include<bits/stdc++.h>

using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc; while(tc--) { string s; cin >> s; int n = s.length()-1; int cnt = 0; int fg = 0; for(int i = n;i >= 0;i--) { while((s[i] != 5 && i >=0) || (s[i] != 0 && i >= 0)) { cnt++; i--; } int y = i; i--; while((s[i] != 0 && i >= 0) || (s[i] != 2 && i >= 0) ||(s[i] != 5 && i >= 0)|| (s[i] != 7 &&i >=0) ) { cnt++; i--; } int x = i; if((s[x]==2&&s[y]==5)||(s[x]==0&&s[y]==0)||(s[x]==5&&s[y]==0)||(s[x]==7&&s[y]==5)) break; } cout<<cnt<<endl;

} return 0; }

•  » » 6 weeks ago, # ^ |   0 Make good use of spoilers and blocks.
•  » » » 6 weeks ago, # ^ |   0 haha
•  » » 6 weeks ago, # ^ |   0 Nice
 » 5 weeks ago, # |   0 MrPaul_TUser I'm trying to view this editorial on edge (on laptop) and chrome (on phone), but on both platforms, the editorials aren't available Спойлер
 » 5 weeks ago, # |   0 Did anyone solve F using meet in the middle idea ?
•  » » 5 weeks ago, # ^ |   0 I'm trying to do it here but I need a way to combine the answer faster, I'm doing it in O(2^(n/2)*a*b) but it didn't pass.
 » 5 weeks ago, # |   0 I think problem A has tricks, but not. It's so easy!
 » 5 weeks ago, # |   0 Can someone explain why my code is slower and getting TLE than the solution on problem E? Link to my code https://codeforces.cc/contest/1593/submission/133856542. The idea is the same, except I'm using a map and set for the adjacency list. If the lists size is 1, I add it to the queue and later remove it.
 » 4 weeks ago, # |   0 My idea for E was to look at one diameter of the tree and take a middle point in that diameter. After that i root the tree in this middle point and after that it's easy but unfortunately i got memory limit exceeded. Is this idea works?
 » 3 weeks ago, # |   0 B problem solutioin good!
 » 11 days ago, # |   0 CAN F QUESTION DE DONE USING MEET INT THE MIDDLE?