By Vladosiya, history, 4 weeks ago,

Idea: senjougaharin

Tutorial
Solution

2000B - Seating in a Bus

Idea: myav

Tutorial
Solution

2000C - Numeric String Template

Idea: myav

Tutorial
Solution

2000D - Right Left Wrong

Tutorial
Solution

2000E - Photoshoot for Gorillas

Tutorial
Solution

2000F - Color Rows and Columns

Idea: senjougaharin

Tutorial
Solution

2000G - Call During the Journey

Idea: senjougaharin

Tutorial
Solution

2000H - Ksyusha and the Loaded Set

Idea: senjougaharin

Tutorial
Solution
• +27

 » 4 weeks ago, # |   0 can anyone pls tell why this code is getting a runtime error. for Problem D Code#include using namespace std; typedef long long ll; #define f(i,a,b) for(ll i=a;i=a;i--) /* When a man learns to love he must bear the risk of hatred */ /* I don't know WTF am I doing */ /* Now I hate You */ int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll t;cin>>t; while(t--){ ll n;cin>>n; vector a(n); f(i,0,n){ cin>>a[i]; } string str; cin>>str; vector leftsig,rightsig; f(i,0,n){ if(str[i]=='L')leftsig.push_back(i); else rightsig.push_back(i); } ll left = 0; ll right = rightsig.size()-1; ll sum = 0; while(left=0 && leftsig[left]
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 consider the case where there are no 'R' in the string. in this scenario, your 'right' variable would be initialized with the value -1edit : avoid using C++17 (GCC 7-32) and use C++20 (GCC 13-64) instead
•  » » » 4 weeks ago, # ^ |   0 you mean something like this -> n = 6, a(n) = 1 1 1 1 1 1 s = LLLLLL -> and the output should be 0 right. actually I checked this one already and it gives me 0 perfectly fine. Cause I'm checking the out of bound condition before using those
•  » » » » 4 weeks ago, # ^ |   0 I admit I do not know much about C++17 (32-bit), but if I had to guess, this particular error might be occurring because your while loop condition:while(left < leftsig.size() && right >= 0 && leftsig[left] < rightsig[right]) {is not stopping after right >= 0 evaluates to false. Instead, it continues evaluating leftsig[left] < rightsig[right], which could cause an access violation if right is -1 and thus result in the erroryou can fix it by choosing C++20 (GCC 13-64) as your compiler when you submit the codehttps://mirror.codeforces.com/contest/2000/submission/276452095
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 yeah I guess C++17 doesn't stop when a condition is false in the loop conditions, untill it checks all the conditionsedit: I used the prefix sum to avoid tle and it went ohk
•  » » » 4 weeks ago, # ^ |   0 oh thanks for the help it went perfectly just by changing this. Wasn't expecting it to be this sort of issue, will use C++ 20 always :) .
•  » » 4 weeks ago, # ^ |   0 This solution will give tle as you are calculating sum of subarray again and again. Instead use prefix sum to get the sum of the subarray.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I did that that in the updated code here -> Code#include using namespace std; typedef long long ll; #define f(i,a,b) for(ll i=a;i=a;i--) /* When a man learns to love he must bear the risk of hatred */ /* I don't know WTF am I doing */ /* Now I hate You */ int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); ll t;cin>>t; while(t--){ ll n;cin>>n; vector a(n); f(i,0,n){ cin>>a[i]; } string str; cin>>str; vector prefix_sum(n+1, 0); for(ll i = 0; i < n; i++) { prefix_sum[i+1] = prefix_sum[i] + a[i]; } vector leftsig,rightsig; f(i,0,n){ if(str[i]=='L')leftsig.push_back(i); else rightsig.push_back(i); } ll left = 0; ll right = rightsig.size()-1; ll sum = 0; while(left=0 && leftsig[left]
 » 4 weeks ago, # |   0 I need help Can anyone tell me why my solution in proplem E got TLE when i write it in java , but when i write the same code in c++ i got ACjava solution --> Your text to link here...c++ solution --> Your text to link here...
•  » » 4 weeks ago, # ^ |   0 С++ is faster than java
 » 4 weeks ago, # |   0 someone explain how to intuit the way they count it in problem E please.
