By Vladosiya, history, 6 months ago,

1927A - Make it White

Idea: MikeMirzayanov

Tutorial
Solution

1927B - Following the String

Idea: MikeMirzayanov

Tutorial
Solution

1927C - Choose the Different Ones!

Idea: MikeMirzayanov

Tutorial
Solution

1927D - Find the Different Ones!

Idea: MikeMirzayanov

Tutorial
Solution

1927E - Klever Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1927F - Microcycle

Idea: MikeMirzayanov

Tutorial
Solution

1927G - Paint Charges

Idea: MikeMirzayanov

Tutorial
Solution
• +160

 » 6 months ago, # |   +4 Nice contest. Thnx, Mike!
•  » » 6 months ago, # ^ |   -32 No,I do not think so
•  » » » 6 months ago, # ^ |   0 Can't solve it nicely doesn't mean the contest is not nice.
•  » » » 6 months ago, # ^ |   0 skill issue
 » 6 months ago, # |   0 Good round!
 » 6 months ago, # | ← Rev. 2 →   +10 The system testing is going on for last >4 hrs. Is there a way I can submit problems while system testing goes on for contests?
 » 6 months ago, # |   +2 loved this round. the problems were so unique but system testing is not ending :'(
•  » » 6 months ago, # ^ |   0 Exactly.
•  » » 6 months ago, # ^ |   0 when will our rating will be updated? This is my First contest participation
•  » » » 6 months ago, # ^ |   0 Idk either:( we should wait
•  » » » » 6 months ago, # ^ |   0 oh ok ;( thanks for the reply mate
 » 6 months ago, # |   +10 Good round. I done abcde. We will be waiting for new and interesting rounds from MikeMirzayanov. Thanks for fast editorial.
 » 6 months ago, # |   0 Problems were really nice. Thanks!
 » 6 months ago, # |   0 Please someone tell me, why did I get TLE on problem B with this approach??int main() { // Code int t; cin >> t; int total = 0; while(t--) { int n; cin >> n; vector arr; int temp; for(int i = 0; i < n; i++) { cin >> temp; arr.push_back(temp); } int freq[26] = {0}; string result = ""; // trace traversal for(int i = 0; i < n; i++) { // letter frequency traversal for(int j = 0; j < 26; j++) { if(arr[i] == freq[j]) { freq[j]++; // add the frequecy result = result + char(97 + j); break; } } } cout << result << endl; } return 0;}
•  » » 6 months ago, # ^ |   +18 i think problem in this:result = result + char(97 + j); you can use this instead: result += char(97 + j);
•  » » » 6 months ago, # ^ |   +3 ok :)
•  » » 6 months ago, # ^ |   0 result = result + char(97 + j);This is a O(n^2) operation.use this insteadresult.push_back(char(97+j));
•  » » » 6 months ago, # ^ |   +3 ok thanks :)
•  » » » 6 months ago, # ^ |   0 The time complexity of push_back is how much?
•  » » » » 6 months ago, # ^ |   0 $O(1)$ for sure. string = basic_string, and basic_string is just like a extended vector.
•  » » » » 6 months ago, # ^ |   0 but "result = result + char(97 + j)" will have a worse time complexity because it is equivalent to string splicing and it is $O(N)$.
•  » » 6 months ago, # ^ |   +1 You're making things unnecessarily complicated. Take a look at my submission: 245110216
•  » » 6 months ago, # ^ |   0 result = result + char(97 + j); This line gives tle because you are adding result in result this takes o(n^2) time that is why you are getting tle. to avoid this you can create a char array instead of the result string and add single elements to the array. Hope this helps.
•  » » 6 months ago, # ^ |   +1 s is a std::string, then s+='a' is O(1) but s = s+'a' is O(s.size()).ac submission
•  » » 6 months ago, # ^ |   0 The time complexity of str=str+str2 is O(2n) as it process both the string so it TLE's almost everytime on the large testcases .Use either str.push_back(str2) or str+=str2.Here is a relevant link regarding this :https://stackoverflow.com/questions/57132337/difference-between-string-s1-and-string-string-s1
 » 6 months ago, # |   0 fast editorial
 » 6 months ago, # |   0 Can someone tell when rating gets updated.
•  » » 6 months ago, # ^ |   0 got updated
 » 6 months ago, # | ← Rev. 9 →   0 Here is how i explain C:Same as Mike, i have:Cnt0 = the number of x that only appear in ACnt1 = the number of x that only appear in B(1<= x <= k )(Remember, if a number satisfy Cnt1 condition -> both Cnt0 and Cnt1 is increased) Call Cnt0-k/2= ySo imagine that we have an answer array C of size k, then we put all numbers from A to C, and then what we do next is to replace each number in array C that belongs to A by numbers from B (we can choose to put a number in C from A/B if it appears in both arrays) -> Check if y <= Cnt1When the answer if no? when there is x (1 <= x <= k ) that doesnt appear in both 2 arrays or y<0 (cant have enough k/2 numbers in C from A).Sorry if my English is bad.
•  » » 6 months ago, # ^ |   0 I did it like this.I marked the values till k as 1 if they occurred in a, and same in b as well using two arrays mark_a[10^6+1], mark_b[10^6+1]. The iterate till k and do the following. mark the no of missing values in a and b.if both of them have a missing value i.e mark_a[i] == mark_b[i] == 0 then answer is no, else if any of them have more than k / 2 missing values then answer is no.if any of the above conditions aren't true then the answer is yes.Here is my submission id 245227353You can also make mark_a, mark_b of length k+1 rather than 10^6 + 1
•  » » » 6 months ago, # ^ |   0 The last for loop is unnecessary btw you can remove it.The solution will still get accepted.Thanks For reading, sorry if my explanation was bad.
•  » » » 6 months ago, # ^ |   0 it's my first idea, but i set the mark array limit to 2e5... and then i lost 20 mins more to figure out the idea in the tutorial
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 You can also make mark_a, mark_b of length k+1 rather than 10^6 + 1no you cannot create mark_a and mark_b of length k+1, why?let say n=2 and m=2 and k=2 you have array elements as {101,102} and {102, 103} then mark_a[k+1] is mark_a[3] where you only have position 0, 1, 2 and so for mark_b[3], now you don't have position 101 102 103 in your mark_a and mark_b where will you assign mark_a[101]=1 or mark_b[101]=1. why you declare mark_a and mark_b of size 10^6+1 is because that is the range of array elements 1<=a[i]<=10^6, so now for every possible element you have in array you have position where you will mark 1 if found in mark_a or mark_b.//(sorry for bad english)i am saying you can't create mark_a or mark_b of length k+1 as per your code which will possibly generate out of bounds error 245227353but you can create mark_a and mark_b of length k+1, if you check whether if a[i] or b[i] is <=k and then assign 1 as mark_a[a[i]]=1 or mark_b[b[i]]=1 246066103
 » 6 months ago, # |   +29 Another idea for problem F We can get all the bridges in the graph using Tarjan.If the edge is a bridge then it's impossible to make a cycle by this edge.Sort edges by weight and the first edge that is not a bridge surely will make a cycle, then find it by dfs.
•  » » 6 months ago, # ^ |   0 nice one(
•  » » 6 months ago, # ^ |   0 Yess, I also used the same logic
•  » » 6 months ago, # ^ | ← Rev. 3 →   +3 Another idea is to count the number of encountered cycles on the DFS tree and figure out from those counts if an edge sits on some cycle.You can do that by tracking the enter time ins. If ins[child]
•  » » 6 months ago, # ^ |   0 Hey! I am using the exact same approach but getting MLE. Can you please help. code
•  » » 6 months ago, # ^ |   0 Amazing Implementation Skills
 » 6 months ago, # |   0 245202834 why it is wa 2? I'm trying to use two pointers help me please problem C
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 im not sure but I think that when in case of both you can just increase both variable by one and do nothing else and when you finish the loop just check if c1 and c2 both are less than or equal to k/2 and also check if the remaining space in both c1 and c2 is enough for the both variable
•  » » » 6 months ago, # ^ |   0 245205769 this is correct solution, but I uses maps. I want do the same things using two pointers^ but it as WA
 » 6 months ago, # |   +1 Another solution for D: Build 2 segment trees on array: for min and max values on range (vertices store min/max value and index). Then we can answer on query: if max(L, R).value == min(L, R).value then answer is -1 -1, else min(L, R).index max(L, R).index
•  » » 6 months ago, # ^ |   0 can be easily handled by building the tree with each node representing the position of the max/min value, not the value itself
•  » » » 6 months ago, # ^ |   0 This is exactly what I tried to do during the contest (as I've been studying segment trees and I'm in love with them lol)I couldn't figure out the implementation details during the contest, but afterwards, I tried it and got TLE. I'm using Python, so maybe that's it, but I would like some help and feedback on my implementation:TLE Submission
•  » » » » 6 months ago, # ^ |   0 Sorry but i dont know much about python (cant even read the syntax). Here is my C++ code:https://mirror.codeforces.com/contest/1927/submission/245178309
•  » » » » » 6 months ago, # ^ |   0 Thanks! It's pretty much the same thing, with some optimizations (I really like how you avoid having two separate trees :). I'm sure the efficiency of C++ really helps as well.I'll work on mine, and see if I can optimize it further
•  » » » » » » 6 months ago, # ^ |   0 remember that python is about 4-5x slower than C++ (It's not allowed for national OI in my country lol)
•  » » » » » » » 6 months ago, # ^ |   0 Oh wow :_(But that's valid, yes. Even with PyPy and all the possible optimisations, it is still really slow.I've been trying to learn C++ recently, but I'm not comfortable enough yet to use it in a contest. It's one of my goals for this year though
•  » » » » 6 months ago, # ^ |   0 You can use time.time() to check which parts of code takes much time. It can be input parsing or building tree, taking query or outputing.Sometimes python may fail you just because it's slower than c++ (for example, python list acessing is quite slower than c++ native array).
•  » » » 6 months ago, # ^ |   0 You are right, the value actually is not required.
•  » » 6 months ago, # ^ |   +1 I used sparse tables instead, but the idea is the same
•  » » 6 months ago, # ^ |   0 It's an overkill, but I did the same lol :P.
 » 6 months ago, # |   +11 Can anyone share the $n^2$ solution about G? Thanks a lot.