•  » » 4 weeks ago, # ^ |   0 consider 2D adjacent difference it could be a lot easier
•  » » 4 weeks ago, # ^ |   0 do u know diffrence array? to update values in range for 1d vector it can be used here to count for 2d vector then 2d prefix sum
 » 4 weeks ago, # | ← Rev. 3 →   +17 I am impressed by how treap is being casually used in a div3 contest editorial (problem H). (Context: Of course I am well aware that this is not how most contestants solved, or are supposed to solve it, but rather make use of the (non-essential) constraints max <= 2e6. It is also clear that a fully online solution of this without the extra constraints will have to involve your favourite BBST. Though, I don't know how many people will get confused by the editorial. )
•  » » 4 weeks ago, # ^ |   +33 They took the effort to explain the std::set part but not the treap part :)
•  » » 3 weeks ago, # ^ |   0 If possible can you explain how to do it without treap? I was thinking of a solution where I can maintain an array where the indices represent the lengths of the free segments and the value at that index is the value of the left border of that segment, then I just need to find suffix minimums to answer any query. I was thinking of using segment tree for handling updates and suffix range queries, but I think that will TL because there is no bound on sum of $max(a_i)$ across all test cases and my time complexity would become $O(T\cdot max(a_i) \cdot\log{max(a_i)})$ in that case.
•  » » » 3 weeks ago, # ^ |   0 You can reuse the same segment tree. So initialise one segment tree with size max(a_i), at the end of each test case you undo all insertions. I take that you already know how to "find first index in segment tree that is >= some value", but for others this can be handled by using a max-segment tree and a standard segment tree descend
•  » » » » 13 days ago, # ^ |   0 I tried implementing this solution but I received TLE. Can you help me find out why this is happening? https://mirror.codeforces.com/contest/2000/submission/278601400
•  » » » » » 13 days ago, # ^ |   0 Your segment tree descent code is O(n). Read the segment tree before deciding going left or right, rather than just recur/
•  » » » » » » 12 days ago, # ^ |   0 Hi I just reimplemented a log(n) descent. However, I am still getting TLE ;-;https://mirror.codeforces.com/contest/2000/submission/278684047
•  » » » » » » » 12 days ago, # ^ |   0 I cannot find an obvious mistake. Try to run it in gym with more TL and see how close it is. If it is close to 3s, then it may simply be that recursive seg tree are too slow to pass. My solution that takes 1500ms in Kotlin is iterative.
•  » » 3 weeks ago, # ^ |   0 treap sounds like something you cover a pool with
 » 4 weeks ago, # |   +9 for E, I completely missed the n*m<=2e5 bound and coded a O(nlogn + mlogm + wlog(n*m)) solution276188663
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I also misread the n*m<=2e5 constraint, and I tried to code a bfs type solution starting from the center of the grid where we greedily visit cells in the graph that have the most subarrays containing them. I failed in the implementation, but is your solution idea similar?
•  » » » 4 weeks ago, # ^ |   +1 yes, similar, that's pretty much what I did
•  » » 4 weeks ago, # ^ |   0 I got scared when I didn't see the n*m <= 2e5 condition and I immediately re-checked the problem statement :)
• »
»
»
4 weeks ago, # ^ |
+3

## 🆗

 » 4 weeks ago, # |   0 H can be solved using segment tree. 276462150
 » 4 weeks ago, # |   0 How can I report suspected cheating in this round?
 » 4 weeks ago, # | ← Rev. 3 →   0 please help me with my submissions for C. I've used a map for int to char mapping, and then a vector of size 26 for char to in mapping. My conditions are also correct (acc to me) so please if anyone can see why is my code failing please help me ! I am getting WA on test 18.276216688so i just changed my code to use 2 maps instead of 1 map + 1 vector and it got accepted. why did this happen ?276481407i solved it.. i was initializing vector with -1 which is wrong. i made it INT_MIN and it worked276482552
 » 4 weeks ago, # |   +3 The problem H has a beautiful solution using sqrt decomposition (It works slower than the author's solution, but it seems to me easier to understand and write). My example solution: https://mirror.codeforces.com/contest/2000/submission/276433907