•  » » 6 months ago, # ^ |   +35 My $O(n^2)$ submission: 245368999Let $dp[i][j]$ be the minimum operations to paint all cells from $1$ to $j$ by only using charges before $i$-th cell.Then for each cell $i$, we try to update the cells that can be reached from $i$. Make sure to contain the following case, that is, we use charge $i$ to paint the cells at left side of $i$, and use another charge (at $(i-a_1+1)$ ~ $(i-1)$) to paint the cells at right side of $i$. (See example testcase 8.)This is my first time trying to write a comment, and I'm not good at explaining things ><. See my code for more details.Hope y'all have a nice day :).
•  » » » 6 months ago, # ^ |   0 wow! are you anonymous LGM?
•  » » » 6 months ago, # ^ |   0 by the way, i couldn't understand your code even though i looked at it for an hour. forgive me for my stuipidness. if you don't mind, could you explain this part in more detail? : if (j >= l+1 && j <= i-1){int r2 = min(j+v[j]-1, n);dp[i][r2] = min(dp[i][r2], dp[j-1][max(l-1, 0ll)]+2);} i believe this part is the part you mentioned "Make sure to contain the following case, that is, we use charge i to paint the cells at left side of i ," but i really can't understand it.
 » 6 months ago, # |   0 Great round with unique problems, thanks!
 » 6 months ago, # | ← Rev. 2 →   +5 Problem G$O(N^{2})$ time complexity
•  » » 6 months ago, # ^ |   +6 uhh, can you explain it ?
•  » » » 6 months ago, # ^ | ← Rev. 9 →   +4 dp[i][j] is the rightmost index we can achieve(filling all the prefix..) if we have first i elements of the array and we have used j of them. final answer is minimum j that dp[i][j] >= n in each step we can either pick the i th element and use it to the left either to the right .there is one more case when we pick 2 elements(A and B) .....A.....B.....and use A to the right and B to the left(other cases to use left and right is not optimal.. I can prove)KLEFT[i](you can see the implementation) pair shows the rightmost two k values, if we use the k th element to the left and it covers from i to k segmentThis is my $O(N^{3})$ solution which easily can be optimized to $O(N^{2})$ https://mirror.codeforces.com/contest/1927/submission/245217545
•  » » 6 months ago, # ^ |   0 I think it got WA?
 » 6 months ago, # |   0 D using Segment Tree too.
 » 6 months ago, # |   0 Could you please explain the dry run of the solution of E. Suppose, n=7, k=4 Why, the permutation 1,4,5,7,2,3 6 would not be valid? Why I have to take in this way: 1,8,3,5,2,7,4 ?
•  » » 6 months ago, # ^ |   0 The differents values of sum ok k elements from left to right are 17, 18, 19, 18, so the difference between minimal and maximun is 2 > 1 so It will not work. The apprroach to resolve E and minimize the answer is going to alternate maximum value and minimum, You can have one number i, and inscrease it each time, for odd indexes give number from left, and for even indexes give it from right.
•  » » » 6 months ago, # ^ |   0 1.1+4+5+7=17 2.4+5+7+2=18 3.5+7+2+3=17 4.7+2+3+6=18 So the difference of sum of k value doesn't exceed more than 1.
•  » » » » 6 months ago, # ^ |   0 Sorry I took the case : 1,8,3,5,2,7,4
 » 6 months ago, # | ← Rev. 2 →   0 Another idea of problem G:Because every cell must be colored, I considered greedy.Enumerate each $i$ from $1$ to $n$, suppose that at this moment, all cells from $1$ to $i-1$ are colored.Thinking greedily, it is definitely necessary to color as many cells as possible in $i+1$ to $n$ while coloring the cell $i$, suppose the number as $l$.So preprocess the one with the highest number of stained cells out of all the painting schemes starting with $i$.Then it is easy to dynamically maintain the $l$ for each $i$. I am not sure if this algorithm is correct. It is even $O(N)$.upd: this algorithm is probably wrong. In the last case of the sample, my implementation will use $a_3$ twice.