•  » » 4 weeks ago, # ^ |   +4 Problem H Solution without any specific method/data structure but only logic — 276496494
•  » » » 4 weeks ago, # ^ |   0 what is the time complexity of this block? auto fitr = que.lower_bound(x); if(fitr == que.end()) cout << -1 << " "; else { int mini = INT_MAX; for(; fitr != que.end();) { mini = min(mini, *(fitr->second.begin())); fitr = next(fitr); } cout << mini << " "; } 
•  » » » » 4 weeks ago, # ^ |   0 Worst case is ~ $\sqrt {2 . 10^6}$. When the set has 2e6-1, 2e6-4, 2e6-8, 2e6-13, .... and the query is "? 1" ig
 » 4 weeks ago, # |   0 For problem D, I know that it can be solved using 2 pointers or manually matching the L's with R's, but still I can't figure out what is wrong with my solution, it gives Wrong Answer on Test 7, i.e. it is working for smaller inputs but not for larger ones, (maybe, I don't know). It would be very helpful, if someone could point out the idea that I am missing.
 » 4 weeks ago, # |   0 Can someone explain me Problem F in detail? I saw shayan's vid but I keep getting lost. (I have a fair experience with dp)
•  » » 4 weeks ago, # ^ |   0 The hardest part of this problem is understanding optimal way of painting single rectangle. Like they say in editorial you must always choose to paint single column or row of minimum size. For example, if you have 3 by 4 rectangle you unpainted rectangle will change like this: 3x4 -> 3x3 -> 3x2 (or 2x3, does not matter) -> 2x2 -> 2x1 (or 1x2) -> 1x1 -> 0x0 Every transition will give you one score point (except for last which gives 2 points because we paint one row and one column at the same time). You perform this sequence of operations on the first rectangle, keep track on the number of operations (cnt1) and score (s), calculate recursively min. number of operations for the rest of the rectangles to achieve (k — s) score (cnt2), choose min(cnt1 + cnt2) after painting sequence is complete.
•  » » » 4 weeks ago, # ^ |   0 Thanks! :)
 » 4 weeks ago, # |   0 can someone explain, why the sample testcase 1 answer is 0. I think we can wait upto 19 minutes and then take the bus route 1 — 5 which will cost 30 minutes, and we will arrive on 5 at 49 minutes ?
•  » » 4 weeks ago, # ^ |   0 You cannot ride a bus during entire phone call, not just start of it.
 » 4 weeks ago, # |   -17 My Insights for A,B,C Problem ABasic Implementation Problem .We must always start with $10$ , thus the length of string must be at least $3$ thus the answer is NO if $|s|<3$ , otherwise the answer is YES if $s[0],s[1]=10$ and int(s[2:])>=2 and s[2]!='0' otherwise NO Codedef solve(): s=input() if(len(s)<3): print("NO") elif(s[0]+s[1]=='10' and int(s[2:])>=2 and s[2]!='0'): print("YES") else: print("NO") for _ in range(int(input())): solve()  Problem BA Typical Introductory Simulation Problem$a_0$ will be the first seat always , keep iterating through the array , if there's any $a_{i-1} \notin \text{seats}$ and $a_{i+1} \notin \text{seats}$ then the answer is NO , otherwise the answer is YES Codedef solve(): n=int(input()) a=list(map(int,input().split())) o={a[0]} for i in range(1,n): if(not a[i]-1 in o and not a[i]+1 in o): print("NO") return o.add(a[i]) print("YES") return for _ in range(int(input())): solve()  Problem CNice Introductory Problem about using map , unordered_map data structures (in c++) or dict (in python)For each string $s$ it must satisfy $|s|=n$ as the template requires , iterate through the elements of the array $a$ and current string $s$ (since they have the same length $|s|=|a|=n$) , create two maps $mp1$ , $mp2$ and alternate the values so we can check the template requirements $mp1[s[i]]=a[i]$ and $mp2[a[i]]=s[i]$ and vice versa is possible as well , after checking of all values , if the above holds then it's a valid template otherwise it's not. Codedef solve(): n = int(input()) a = list(map(int, input().split())) m = int(input()) for _ in range(m): s = input().strip() if len(s) != n: print("NO") continue mp1 = {} mp2 = {} consistent = True for i in range(n): x, y = a[i], s[i] if x in mp1: if mp1[x] != y: consistent = False break if y in mp2: if mp2[y] != x: consistent = False break mp1[x] = y mp2[y] = x if consistent: print("YES") else: print("NO") for _ in range(int(input())): solve() $\text{Nice Educational Contest overall !}$
 » 4 weeks ago, # |   0 Can anyone help me find out the test case for which 276261336 problem C (test case 18), failed ?. Appreciate any help thank you :)