•  » » 6 months ago, # ^ |   0 the algorithm won't work on many cases
•  » » » 6 months ago, # ^ |   0 Could you give me an example?
•  » » » » 6 months ago, # ^ |   0 1 1 1 1 1 1 | 0 0 0 0 0 0 0 0 0 0 01-> means colored cell , 0 means not coloredaccording to your algorithm in next step this happens1 1 1 1 1 1 | 1 1 1 1 1 1| 0 0 0 0 0then you start considering from first cell of 3rd part and it can happen they only paint themselves and they require total 5 steps to be paintedbut it could happen that among the unconsidered cells in 2nd part one could paint till the nth cell to the right direction
•  » » » » » 6 months ago, # ^ |   0 I realised this, so I didn't skip the cells that were already coloured, instead considering the contribution of these cells to $l$.
•  » » » » » » 6 months ago, # ^ |   0 But $R$ could give you better answer right?
•  » » » » » » » 6 months ago, # ^ |   0 what is "R"? My $l$ is clearly defined in the algorithm description.
•  » » » » » » » » 6 months ago, # ^ |   0 why don't you just implement to check whether it really works?
•  » » » » » 6 months ago, # ^ |   0 it won't improve the time complexity
 » 6 months ago, # |   0 I got TLE ON problem D with binary search any one have an idea why ? https://mirror.codeforces.com/contest/1927/submission/245354533
•  » » 6 months ago, # ^ |   0 u are passing the vector instead of a reference to it to the function look at this:https://mirror.codeforces.com/contest/1927/submission/245372067
•  » » » 6 months ago, # ^ |   0 yes you are right it passed now thanks
 » 6 months ago, # |   0 Thank you for the contest. I finally reached expert.
 » 6 months ago, # |   0 Interesting pset. Thanks!
 » 6 months ago, # |   +1 hey , the contest counted as unrated for me and I have solved a problem ?????
 » 6 months ago, # | ← Rev. 2 →   0 Can someone explain me why the author’s solution for problem B is not of complexity O(N^2)? I would assume doing s += chr(97 + j) to be of O(N) since strings are immutable and don’t have append in amortized O(1) like lists do
•  » » 6 months ago, # ^ |   0 no its o(1) search on the internet strings are mutable you can append at the back but if you want to append at the beginning then it will be o(n)
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 @SuperMo I don't understand your answer, strings aren't mutable in Python and the author's solution is in Python
•  » » » » 6 months ago, # ^ |   0 yeah sorry I thought it was c++
 » 6 months ago, # |   0 Is it possible to detect whether an edge belongs to a cycle by just DFS in linear time?
•  » » 6 months ago, # ^ |   +6 Yes, moreover — there is an algorithm for finding all bridges in a graph in linear time, based on dfsLooks like a more or less normal description of this algorithm: https://cp-algorithms.com/graph/bridge-searching.html
 » 6 months ago, # |   0 Thanks for the tutorial. I was said that G can be resolved in O(n^2) can someone say me how?
 » 6 months ago, # |   +17 Can someone explain G in simple terms
•  » » 6 months ago, # ^ | ← Rev. 3 →   +3 in my dp solution of $G$ I have 3 states : $pos$ : current position $a$ : index of the first unpainted cell $b$ : index of the last painted cell here is the code tell me if you don't understand the transitions
 » 6 months ago, # |   +6 can someone please explain the editorial of $F$ in details?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +11 First part: We should find minimal weight edge (u->v) that completes cycle. Second part: We should find the cycle including edge u->v. Detail on FA. For the first part, we use DSU to find out which vertexes are connected. For each edge (u->v), if u and v is already connected, then this edge completes cycle.B. We should iterate through each edge only once. And we should iterate descending order to find minimal weight edge. Consider three vertexes v1, v2, v3 form a cycle. Evaluating first two edge will make all three vertexes connected together. Then evaluating the third edge u->v will found out u and v is already connected, thus we can claim the third edge completes the cycle. If we don't iterate edges in descending order, the third edge might have bigger weight than first two edge!C. For the second part, there exists two paths from u to v. The minimal edge, and longer path without minimal edge. To travel in a cycle, we travel u -> v without minimal edge. Then we travel v -> u with minimal edge. If we want to find the path without minimal edge, simply exclude the minimal weight edge from graph and use DFS.My submission with some comments: 245285224
•  » » » 6 months ago, # ^ |   +3 thanks
 » 6 months ago, # |   0 Anyone resolved the problem D with Segment Tree?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Find min and max in range and check they if they are equal then there is no possible pair else you can print the index of min and max values. My solution
•  » » » 6 months ago, # ^ |   0 Thanks! :)
 » 6 months ago, # |   0 Can anyone tell me why is this giving wrong answer (for problem F). 245356240My idea here is, find the 2 nodes with minimum edge weight(say n1 & n2) and then do dfs from one of the node(n1) untill you reach another node(n2). In this way you will end up finding a cycle.What is wrong in this??
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 There may not always exist a simple cycle including the minimum edge.Consider this:16 71 3 21 2 42 3 33 4 14 5 54 6 65 6 7The lightest edge is "3 4 1". However, no cycle includes it.
•  » » » 6 months ago, # ^ |   0 Ahh Thanks
 » 6 months ago, # |   +3 1927D - Find the Different Ones! is required almost similar thought as 622C - Not Equal on a Segment.
 » 6 months ago, # | ← Rev. 2 →   0 Can someone explain Problem E in an easier way? I thought of switch alternately between largest evens and largest odds but that doesn't seem to work. UPD: I solved it. Used the intuition to increase the values at even indices and decrease at odd indices.
 » 6 months ago, # |   0 Excellent contest.
 » 6 months ago, # |   0 Is a very nice competition.The question is quite thought-provoking.I like it.
 » 6 months ago, # |   0 Can somebody please look into this submission of b and tell why I am getting TLE? Thank you. https://mirror.codeforces.com/contest/1927/submission/245142912