•  » » 3 weeks ago, # ^ |   0 I found this test case: Test1 3 0 0 1 4 CBB ACE D DD which in my code returns: ResultNO NO NO NO and in yours: ResultNO YES NO NO Hope it helps!
•  » » » 3 weeks ago, # ^ |   0 This is awesome, Thanks a lot :)
 » 4 weeks ago, # | ← Rev. 4 →   0 For problem G sample 1, can someone share the route which corresponds to a starting time of 0? From what I understand of the problem, there should be no solution and the answer should be -1. Maybe I am overlooking something. I am copying the sample below for convenience. 5 5 100 20 80 1 5 30 100 1 2 20 50 2 3 20 50 3 4 20 50 4 5 20 50 
•  » » 4 weeks ago, # ^ |   0 In time 0, walk through the edge from 1 to 5. That will take 100 units of time, which fits in t0.
 » 4 weeks ago, # |   0 For problem E, the image in the Notes section loaded for me without any gorillas and I lost a lot of time trying to make sense of the image.
 » 4 weeks ago, # | ← Rev. 3 →   0 For Problem F, sample 6, reproduced below, can someone explain how the required 25 points can be obtained in 80 operations, as given in the sample solution? 3 25 9 2 4 3 8 10 
•  » » 3 weeks ago, # ^ |   0 First we will completely fill the 2*9 and 4*3 rectangles. After this our score would be 18 and operations are 30. After this we will start filling the 8*10 rectangle in this order — 8, 8, 8, 7, 7, 6, 6. This would lead to a total score of 25 in 80 operations.
•  » » 3 weeks ago, # ^ |   0 Take all 9x2 for 11 points, take all 4x3 for 7 points, take all but a 5x6 rectangle from 8x10 (which is 50 squares) for 7 points. 8+8 + 8+7 + 7+6 + 6 = 50 11+7+7 =25, 18+12+50=80
 » 4 weeks ago, # |   0 are there public solutions using python? as i am currently learning python and want to master it before starting c++
 » 3 weeks ago, # |   0 did any one solved F using greedy?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Can you tell me how 35 operations are required in last test case4 18 5 4 8 5 8 3 6 2