•  » » 6 months ago, # ^ |   0 $\mathcal{O}(n^2)$ too bad for B
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Thanks for the reply, I actually found out about the error(it was in my declaration of vector v); The complexity is not O(n^2), it has nested loops but it is accessing the indexes only once;
 » 6 months ago, # | ← Rev. 2 →   0 I am getting a memory limit exceeded error on test case 27 in code 245453024
 » 6 months ago, # |   +1 For problem F, can anyone tell me how to solve it if it also asks to minimize the number of vertices in the found cycle? Thanks.
•  » » 6 months ago, # ^ |   0 This is unsolvable within the problem constraints, as if you give the same weight to all edges, the problem turns into figuring out the shortest cycle in the graph .This is a well known problem and the fastest solution for it is $O(nm)$.
 » 6 months ago, # | ← Rev. 2 →   0 waiting for a rollback :(
 » 6 months ago, # | ← Rev. 2 →   0 Anyone knows how to solve DFS problems in Python? I seem to encounter runtime errors (I assume it's segmentation fault).For problem F, I found an $O(m)$ algorithm. 1 DFS to find the minimum edge on a cycle and 1 DFS to get that cycle.I do sys.setrecursionlimit(10**6) but it will not pass in Python. The same algorithm in C++ passes, but I assume if recursion gets deep enough, even C++ will not be able to do it.Is it the case that for $n > 10^5$ I should not use DFS? I'm not sure if there's a pattern to iterative DFS (stackless) but I find it a bit hard to shuffle the moments when I'm leaving the node and which metadata to keep.