•  » » » 3 weeks ago, # ^ |   0 Use entire first and last rectangle and then use rectangle which is having b = 3 to make the score 18
 » 3 weeks ago, # | ← Rev. 2 →   0 Can anyone please explain what's wrong in my approach of problem G. I applied binary search to find how late we can start to reach on time. What I'm doing in my modified dijkstra is that if I can take bus then then will take it but if I will get a call in between or currently on a call then I will take the best of wait till the call is finish and take bus or walk. My Code#include using namespace std; // Include necessary header files for ordered_set #include #include using namespace __gnu_pbds; // Define an ordered set typedef tree, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // Define macros for convenience #define int long long #define f(i, a, b) for (int i = a; i < b; i++) #define rf(i, a, b) for (int i = a; i >= b; i--) #define vi vector #define vpii vector> #define vvvi vector>> #define vvi vector> #define vvpi vector>> #define vb vector const int inf = 1e18; int n, m, t0, t1, t2; vvvi adj; int dijkstra(int src, int dest, int start_time) { vi dist(n + 1, inf); dist[src] = start_time; priority_queue> pq; pq.push({start_time, src}); int dur = t2 - t1; while (!pq.empty()) { vi curr = pq.top(); pq.pop(); int u = curr[1]; int time = curr[0]; if (time > dist[u]) continue; for (vi edge : adj[u]) { int v = edge[0]; int l1 = edge[1]; int l2 = edge[2]; int new_time = time + l1; if (time >= t1 && time < t2) { // Call is active if (dur >= l2) { // take l2 route new_time = time + l2; dur -= l2; } else { // take l2 route if (l2 < (t2 - time) + dur + l1) { new_time = time + l2; dur = 0; } else { // wait and take l1 route new_time = time + (t2 - time) + dur + l1; dur = 0; } } } else if (time <= t1 && t1 < new_time) { // Crosses into active call period if (dur >= l2) { // take l2 route new_time = time + l2; dur -= l2; } else { if (l2 < (t1 - time) + dur + l1) { // take l2 route new_time = time + l2; dur = 0; } else { // wait and take l1 route new_time = time + (t1 - time) + dur + l1; dur = 0; } } } if (new_time < dist[v]) { // Relaxation dist[v] = new_time; pq.push({new_time, v}); } } } return dist[dest]; } void solve() { cin >> n >> m; cin >> t0 >> t1 >> t2; adj = vvvi(n + 1); f(i, 0, m) { int u, v, l1, l2; cin >> u >> v >> l1 >> l2; adj[u].push_back({v, l1, l2}); adj[v].push_back({u, l1, l2}); } int low = 0, high = t0; int ans = -1; // binary on how late we can start our journey to reach on time while (low <= high) { int mid = low + (high - low) / 2; if (dijkstra(1, n, mid) <= t0) { ans = mid; low = mid + 1; } else { high = mid - 1; } } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int tc; cin >> tc; while (tc--) solve(); return 0; } 
 » 3 weeks ago, # |   0 Is there anyone who solved problem G using python? My code exceeded time limit on test 17. Codefor test in range(int(input())): n, m = [int(i) for i in input().split()] t0, t1, t2 = [int(i) for i in input().split()] G = dict() for i in range(m): #made graph start, end, bus, walk = [int(i) for i in input().split()] if start not in G: G[start] = [[end,(bus,walk)]] else: G[start].append([end,(bus,walk)]) if end not in G: G[end] = [[start,(bus,walk)]] else: G[end].append([start,(bus,walk)]) #Djikstras from the end (node n) to start (node 1) using latest, latest[n]=t0 #if he can ride bus (not on call), ride bus #else choose max (starting time) of walking and waiting for call to end then ride bus latest = [-1]*(n)+[t0] cur = n; vis = []; frontier = [n] while True: #if cur=k, then we have the shortest path to k cur = frontier[0] #pick largest time for i in frontier: if latest[i] > latest[cur]: cur = i if cur == 1: break frontier.remove(cur) vis.append(cur) for prev, time in G[cur]: if prev in vis: continue bus = time[0]; walk = time[1] a = latest[cur] if (t2 <= a - bus) or (t1 >= a): #can ride bus latest[prev] = max(latest[prev], a - bus) else: latest[prev] = max(latest[prev], t1 - bus, a - walk) if prev not in frontier: frontier.append(prev) print(latest[1]) 
 » 3 weeks ago, # |   0 Thanks for the editorial ^_^
 » 3 weeks ago, # |   0 Can someone please explain me how are we getting 35 operations in last test case of sample? I am getting 36 operations to score 18 points. 4 18 5 4 8 5 8 3 6 2 
•  » » 3 weeks ago, # ^ |   0 Fill the 6 x 2 (score = 8 & operations = 12) rectangle and 5 x 4 rectangle (score = 9 & operations = 20) completely and one row of 8 x 3 rectangle (score = 1 & operations = 3). Therefore total operations and score would be 12 + 20 + 3 = 35 and 8 + 9 + 1 = 18 respectively.
 » 3 weeks ago, # | ← Rev. 2 →   0 Why am I not official in this round !!!
 » 2 weeks ago, # |   0 In problem G, why did I get TLE when I used priority_queue but after switching to set> it became AC?
 » 12 days ago, # |   0 I am only into dsa, can that help me in cp. I am new to this field
 » 4 days ago, # |   0 In problem H, I am getting WA, Can someone explain what am I doing wrong.I am trying to maintain the free segments and updation using multiset. I am maintaining (dist, left_endpoint) in the multiset and the points currently in the set. Then I am performing the insertion and removal operation by taking the next and previous points from the points set.Link to my solution: submission
•  » » 3 days ago, # ^ |   0 I did the same thing with you, and also got WA in test case 2.
•  » » » 3 days ago, # ^ |   0 Were you able to solve the issue??
•  » » » » 3 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } I can not, but I do not know why. It seems quite right to me.
•  » » 2 days ago, # ^ |   0 I have a test case totay and my code gets the wrong answer. Now I find the problem in my code with this case. You can test yours. input: 1 6 1 4 6 7 8 9 3 ? 5 + 10 ? 1 output 10 2
•  » » » 2 days ago, # ^ |   0 Yes my code is also failing this TC. The issue is that since I have sorted the multiset based on distance so there might be a smaller point later on but with a bigger distance. I need to find the lowest value available in suffix of distances starting from k.