•  » » 6 months ago, # ^ |   0 As a Python user, I have some advice for you. Recursive functions can be inefficient in Python, so it's best to avoid using them whenever possible. If you need to implement depth-first search (DFS), consider using a stack instead of recursion. Alternatively, you can explore other algorithms. For example, in this problem, you could use Union-Find (Disjoint Set Union, DSU) to find the minimum edge and Breadth-First Search (BFS) to detect cycles.
•  » » » 6 months ago, # ^ |   0 Thanks for the suggestion. The DFS works fine with CPython 3.10+ (not available on codeforces). I guess if I used union-find I'd have to write an iterative find, right, a recursive one can also break? def find(x): while x!=P[x]: P[x] = x = P[P[x]] This change in Python made the DFS work: https://docs.python.org/3/whatsnew/3.11.html#inlined-python-function-callsIs there an example of a correct way to think about DFS+stack. I think I would have to be careful to not push a node multiple times. If I need to do something when exiting the node (when all of the children are completely processed), then I need to not exit it twice. I also cannot pop immediately the node of the stack.If graph is not a tree, then I have to keep track of which nodes are pushed to the stack and not push them again. But I also have to keep track of which nodes I visited.
•  » » » » 6 months ago, # ^ | ← Rev. 6 →   0 To impliment path compression of union-find, recursion is enough. Pay attention to the depth of recursions. the depth of the union-find tree is small enough if you perform path compression each time you unite two elements. However, considering dfs on a linear graph, the depth is too large. It causes no problem if the depth is small (like $\le 10^3). In fact, I could get AC with recursive union-find even in Python3 (not PyPy). Regarding the way of rewriting DFS as DFS+stack, I'll show you two solutions to the problem: UF+DFS(recursion): submission:245574662 (TLE) UF+DFS(stack): submission:245574463 (AC) The dfs part of the cycle construction only differs, but they have the same result. (But rewriting is hard for me at least, I used bfs during the contest.) •  » » » » » 6 months ago, # ^ | 0 Looking at your stack solution, if you want to support extra processing on node exit (for example, let's say you're calculating number of children), You would have to also keep track if you exited a node already (not to overcount children). I guess I'm on the right path there, but the +/- trick is useful.I tried the stack solution for Problem F (with bfs for cycle):https://mirror.codeforces.com/contest/1927/submission/245556453But it says it takes too much memory.Thanks again, I guess it's just memory heavy.  » 6 months ago, # | 0 I am trying to solve 1927D - Find the Different Ones! using MO's algorithm. But, getting TLE. plz help me!!! •  » » 6 months ago, # ^ | 0 you don't need mo's algo for that. use monotonic stack instead •  » » » 6 months ago, # ^ | 0 thanks a lot. but, recently i am trying to solve MO's algo related problems. that's why i tried this using MO's. this is my submission.  » 6 months ago, # | 0 Does anyone know if there are any traps in Test 19 of Problem F? It seems that the sorting of edges requires O(mlogm), and the DFS to find a path requires O(n), but I keep getting TLE. Or am I just too silly to see some stupid bugs 245508630? I would really appreciate some advice! •  » » 6 months ago, # ^ | +3 Found the mistakes. No problem now! •  » » » 6 months ago, # ^ | 0 Why my DFS in F TLE in Test19 https://mirror.codeforces.com/contest/1927/submission/245777873 •  » » » » 6 months ago, # ^ | 0 I mistakenly declared an adjacency matrix (n*n elements) instead of an adjacency list (n*0 elements), and therefore got an TLE. I am not familiar with Java, so I'm not sure whether you stumbled upon the same mistake. It seems that Test 19 may have a large n, so maybe you can check whether you declared the graph correctly or made some mistakes that give you an O(n^2) complexity.-  » 6 months ago, # | ← Rev. 2 → 0 My Submission1927D - Find the Different Ones! 3 test cases have passed completely, 4 test case it is giving me wrong answer. Any suggestion how to fix that?  » 6 months ago, # | +7 I've recently gained an AC verdict on problem G, and I've decided to share my O($n^2$) solution. The reason for this is that I found the other explanations (including the editorial) not as deep as I would have liked them to be. So here it goes:Let $dp[i][j]$ be the minimum number of charges to use in order to paint all cells up until at least index $j$, with the restriction that we may only use charges up until index $i$ (both are inclusive).As always in DP, let's assume the worst initially, and gradually improve on them later on, so set all values to $+\infty$. To paint all cells until index 0 ($j=0$), we don't need to use any charges, so let all $dp[i][0]=0$.We will use two loops to fill our DP table: the outer loop will gradually allow the use of more and more charges, while in the inner loop we'll try to paint more and more cells using only the allowed charges, but at the same time, also trying to use the least possible of them.In each iteration of the outer loop, we're allowing the use of 1 more charge compared to the previous iteration. So the natural thing to do is to try to improve on the previous results. For this, we'll see what we can do with the recently allowed charge at index $i$. We could either not use this charge at all, use it to the left, or use it to the right.Not using this charge means $dp[i][j]=dp[i-1][j]$, using this charge to the left means $dp[i][j]=dp[i-1][i-A[i]]+1$ and using this charge to the right means $dp[i][i+A[i]-1]=dp[i-1][i-1]+1$. Don't forget to add the boundaries 0 and N, of course a few of these indices may exceed them! Naturally, it's possible for any of these subproblems that we've already found a more optimal solution, in these cases don't actually set them to these candidate values. Also, the case when we use the charge at index $i$ to the left isn't valid when $j > i$. Notice that when we use $i$ to the right, it has a constant $j$ value, so we don't need to put that into the inner loop. Also, because of the fact that we've only updated our DP table at edge cases of the possibilities the recently allowed charge offers, it's possible that we have a higher value at a lower $j$, so let's solve this issue using a loop after the first inner loop that fixes these values. Note that this doesn't increase our O($n^2$) time complexity.So why does this work? Because we only use lower $i$s to compute the optimal solution for higher $i$s, and these lower $i$s are guaranteed to already be solved. Why is that? Because we never set a new value for a lower $i$.Except I lied to you (I'm sorry), this does NOT work. We can see this solution failing for test case 11 in the example input. There is 1 more case to consider. That is, when we use 2 charges at indices $i$ and $j$ such that$j
 » 6 months ago, # | ← Rev. 3 →   0 A
 » 6 months ago, # | ← Rev. 2 →   0 Problem-D can easily be solved by using next greater and next smaller element.Claim : If in [l,r] we don't have all same elements then we could just pick the lth element and find its next strictly greater element or smaller as well . If that thing exists and is within r , then answer exists otherwise NOT .TC : O(n) for precomputation and O(1) per query.Hope it helps.
 » 6 months ago, # |   0 So I want to wonder that why the problem C couldn't accept this code? #include using namespace std; #define int long long #define mpr make_pair #define fr first #define sc second inline int read(){ int res=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') {res=res*10+(c-'0');c=getchar();} return res*f; } const int N=2e5+5; int t,n,m,k,a[N],b[N],ta[N],tb[N]; bool solve(){ n=read(),m=read(),k=read(); for (int i=1;i<=n;i++){ a[i]=read(); if (a[i]<=k) ta[a[i]]++; } for (int i=1;i<=m;i++){ b[i]=read(); if (b[i]<=k) tb[b[i]]++; } int ca=0,cb=0; for (int i=1;i<=k;i++){ if (ta[i]>0&&tb[i]<=0) ca++; else if (ta[i]<=0&&tb[i]>0) cb++; else if (ta[i]<=0&&tb[i]<=0) return 0; } if (ca>k/2||cb>k/2) return 0; return 1; } signed main(){ t=read(); while (t--){ if (solve()) puts("YES"); else puts("NO"); for (int i=1;i<=k;i++) ta[i]=tb[i]=0; } return 0; } 
•  » » 6 months ago, # ^ |   0 k can be as large as 4e5, and ai and bi can be as large as 1e6, so the length of your ta ans tb is too short. You should set N to 1e6+5.
 » 6 months ago, # |   0 F can be solvable using bridges, find the smallest weight edge (u,v) which is not a bridge ,it will be the answer, and for simplicity the required path will be largest path between u,v (can be found using dfs).
 » 6 months ago, # |   0 B.following the string problem is getting tle can anyone get it in python
 » 6 months ago, # | ← Rev. 3 →   0 Anyone can tell me how can i optimize this code of D problem. It's showing MLE which is obvious but then how alternatively I can solve it with same approach? def bs(s,e,a,dp): if(s==e): dp[s][e]=[False,s,s] return(False,s,s) if(s+1==e): dp[s][e]=[a[s]!=a[e],s,e] return(a[s]!=a[e],s,e) if(dp[s][e]!=-1): return(dp[s][e]) else: mid=(s+e)//2 x1,y1,z1=bs(s,mid-1,a,dp) x2,y2,z2=bs(mid,e,a,dp) if(x1 or x2): if(x1): dp[s][e]=[True,y1,z1] return([True,y1,z1]) else: dp[s][e]=[True,y2,z2] return([True,y2,z2]) else: if(a[y1]!=a[y2]): dp[s][e]=[True,y1,y2] return([True,y1,y2]) elif(a[y1]!=a[z2]): dp[s][e]=[True,y1,z2] return([True,y1,z2]) elif(a[y2]!=a[z1]): dp[s][e]=[True,y2,z1] return([True,y2,z1]) elif(a[y2]!=a[y1]): dp[s][e]=[True,y2,y1] return([True,y2,y1]) else: dp[s][e]=[False,s,e] return([False,s,e]) for _ in range(int(input())): n=int(input()) a=list(map(int,input().strip().split())) q=int(input()) dp=[] for i in range(n): dp.append([]) for j in range(n): dp[i].append(-1) for i in range(q): l,r=map(int,input().strip().split()) if(a[l-1]!=a[r-1]): print(l,r) else: s,e=l-1,r-1 ans=bs(s,e,a,dp) if(not ans[0]): print(-1,-1) else: ab=ans[1]+1 cd=ans[2]+1 print(min(ab,cd),max(ab,cd)) Thanks in advance !!
 » 6 months ago, # | ← Rev. 2 →   0 Can someone please help me find the test case on which my code is failing. It is failing test case 6 of problem G. code
•  » » 6 months ago, # ^ |   +3 Take a look at Ticket 17336 from CF Stress for a counter example.
•  » » » 6 months ago, # ^ |   0 Thanks!
 » 6 months ago, # |   0 Can anyone explain me the second paragraph of the solution of Problem D?
 » 6 months ago, # |   0 Can someone please explain to me why solution in java 245738199 is giving TLE whereas same solution in c++ (245745549) works
•  » » 6 months ago, # ^ |   0 StringBuffer is OK. 248030776. Maybe problem it is.
 » 6 months ago, # |   0 Hi all,I read the tutorial and got accepted on problem F, but I still have one question: What if we just choose the edge with the minimum weight and then find any cycle which contains that edge. Isn't that simpler? Do we still have to use DSU and stuff?Thanks in advance.
 » 6 months ago, # |   0 Why my DFS in F TLE in Test19 https://mirror.codeforces.com/contest/1927/submission/245777873
•  » » 6 months ago, # ^ |   0 Yeah I got the same problem https://mirror.codeforces.com/contest/1927/submission/245882846 For me its probably bc I used clone but idk how else you would do it
 » 6 months ago, # |   0 Thanks for Python solutions besides the great contest!
 » 6 months ago, # |   0 someone pls explain the solution to G in simple wordsdifficult to get around for me
 » 6 months ago, # |   0 Can anyone look into my submission for F? It's MLE in TC 7.https://mirror.codeforces.com/contest/1927/submission/246026044
 » 6 months ago, # | ← Rev. 2 →   0 I am trying for the Problem G seems like I am stuck for this test case 1 1 4 1 3 2 t = int(input()) for i in range(t): n = int(input()) lst = input().split() for j in range(n): lst[j] = int(lst[j]) dic = {} def f(i, last): if(i>=len(lst)): if(last!=-1): return float("inf") else: return 0 else: if((i, last) in dic): return dic[(i, last)] notblast = float("inf") blastleft = float("inf") blastright = float("inf") if(last!=-1): if(i-lst[i]+1<=last): blastleft = 1 + f(i+1, -1) flag = False for j in range(i, min(i+lst[i]+1, len(lst))): if(j-lst[j]+1<=last): flag = True break if(flag): blastright = 2 + f(i+lst[i], -1) notblast = f(i+1, last) else: blastright = 1+f(i+lst[i], -1) notblast= f(i+1, i) blastleft = 1+f(i+1, -1) dic[(i, last)] = min(notblast, min(blastleft, blastright)) return dic[(i, last)] print("Ans", f(0, -1)) Any Ideas why this gives the output as 2 the correct output is 3 though
 » 6 months ago, # | ← Rev. 3 →   0 alternate solution for F first remove all the bridges from the graph now every edge in graph has atleast one cycle so choose the one which has minimum weight and and get the cycle code#include using namespace std; char nl = '\n'; using i64 = long long; int n, m; vector>> g; vector> brij; vector visited; vector tin, low; int timer; void dfs(int v, int p = -1) { visited[v] = true; tin[v] = low[v] = timer++; for (auto& to : g[v]) { if (to[0] == p) continue; if (visited[to[0]]) { low[v] = min(low[v], tin[to[0]]); } else { dfs(to[0], v); low[v] = min(low[v], low[to[0]]); if (low[to[0]] > tin[v]) brij.push_back({v, to[0]}); } } } void find_bridges() { timer = 0; visited.assign(n, false); tin.assign(n, -1); low.assign(n, -1); for (int i = 0; i < n; ++i) { if (!visited[i]) dfs(i); } } void solve(int t) { // cout << "test #" << t << nl; cin >> n >> m; g.clear(); g.resize(n); brij.clear(); for(int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--; v--; g[u].push_back({v, w}); g[v].push_back({u, w}); } find_bridges(); for(auto& e : brij) { for(int i = 0; i < g[e[0]].size(); i++) { if(g[e[0]][i][0] == e[1]) { g[e[0]].erase((g[e[0]].begin() + i)); break; } } for(int i = 0; i < g[e[1]].size(); i++) { if(g[e[1]][i][0] == e[0]) { g[e[1]].erase((g[e[1]].begin() + i)); break; } } } pair ini; int cur = INT_MAX; for(int i = 0; i < n; i++) { for(auto& a : g[i]) { if(a[1] < cur) { cur = a[1]; ini = make_pair(i, a[0]); } } } for(int i = 0; i < g[ini.first].size(); i++) { if(g[ini.first][i][0] == ini.second) { g[ini.first].erase(g[ini.first].begin() + i); break; } } for(int i = 0; i < g[ini.second].size(); i++) { if(g[ini.second][i][0] == ini.first) { g[ini.second].erase(g[ini.second].begin() + i); break; } } // bfs form ini.first to ini.second vector p(n, -1); queue q; q.push(ini.first); p[ini.first] = ini.second; while(!q.empty()) { int u = q.front(); q.pop(); for(auto& c : g[u]) { if(p[c[0]] != -1) continue; p[c[0]] = u; q.push(c[0]); } } vector ans; int x = ini.second; while(1) { ans.push_back(x); if(x < 0 || x >= n) break; x = p[x]; if(ans.back() == ini.first) break; } cout << cur << " " << ans.size() << nl; for(auto& a : ans) cout << a + 1 << " "; cout << nl; } int main() { ios::sync_with_stdio(false); cin.tie(0); int tt = 1; cin >> tt; for(int t = 1; t <= tt; t++) solve(t); } 
 » 6 months ago, # |   0 I tried using binary search to find l, r for problem D.Approach -> - storing start and end indices for all intervals for which values of array are equal. - then for each query using upper bound to check if given interval exists inside any interval with all equal values to return -1, -1 otherwise returning the appropriate indices.Here is the code:- My Code#include using namespace std; pair find_indices_pair(vector& a, vector& start_indices, vector& end_indices, int n, int l, int r) { pair target_indices_pair; if((start_indices.size() == 0) || (r <= start_indices[0]) || (l >= end_indices[end_indices.size() - 1])) { target_indices_pair.first = l; target_indices_pair.second = l + 1; return target_indices_pair; } auto itr = upper_bound(start_indices.begin(), start_indices.end(), l); itr--; int req_index = itr - start_indices.begin(); if(l >= end_indices[req_index]) { target_indices_pair.first = l; target_indices_pair.second = l + 1; return target_indices_pair; } else if(end_indices[req_index] >= r) { target_indices_pair.first = -1; target_indices_pair.second = -1; return target_indices_pair; } else if(end_indices[req_index] < r) { target_indices_pair.first = end_indices[req_index]; target_indices_pair.second = end_indices[req_index] + 1; return target_indices_pair; } target_indices_pair = {-1, -1}; return target_indices_pair; } int main() { int t; cin >> t; while(t--) { int n; cin >> n; vector a(n + 1); for(int i = 1; i <= n; i++) { cin >> a[i]; } vector start_indices, end_indices; int st = 1; while(st <= n) { int ed = st + 1; if(a[st] != a[ed]) { st++; continue; } while(ed <= n) { if(a[st] != a[ed]) { start_indices.push_back(st); end_indices.push_back(ed - 1); st = ed; break; } ed++; if(ed == (n + 1)) { start_indices.push_back(st); end_indices.push_back(n); st = n + 1; break; } } } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; pair res = find_indices_pair(a, start_indices, end_indices, n, l, r); cout << res.first << " " << res.second << "\n"; } cout << "\n"; } return 0; } `To me issue seems to be where i am creating start_indices and end_indices vectors. If anyone can help it would be great. Thanks.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 ):
 » 6 months ago, # |   0 problem E different solution with explanation https://mirror.codeforces.com/contest/1927/submission/248029334
 » 13 days ago, # |   0 My Approach for problem D using the Binary Search and storing the diff points of array earlier in a separate vector , it might be a childish solution but I liked my approach because its easy to understand.Code:Have a look