### DishonoredRighteous's blog

By DishonoredRighteous, history, 4 days ago,

Hello, Codeforces!

I'm glad to invite you to Round 791 which will start at May/14/2022 12:35 (Moscow time). Please notice the unusual time.

There will be 6 problems in the round. Round is based on Team Olympiad in Lipetsk which is being held for the seventh time. Problems were proposed and prepared by iakovlev.zakhar, Kon567889, iura, andr1y, Masha237, welleyth and me. I would like to thank Aleks5d and KAN for CF round coordination and testers: Um_nik, 353cerega, errorgorn, Stepavly, divanik, nnv-nick, 4qqqq, to be continued...

Of course, I'd like to thank all Codeforces team for Codeforces and Polygon beautiful platforms!

I also would like to thank golikovnik, egneeS, dshindov and Inessa Shuykova (Lipetsk teams' coach) for preparing other Olympiad problems that haven't been taken for this round.

Note that if you are an official participant of the Olympiad, you are not allowed to participate in this round.

Scoring distribution will be announced later.

Wish you good luck and high rating!

UPD.1 Scoring distribution: $500 - 1000 - 1500 - 1750 - 2250 - 3000$.

UPD.2 Congratulations to winners!

Official participants:

Unofficial participants:

UPD.3 Editorial is available here.

• +225

 » 4 days ago, # |   -17 Team based round... interesting, will participate.
•  » » 3 days ago, # ^ |   0 is there team participation?
•  » » » 3 days ago, # ^ |   0 I don't think so
 » 4 days ago, # |   +42 Users rated >= 2100 can't seem to register for the round?
•  » » 4 days ago, # ^ |   +6 fixed
•  » » » 46 hours ago, # ^ |   +3 fixed
 » 4 days ago, # | ← Rev. 2 →   +2 I like when contests are at this time. (5:35 AM, Saturday for me) It forces me to not sleep in and be a lazy bum
•  » » 3 days ago, # ^ |   0 Mine is perfect dinner time
•  » » » 3 days ago, # ^ |   0 ME TOO(I finally don't have to take part in the contest at 22:35).
•  » » » » 2 days ago, # ^ |   0 +1
 » 3 days ago, # |   +11 hopeforces
 » 3 days ago, # |   0 Will the problems be a different style than regular rounds?
•  » » 3 days ago, # ^ |   +14 Nope
 » 3 days ago, # |   0 i see olympiad i upvote (unless its russian, then i just comment)
•  » » 3 days ago, # ^ |   0 It's a Russian olympiad. You didn't upvote?
 » 3 days ago, # |   +60 CF 791 -> ABC 251 -> Code Jam Round 2No clashes with 20-25 mins break each. Sweet. Thanks for the unusual time :)
•  » » 3 days ago, # ^ |   -20 In addition, there is a Leetcode contest at the usual time of codeforces rounds.
 » 3 days ago, # |   -13 Guys, be careful. Unusual time
 » 3 days ago, # |   0 Is it only me, or does everyone feel that contest at an unusual time has less participation than the usual time contest? Hence have less probability for the rating to increase. I know we should not give contest for rating, but still...
 » 3 days ago, # |   0 This round will be hard. Good luck everybody!!!
•  » » 3 days ago, # ^ |   +2 Hard like the most of unusual time contests but the standing will be much greater then other rounds so rating will also increase more then other contests. Point to think! And Wishing good luck to you all
•  » » » 3 days ago, # ^ |   0 Good luck to you too.
 » 3 days ago, # |   +1 How to know if a contest is unrated for me, I am new to the cf and could not find any official post on this info yet ?
•  » » 3 days ago, # ^ |   0 For gray users all the rounds (expect Div.1, because you can't register for it + some rounds like april fools contest) are rated.
•  » » » 3 days ago, # ^ |   0 thanks for the info! does that mean div 3 users can participate up to div 2 rounds and also not to div 4 rounds as well?
•  » » » » 2 days ago, # ^ |   +6 See, as a grey coders can give div, 2, 3, 4, and all of these are rated for them. I think you are trying to think of these contests in terms of CodeChef contest, those two are pretty different.
•  » » » » » 2 days ago, # ^ |   0 yeah I see. Thats why I was super confused at first, but the lack of official post on how ratings works on codeforces. I found a old post that explains div 3 but I could not find anything which provides all the information at one place.
 » 3 days ago, # |   +12 The unusual time strikes back.
 » 3 days ago, # |   -8 Why so unusual time? anyone any idea
•  » » 3 days ago, # ^ |   +4 There is olympiad in this time, round based on it. The unusual time is to avoid cheating
•  » » » 2 days ago, # ^ |   0 Oh got that
•  » » 3 days ago, # ^ |   +4 There's also a codejam round on the usual time.
 » 3 days ago, # |   -6 Why the time has changed ? Not great time
 » 3 days ago, # |   0 If the score is more than 2100, why do people with a score of more than 2100 participate in the ranking
•  » » 2 days ago, # ^ |   +16 First,it's rating.It's because they would like to practice since there is no div.1 for it.
 » 3 days ago, # |   -14 "i_am_completely_useless for being completely useless." -- Sakura :))xD
•  » » 3 days ago, # ^ |   -14 Nice quote...
•  » » » 2 days ago, # ^ |   -14 Thanks!
•  » » 2 days ago, # ^ |   -14 Nice bro!
•  » » » 2 days ago, # ^ |   -14 Thanks!
 » 2 days ago, # |   +9 Thank you for the unusual time!
 » 2 days ago, # |   -8 excited for this contest, go go go !
 » 2 days ago, # |   -8 My First CF Contest! Woohoo!
 » 2 days ago, # |   -8 Unfortunately, I need classes at that time, so I can't participate in this contest.
 » 2 days ago, # |   -10 QueryForces
 » 2 days ago, # |   +8 Pretests in C must be extremely weak
•  » » 2 days ago, # ^ |   -8 edge cases ?
•  » » » 2 days ago, # ^ |   +8 first q/2 queries of type 1 having x = i , y = i for i 1 to q/2Then next q/2 queries of type 3 having x1 = 1 , y1 = 1 , x2 = n , y2 = n .If somebody checked type 3 queries linearly from x1 to x2 , or y1 to y2 then Complexity will be O(Q*N) and there are many such accepted solutions
 » 2 days ago, # |   +11 waiting for contest finish to get solution for problem E
•  » » 2 days ago, # ^ |   +1 saw your dp solution of c question , edu round :) love u bro
•  » » » 2 days ago, # ^ |   0 Thanks:)
•  » » 2 days ago, # ^ | ← Rev. 2 →   +4 You can find contribution of each subarray.Let us focus on some subarray $s$. There exists a mask $m$ for $s$ such that $s$ will contribute to the answer iif mask of query is supermask of $m$.$m$ gets fixed because we have the restriction that if $s[l] != ?$ and $s[r]=?$, $s[r]=s[l]$ ($r=|s|-l+1$).Now for subarray $s$ to contribute $1$ to the answer, some $?$ get fixed and rest $?$ are flexible. Suppose we have $freq$ flexible $?$. Finally $s$ will be contribute $1$ to answer in $|t|^{freq}$ arrays.
•  » » » 2 days ago, # ^ | ← Rev. 2 →   0 There are $2^{17}$ masks, and len $|t|$ is up to 17, and also we need to sum up all summasks foreach mask.All my tries did run like more than a minute...how to do that right?
•  » » » » 2 days ago, # ^ | ← Rev. 2 →   +7 Say mask of query is $q$. Now you need to check contribution of all masks $m$ such that $q&m=m$. You can traverse over all submasks in $O(3^x)$ operations(here $x=17$). Suppose we have a $dp$ array, such that mask $x$ will contribute $dp[x][i]$ to the answer, if $q&x=x$ and $__builtin_popcount(q)=i$. So you calculate this $dp$ while traversing all subarrays(fixing middle position and moving sideways).You can precompute answer for all masks.My submission
•  » » » » » 2 days ago, # ^ |   0 oh thanks! I forgot about this trick to iterate over submasks
•  » » » » » 2 days ago, # ^ |   +3 actually you can solve it in $O(2^{17}\times 17^2)$ by using SOS dp or fast walsh transform.The solution is similar to yours.My submission
 » 2 days ago, # | ← Rev. 2 →   0 Why Segment tree solution is giving TLE in C. :( code#include using namespace std; long long int st1[2000005]; long long int arr1[100005]; long long int st2[2000005]; long long int arr2[100005]; void build1( long long int node, long long int start, long long int end) { if(start == end) { st1[node] = arr1[start]; return; } long long int mid = start + ((end-start)/2); build1(2*node+1, start, mid); build1(2*node+2, mid+1, end); st1[node] = st1[2*node+1] + st1[2*node+2]; } void update1( long long int node, long long int start, long long int end, long long int k, long long int u) { if(start == end) { st1[node] = u; arr1[k] = u; return; } long long int mid = start + ((end-start)/2); if(start <= k && k <= mid) { update1(2*node+1, start, mid, k, u); } else update1(2*node+2, mid+1, end, k, u); st1[node] = st1[2*node+1] + st1[2*node+2]; } long long int query1( long long int node, long long int start, long long int end, long long int l, long long int r) { if(start >= l && r >= end) return st1[node]; else if((r < start) || (l > end)) return 0; else { long long int mid = start + ((end-start)/2); long long int p1 = query1(2*node+1, start, mid, l, r); long long int p2 = query1(2*node+2, mid+1, end, l, r); return (p1+p2); } } void build2( long long int node, long long int start, long long int end) { if(start == end) { st2[node] = arr2[start]; return; } long long int mid = start + ((end-start)/2); build2(2*node+1, start, mid); build2(2*node+2, mid+1, end); st2[node] = st2[2*node+1] + st2[2*node+2]; } void update2( long long int node, long long int start, long long int end, long long int k, long long int u) { if(start == end) { st2[node] = u; arr2[k] = u; return; } long long int mid = start + ((end-start)/2); if(start <= k && k <= mid) { update2(2*node+1, start, mid, k, u); } else update2(2*node+2, mid+1, end, k, u); st2[node] = st2[2*node+1] + st2[2*node+2]; } long long int query2( long long int node, long long int start, long long int end, long long int l, long long int r) { if(start >= l && r >= end) return st2[node]; else if((r < start) || (l > end)) return 0; else { long long int mid = start + ((end-start)/2); long long int p1 = query2(2*node+1, start, mid, l, r); long long int p2 = query2(2*node+2, mid+1, end, l, r); return (p1+p2); } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // think twice long long int n, q; cin >> n >> q; build1(1, 1, n); build2(1, 1, n); // for(long long int i = 1; i <= n; i++) // { // arr1[i] = 0; // arr2[i] = 0; // } while(q--) { long long int t; cin >> t; if(t == 1) { long long int x, y; cin >> x >> y; update1(1, 1, n, x, 1); update2(1, 1, n, y, 1); } else if(t == 2) { long long int x, y; cin >> x >> y; update1(1, 1, n, x, 0); update2(1, 1, n, y, 0); } else { long long int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; if((x2-x1+1) == query1(1, 1, n, x1, x2) || (y2-y1+1) == query2(1, 1, n, y1, y2)) printf("Yes\n"); else printf("No\n"); } } return 0; } 
•  » » 2 days ago, # ^ |   +5 Segment tree has a much bigger constant than Fenwick tree
•  » » » 2 days ago, # ^ |   +1
•  » » 2 days ago, # ^ |   +1 maybe you can use int instead of long longand use scanf/printf instead of cin/cout
•  » » 2 days ago, # ^ | ← Rev. 2 →   0 My binary index tree TLEed with bare cin/cout while it passed when I unsynchronized iostream with stdio, so maybe it's io's fault
•  » » 2 days ago, # ^ |   +3 You’ve made the ST too big. Much bigger than required.
•  » » » 2 days ago, # ^ |   0 Still got TLE. The array size should be 1e5. And st size should be 4e5. Am I right?
•  » » 2 days ago, # ^ |   0 you don't have cin.tie(0)->sync_with_stdio(0); 
•  » » 2 days ago, # ^ |   0 you shouldn't use 'build' initially all values ​​are 0
•  » » 44 hours ago, # ^ |   0 Why do you use long longs?
 » 2 days ago, # |   +1 Used a single loop in Problem-B, still exceeded the time limit, is it me or python at fault here?
•  » » 2 days ago, # ^ |   +3 sum() uses loop internally
 » 2 days ago, # | ← Rev. 2 →   +33 Thanks to iura for setting F! I really enjoyed solving it during testing. Here is my alternate solution to F that works for much larger constraints.Let $S_i$ be sets containing all representatives of all arrays $a$ of size $i$ and $C_i$ be the set of cliques of size $i$. When we talk about clique, we are talking about cliques on the graph where we draw the edges as $(u_i,v_i)$. Also when we talk about arrays, we will basically refer to its equivalence class, so treat $a$ as the representative.Take some array $a$ and let $s_a$ be the possible values of the first element of $a$ after some operations. Note that it is necessary that $s_a$ is a clique because otherwise, we are not able to swap all values in $s_a$ to the start of $a$.Let us suppose that we know $S_j$ for all $j0\end{cases}$.We can find all $|C_j|$ in $O(2^d)$ by brute force. To do this, we check if some mask $bm$ is a clique in $O(1)$ by taking an arbitrary bit $b$ from $bm$, checking if $bm \oplus b$ is a clique and that $b$ is connected to everything in $bm \oplus b$. Since we can solve linear recurrence in $O(d \log d \log n)$, we have total complexity of $O(2^d+d \log d \log n)$ but it probably does not matter what algorithm we use to solve the linear recurrence since there is no way it is going to dwarf the $2^d$ term.Can we find all terms of $|C_j|$ faster than $O(2^d)$?Code: 157227780
 » 2 days ago, # |   -16 segment tree forces
•  » » 2 days ago, # ^ |   +2 Which tasks required segment trees? I only looked at A, B, C and D and none of them required it (or anything similar like Fenwick)
•  » » » 2 days ago, # ^ |   +5 B and C were doable using segment trees
•  » » » » 2 days ago, # ^ |   0 My solution to C tle'd using Fenwick tree any suggestions ?
•  » » » » » 2 days ago, # ^ |   0 ++ I used segment tree my solution got tle'd too. I don't know where did I go wrong . :(
•  » » » » » » 2 days ago, # ^ |   0 You should use int instead of long long whenever you can. Also it'll be good to use the fast I/O: cin.tie(nullptr); ios::sync_with_stdio(false); Finally if it doesn't work, use a fenwick tree as it's constant factor is way better than a segment tree's
•  » » » » » 2 days ago, # ^ |   0 You can refer my submission: 157174605
•  » » » » » » 2 days ago, # ^ |   0 Hey winterfire can you check my submission and let me know what you think ? submission
•  » » » » » » » 2 days ago, # ^ |   +1 This solution would get WA even if it didn't TLE. Despite that, you need to use fast I/O. Try adding this:ios_base::sync_with_stdio(false); cin.tie(0);
•  » » » » » » » » 2 days ago, # ^ | ← Rev. 2 →   0 Oh lord thanks Restricted I am using this template from a long time never noticed fast i/o wasn't included that's why I was wondering my submission for B took 1.5 sec but is just simple operations..
•  » » » » » » » » » 2 days ago, # ^ |   0 Happens to the best of us :)
•  » » » » » » » 2 days ago, # ^ | ← Rev. 3 →   0 I don't know about TLE but why you are modifying the FT every time?let's say n number of rooks covering for the ith row! then you don't need to modify FT with -1 unless all the n rooks targeting that ith row are removed! In the same way, you need to modify FT with +1 only when no other rook was targeting that row previously.And lastly, your type3 query should also be corrected accordingly otherwise WA (as stated by Restricted)
•  » » » » » 2 days ago, # ^ |   +8 I did it using segment trees. Create two seg trees for handling rows and cols. If a rook is placed/removed at cell x, y then update the xth row and yth col. For query of type 3, if the bitwise AND of rows x1 to x2 > 0 or cols y1 to y2 > 0 then answer exists.
•  » » » » » 2 days ago, # ^ |   0 Mine passed in 290ms 157157585I'll try to see why your sol TLE'd
•  » » » » » 2 days ago, # ^ |   +1 your solution is wrongConsider a case with a 5x5 grid RRRR. R.... ..... ..... ..... If I query on the whole grid, the answer should be No but your code will output Yes because you shouldn't add 1 everytime you place a rook. See my explanations here for more details:
•  » » » » » » 2 days ago, # ^ |   0 Thanks bestial I got it its wrong , I think TLE is because of fast i/o but if you see any other issue with BIT implementation let me know
•  » » » » » » » 2 days ago, # ^ |   0 It seems ok but for more safety I would add ++index b efore computing any answer for queries (this is because the bit trick you use doesn't work for 0). Adding the ++index would allow you to use the BIT like it's 0-indexed if you want. You only need to make sure that you allocate extra memory but you already did that :)
•  » » » » 2 days ago, # ^ |   0 yes ofc you can use segment trees as arrays
•  » » » » 2 days ago, # ^ | ← Rev. 2 →   0 however actually B can be solved in $O(n+q)$ without using segment tree
•  » » » 2 days ago, # ^ |   0 Maybe B and C.
 » 2 days ago, # |   +6 n = 2 should have been in the samples in A :( Btw, I wonder how many people solved B using segment tree
•  » » 2 days ago, # ^ |   +3 I use segment tree with lazy propagation.
•  » » » 2 days ago, # ^ | ← Rev. 3 →   0 You can do it in an easier way.You want to perform three types of queries set all the elements to x change the value of an element compute the sum of the array If you don't have the "set all the elements to x" queries, you can just compute the sum at the beginning and when you change the value of an element you know how the sum will change.The only problem is that if you performed a "set all the elements" query, the value of the element might not be the one you stored in the array.To handle this, notice that the latest query will give the value of the element.So you just keep track of the time when the set query was applied and when the change query of each element was applied.Code: 157146130
•  » » » » 2 days ago, # ^ |   0 There is an easier way. Just store all changed indices since query 2 and clear them after query 2. https://codeforces.com/contest/1679/submission/157150450
•  » » » » » 2 days ago, # ^ |   0 If there are a lot of queries of type 2, wont this get TLEd as you would be clearing the set each time?
•  » » » » » » 2 days ago, # ^ |   0 but then you are going to clear a set of small size.
•  » » » » » » » 2 days ago, # ^ |   0 Ohhh I see
•  » » » » » » 2 days ago, # ^ |   0 At most for any query 1 you will perform it twice, once while adding it and once while clearing it. So this is still O(q)
•  » » » » 2 days ago, # ^ |   0 157185820 I have almost done the same, but i guess missed some edge cases. Could you point out what is wrong, please?
•  » » » » » 2 days ago, # ^ |   0 use long long.
•  » » » » » » 2 days ago, # ^ | ← Rev. 2 →   0 Thank you for clarify!
•  » » » 2 days ago, # ^ |   +3 Overkill. Could be easily solved in O(n + q) via storing the last occurrence of updating the whole array and the last occurrence of updating an index for each index.
 » 2 days ago, # |   +7 I tried to hack C with 2e5 queries and it said input cannot exceed 256kB, what T_T
•  » » 2 days ago, # ^ |   +4 You can use a data generator.
•  » » » 2 days ago, # ^ |   0 Will learn how to use that before the next contest, till then pain
•  » » » » 2 days ago, # ^ |   +1 Hacking with a generator is quite simple. Just output the test case you want. For example, a test generator for B#include using namespace std; signed main() { ios::sync_with_stdio(0); cin.tie(0); int n = 20, q = 20; cout << n << ' ' << q << '\n'; for (int i = 0; i < n; i++) { cout << "123456"; if (i+1 == n) cout << '\n'; else cout << " "; } for (int i = 0; i < q; i++) { if (i % 2) cout << "2 9999\n"; else cout << "1 2 3\n"; } return 0; } Some things to note are: Don't output any extra spaces or blank lines (e.g. after arrays), and the test case should always end with an endl character (e.g. cout << n << '\n'; instead of just cout << n;). Basically you should follow test standard practices strictly.
•  » » » » » 2 days ago, # ^ |   0 it was helpful,thanks a lot ;)
 » 2 days ago, # | ← Rev. 2 →   0 how to solve c ? some one pls tell me your approach :* (i've tried to do it with brute force by making maps in the last 10 min I was knowing that it gonna get me tle :D ) so how can we solve it:*
•  » » 2 days ago, # ^ |   0 If you have at least one rock in a row set the row's value to 1. If you you have at least one rock in a column set the column's value to one. Now you wanna know if the sum of the columns in [x1,x2] is exatly x2-x1+1 or if the sum of the rows in [y1,y2] is exactly y2-y1+1. This can be easily done with a segment tree
•  » » » 2 days ago, # ^ |   0 hey bro just need a favor from you basically you are a specialist you might be having a good idea about cp so can you tell me after seeing my profile and rating that should I learn segment tree or not cause some of my seniors were saying to me that to learn segment tree your rating should be at least 1500 or something but from last few contest I'm seeing that there is one question of segment tree between a,b,c and you might remember that div4 contest which just held few days ago in it also h2 problem was solved using segment tree so can u suggest me,that when should I learn about it or i should wait for few months :*
•  » » » » 2 days ago, # ^ |   0 I don't see why not. It's not that hard of a concept and it makes you understand some other CP concepts better. At least know what it does and how to use it.
•  » » » » 2 days ago, # ^ |   0 You should learn to use ordered set. Today's C and div4's H2 could be easily done with ordered set.
•  » » » » » 2 days ago, # ^ | ← Rev. 2 →   0 but in java there is nothing as ordered set:* can u suggest any alternative:D
•  » » » » » » 34 hours ago, # ^ |   0 I don't think there is any alternative in java. You have to use fenwick or segment trees.
•  » » 2 days ago, # ^ | ← Rev. 2 →   0 Think of a way to maintain the empty rows/cols, after that when they ask you to check the subrectangle try to find if there is a row and a col that is empty and satisfy this condition: x1 <= row <= x2 && y1 <= col <= y2, if you found such a row and a column then the answer is no otherwise the answer is yes
•  » » » 2 days ago, # ^ |   +3 I solved it using sets and binary search
•  » » » » 2 days ago, # ^ | ← Rev. 2 →   0 but how who can we find it with bs:* can u elaborate
•  » » » » » 2 days ago, # ^ |   +2 Here's my solution https://codeforces.com/contest/1679/submission/157198959The idea is to keep track of the empty rows and empty cols, initially everything is empty so we will insert into our rows and cols the numbers from 1 to n;Rows = [1,2,3,...n] Cols = [1,2,3,...n]Now anytime we insert a rock to some (r,c) that means the row is no longer empty and the col is no longer empty, so we will remove r from our Rows set and c from our Cols set.Now, how can we know that this row/col is empty? we can keep track of the rocks count in each row and col, once the count for a row/col becomes 0, this means we need to insert it into the corresponding set.Take a look at my solution, and hopefully, you will understand what I mean.
•  » » » » » » 2 days ago, # ^ |   0 I tried something like that but there was something wrong and it TLEd on somewhere near the 40th case.
•  » » » » » » » 2 days ago, # ^ |   0 I got TLE first and then used fast I/O and it worked
•  » » » » 2 days ago, # ^ |   0 I used Ordered Set to solve C.
•  » » 2 days ago, # ^ | ← Rev. 3 →   0 When a rook is inserted on (r, c) notice that it covers all cells on row r and col cLet's store for each row if it's already covered by a rook Do the same for columnsNow the subrectangle queries ask if for each cell, either their row or their col is coveredA subrectangle query consider a range of rows and colsWhat happens if a column is not covered ? Basically you need all the rows to be covered for the cells of this column to be covered(same argument in reverse)This way we show that the answer is "Yes" iff all the rows or all the cols are coveredLet's say we put a 1 when a row is coveredWe just need to range sum over the range of rows and make sure the sum is equal to the length of the rangeSame for colsTo handle rooks removal, we count for each row the number of rooks covering itWhen this count reaches 1, we add one in our segtree/bitWhen it reaches 0, we add -1Code: 157157585
 » 2 days ago, # |   0 How to solve D? My idea is to go through the nodes in increasing order and activate them one by one. Once I activate them I want to know if a strongly connected compononeted is activated, this means that I am done regardless of what K is. This is easy to do. The hard part was knowing whether a path that is K long in is created. How do you do it?
•  » » 2 days ago, # ^ | ← Rev. 2 →   +43 The idea for D is fairly simple (and a good learning exercise if you aren't familiar with the "trick"). You just need to combine 3 independent pieces: Binary Search on answer, Cycle detection and Longest path in DAG.Since we are asked to minimize the maximum value of some quantity, it's natural to think in terms of binary search. However, this can be a trap if the function is not monotonic. To work around it, a clever way to define the predicate is to use the at least keyword. Instead of asking whether an answer with value val exists, we ask Does an answer with value at least val exists? With this keyword, it's fairly obvious that existence of at least val implies the existence of at least all value less than val as well.To verify a predicate, you can ignore all vertices with value > val while performing a DFS. (You might've seen this in problems asking you to find the maximum value less than threshold on a path between 2 vertices in a tree). After ignoring these vertices, if the resulting graph contains a cycle, it means you can travel it infinitely many times. If not, it is a DAG. Then, you just need to find the longest path on this DAG and verify if it's at least $k - 1$.Note that you can do all of this in a single DFS (and without explicitly creating the new graph).Code
•  » » » 2 days ago, # ^ |   +6 Of course you do binary search how did I miss it. Eeh, I feel so dumb haha. Thanks a lot!
•  » » » » 2 days ago, # ^ |   +6 You don't need to feel dumb, it happens not to be able to solve a problem!What you should learn from this is that problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)You can find some similar problems on usaco guide: Wormhole SortMooTube
•  » » » » » 2 days ago, # ^ |   +1 That's so nice of you to say thank you! I will definitely be checking the problems you suggested later.
•  » » » 2 days ago, # ^ |   0 Nice explanation. You made it look so simple. Thanks.
•  » » » 2 days ago, # ^ |   +3 damn I only knew binary search
•  » » » 2 days ago, # ^ |   0 Amazing idea!!!
•  » » » 45 hours ago, # ^ |   0 thanks a lot
•  » » 2 days ago, # ^ |   0 Binary search for the answer. And for each check, we could search for cycle or a longest chain in the new DAG, which we needn't really create a new graph but just judge the number on each vertex
•  » » 2 days ago, # ^ |   0 What exactly D asks for?
•  » » » 2 days ago, # ^ |   +4 Given a directed graph, find paths such that there are K vertices in it. Choose a path such that the maximum value of the vertex is the minimum possible. Output this value.
•  » » 2 days ago, # ^ | ← Rev. 2 →   +13 We can use binary search to find the answer.When we are checking if there exists a path of length k with nodes whose values are less than or equal to 'x'(current binary search value), we consider the subgraph 'C' formed by the nodes whose values are less than or equal to 'x'. Now we have two cases. 1. There is a cycle in this subgraph C, the answer is true for this x in this case. 2. There is no cycle => subgraph is a DAG. Find max path length using DP and check if the max path length is >= k. The answer is true for this x if that is the case.Steps 1, 2 are of O(n) complexity each. We do them for a total of O(log(max(a[i]))). Therefore total complexity is O(n*log(max(a[i]))). code.
•  » » » 2 days ago, # ^ |   +3 Unfortunately Got TLE on pretest 10 using the same approach
 » 2 days ago, # |   0 What was the approach for problem A ?
•  » » 2 days ago, # ^ |   0 The max number of cars is calcualted using the maximum number of 4 wheel cars. The min number of cars is calculated using the maximum number of 6 wheel cars. We need to consider some edgecases, like odd numbers.
 » 2 days ago, # |   -8 E was nice construction problem, I like it. But whole contest was spoiled by unclear problem statements, except A there was not a single one I clearly understood. Had to decipher and guess the meaning of all texts, annoying.
•  » » 2 days ago, # ^ |   +4 isn't E Spoilerbitmask dp?
•  » » » 2 days ago, # ^ | ← Rev. 2 →   0 SpoilerYes, it's SOS DP
 » 2 days ago, # | ← Rev. 2 →   -13 me about to solve A in 6 mins.1st error (Not considering the edge case of n == 2) be like: "I will make you pay"2nd error (forgetting to return after printing -1) be like: "LMAO NOOB"And that's how 'A' ruined my LIFE :)
•  » » 2 days ago, # ^ |   0 me too :( let's be more patient
•  » » » 2 days ago, # ^ |   0 yea :p
 » 2 days ago, # |   +1 Can anyone tell me why do i get TL in B
•  » » 2 days ago, # ^ |   0 I guess tot = b[1] * n is $O(n)$
•  » » » 2 days ago, # ^ |   +1 It is just a multiplication of two integers.
•  » » » » 2 days ago, # ^ | ← Rev. 2 →   0 Sorry for the previous nonsense reply, I just read too fast and thought you were creating a list. I got your code accepted by reading the whole input at the start.
•  » » » » » 2 days ago, # ^ |   0 Great. Is it fine though, that such optimizations are needed for code to be accepted. Or it is a problem of a contest?
•  » » » » » » 2 days ago, # ^ |   0 I agree this should not be needed. But I had a look at some of the accepted Python solutions and it seems they write at the start input = sys.stdin.readline which I guess is way faster. Using that your code also gets accepted, so you should write that and keep reading input as you did, which is not a big deal.
•  » » 2 days ago, # ^ | ← Rev. 2 →   0 Yeah this is frustrating. It's only a single linear loop. https://codeforces.com/contest/1679/submission/157146581I also tried the standard Python 3, it just barely passes the pretest but of course it is TLE again on the system test
 » 2 days ago, # |   0 thanks for the early end round,that i could see RNG's exciting game:(
 » 2 days ago, # |   +12 This was a super cool round with nice algorithmic problems ! Congrats to the authors :DHere is my advice about each problem AI think it's ok as a div2 A, I don't have much advice about wether a div2 A should require a little bit of maths or not BThis is a really cute problem if you try to solve it in linear. Sadly it can be bashed with a lazy segtree which makes the problem solvable by template copy paste. I don't know if it's possible to make a lazy segtree TLE without hurting the linear solutions AC rate... CNice problem, I think that it's the perfect difficulty for a div2 C. DNice problem too. It might be a little bit standard though but as long as it's not copy paste I think it's fine.I didn't solve E/F so I don't really have an advice but they both look interesting
•  » » 2 days ago, # ^ |   0 how to solve d?
•  » » » 47 hours ago, # ^ |   0 Problems asking to minimize the maximum (or maximize the minimum) can be solved with binary search in 99% of the cases because fixing the max/min gives you a smaller structure where you have complete freedom (for example in this problem, you don't have to care anymore about whether you move on a too big node)So let's binary search over the maximum node you will walk on (I don't explain why you can binary search here but you can try to prove it as an exercise)Now we need to check if it's possible to find a path of length k (in terms of nodes) using only nodes with value <= MXLet's build a new graph. It'll be the same graph as the original one but only with nodes having value <= MX. We now want to find a path of length at least k. Notice that if the graph has a cycle, we can just keep moving in the cycle and get a path of length at least k. If the graph doesn't have any cycle, it's a directed acyclic graph and you can use dp to compute the longest path in it.Code: 157170838
 » 2 days ago, # |   +11 Since I am poor in English, can anyone explain what is the difference between loops and cycles? Why "loop" is equal to "self-loop" instead of "cycle" in D?
•  » » 2 days ago, # ^ |   0 I didn't solve it but I tried solving it by considering a "loop" to be equivalent to a "cycle". Is it not the case?
•  » » » 2 days ago, # ^ |   0 loop is an edge which starts in vertex v and leads to vertex v too, in other words, loop is a cycle which contains single vertex
•  » » » 2 days ago, # ^ |   0 In the author's opinion, probably, "loop" is equivalent to "self-loop", or you can't even pass sample tests.
•  » » 2 days ago, # ^ |   0 The common wording at least on codeforces is that a loop is a self-loop, a edge that starts and end at same vertex, so a cycle of length 1.And a cycle is a circular path containing more than one vertex.
•  » » » 2 days ago, # ^ |   0 Thanks.
•  » » 2 days ago, # ^ | ← Rev. 3 →   +7 (https://en.wikipedia.org/wiki/Loop_(graph_theory))(https://en.wikipedia.org/wiki/Cycle_(graph_theory))just check out these links, it's not codeforces-related terms but common ones
 » 2 days ago, # |   0 Can anyone please explain a solution for Problem B? (without using segment trees)
•  » » 2 days ago, # ^ |   +5 Yes! You can read about it right here
•  » » » 2 days ago, # ^ |   0 Thanks a lot!
•  » » 2 days ago, # ^ |   0 hint: keep timestamp of modifing for each item
•  » » 2 days ago, # ^ |   0 Notice that if operation of type 2 is never carried out, then the sum would only change by x — arr[i]. Also set arr[i] = x.If the operation of type 2 is carried out, sum for that round will be n*x. Set a boolean flag for all subsequent operations of type 1 will change.After even a single operation of type 2, maintain a map that tracks the most recent entry value of the indices. Note that we don't need to track the unmodified indices, as they will be x only (where x represents most recent value of type 2 operation)Lastly on every occurrence of type 2 operation, make sure that this map is cleared out.
•  » » 2 days ago, # ^ |   0 Someone really wrote seg tree there?)
•  » » » 2 days ago, # ^ |   +2 Me who can't be bothered to think of a linear solution... I'm a simple man, I find any passable solution, I type it up
•  » » 2 days ago, # ^ |   0 Store the initial sum in s.No need to store the array.Maintain a map instead of all the type1 changes made to the array after the recent type2 operation.Maintain a variable l initialized to 0, to store the x value of the last type2 operation.So everytime you get a "1 i x" just look into the map if some change was registered at pos i by "m.count(i)", if it's not zero then update s as s+=x-m[i], else if no change was registered the cell contains the last type2 change hence s+=x-l.Now when you encounter type2 operation clear the map and update the variable l to the new x and the sum s to n*l. Link to my not so legible code
 » 2 days ago, # |   0 The contest was very nice but the pretest cases for problem C were not strong enough and any simple brute-force (TLE) solution will pass it. Let's imagine there is a cheater who created a fake account and joined the contest and then he wrote a simple brute-force solution for it and then he lock his solution and read the solutions of others to submit it from his real account.
 » 2 days ago, # | ← Rev. 3 →   0 Can someone please explain why I am getting TLE in C? https://codeforces.com/contest/1679/submission/157197783 I am using hashing to figure out when to add/delete row/column in sortedset(made using Fenwick Tree). And to find out if the whole sub-rectangle is there, I just subtract indexes with lower_bounds of x1,x2 in row sortedset and y1,y2 in column sortedset and compare it with difference of x1,x2 and y1,y2. It should be O(nlogn) but sadly it's giving TLE:(
 » 2 days ago, # |   +1 Testcase 41 is on fire
•  » » 2 days ago, # ^ |   +1 it got me too :(
•  » » » 2 days ago, # ^ |   +1 Mine just pass..
 » 2 days ago, # |   +1 so many fst on problem C and D..
 » 2 days ago, # |   +4 Several stupid mistakes on A and D led to the terrible penality and the rapid descent of rank.
 » 2 days ago, # |   +6 https://codeforces.com/contest/1679/submission/157173493Just added comment. LOL Will report more cheaters out there.Sorry for bad english
•  » » 2 days ago, # ^ |   0 I really don't know what these cheaters will gain from this sh!t. I think it will be better to ban any cheater forever.here is an example
 » 2 days ago, # |   +3 Sad to get FST on E :( (my solution isn't the best solution so it got TLE on test 10.)
 » 2 days ago, # | ← Rev. 2 →   0 .
 » 2 days ago, # |   0 Problem ECan any one explain why in input2 ?? 1 ab10 palindrome substring(a, b, aa, bb, a, b which other?)
 » 2 days ago, # |   +87 To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!
•  » » 2 days ago, # ^ |   0 Thank you very much
•  » » 2 days ago, # ^ |   -9 You talked about cheaters, do they exist in cf?
 » 2 days ago, # |   0 Can anyone tell me what's wrong with my code for Problem C. I was expecting a TLE but got a WA on the 27284th token!It's in Go, but easy to understand. Uses 2 bool arrays for x and y and just loops over x1->x2 && y1->y2. https://codeforces.com/contest/1679/submission/157188079
•  » » 2 days ago, # ^ | ← Rev. 2 →   0 If I add two rooks on same row and then remove one of them, in that case your code is considering that there is no rook on that row. Because of this mx[x] = false my[y] = false You should store frequency of rooks on particular row and col to resolve this
•  » » » 2 days ago, # ^ |   0 Thanks, I feel so dumb. These start times are killer for NA users.
 » 2 days ago, # |   0 Can anyone tell what's wrong with my submission? Passed the pretests but failed on Test 10. https://codeforces.com/contest/1679/submission/157152675
•  » » 2 days ago, # ^ | ← Rev. 3 →   +1 This test case will fail in your code: 5 3 1 2 3 4 5 2 1 1 5 2 1 4 1 
•  » » » 2 days ago, # ^ |   0 Silly mistake! Got it Thanks.
 » 2 days ago, # |   +1 write x
 » 2 days ago, # | ← Rev. 3 →   0 Can anyone tell me what's wrong with my submission? Passed the pretests but failed Test 22.My Code...
•  » » 2 days ago, # ^ |   0 Just insert one more element = n in your sets.
•  » » » 2 days ago, # ^ |   0 Thank you
 » 2 days ago, # |   +14 Problem b guarantees 1≤ai≤109 but why 0 appears in test6
 » 2 days ago, # |   0 where can i get the editorial of this contest??
•  » » 2 days ago, # ^ |   0 It will be published soon.
 » 2 days ago, # |   +5 Can anyone tell me why I got runtime error? my submissions
•  » » 2 days ago, # ^ |   0 template struct Fenwick { const int n; std::vector a; Fenwick(int n) : n(n), a(n) {} void add(int x, T v) { for (int i = x; i <= n; i += i & -i) { a[i] += v; } } T sum(int x) { if(x <= 0)return 0; T ans = 0; for (int i = x; i > 0; i -= i & -i) { ans += a[i]; } return ans; } T rangeSum(int l, int r) { return sum(r) - sum(l); } }; your code get an out of bound error when i == n (a[n] will out of bound).you should let your vector resize to n + 1.
•  » » » 2 days ago, # ^ |   0 but I declare the structure Fenwick x(n + 1), y(n + 1) way.
•  » » » » 2 days ago, # ^ |   0 In your Fenwick n = n + 1 at the same time. for (int i = x; i <= n; i += i & -i) { a[i] += v; } In this for loop, the n is 1 larger than the n your input. So a[n] will out of bound even if you declare the structure Fenwick x(n + 1000), y(n + 1000).
•  » » » » » 2 days ago, # ^ |   0 yeah, I understand Thank you so much.
•  » » » 2 days ago, # ^ |   0 ok, got it, Thank you
•  » » » 34 hours ago, # ^ | ← Rev. 2 →   0 i also got runtime, when i initialize with n+1 i get RE when initialize with n+2 it passes and when i initialize with n+3 it again gives RE. i couldnt understand why edit: it gets accepted in c++20
 » 2 days ago, # |   0 Can anyone please find a test case where this code (157177615) fails. I have tried to come up with a failing test case but have had no success.
•  » » 2 days ago, # ^ |   +1 Failing testcase: Ticket 7141
 » 2 days ago, # |   +1 Why the system is testing again ?
 » 2 days ago, # |   0 What happened, why is task B being retested?
 » 2 days ago, # |   +10 Thx the contest.Become Master at last!
 » 2 days ago, # |   +1 who else had a rounding error in problem A haha
•  » » 2 days ago, # ^ |   0 me :)
•  » » » 2 days ago, # ^ |   0 it's a pity that you went into the negative, I hope that your rating will grow soon, or rather in the next DIV
 » 2 days ago, # |   0 Thanks for the Problems . It was a pretty balanced round
 » 2 days ago, # |   -19 我小号第一次进前一千！！！
 » 2 days ago, # |   0 Can someone see my solution for C I find nothing time consuming here. Can any minor changes make it acceptable.
•  » » 2 days ago, # ^ |   0 Aren't you iterating over rows and columns for each query though?
•  » » 2 days ago, # ^ |   0 I mean you have those two loops in your code: for i in range (q): for i in range (a[1], a[3]+1): 
•  » » » 2 days ago, # ^ |   0 Thank you! Can you also please suggest other efficient ways to do it with same logic(like checking if all any one of columns or rows are filled) if possible. Or is there any other logic for this
•  » » » » 2 days ago, # ^ |   0 fenwick tree or segment tree to check sum or minimum in the range.
•  » » » » 2 days ago, # ^ |   0 I've done this problem the same way as you (logic wise). You can look at my submission.However, I used C++'s set and its 'lower_bound' function. I guess you can find something similar in python :)Maybe there is even some simpler way to solve it but I can't think of anything.
 » 2 days ago, # |   0 I am getting WA on test 2 but I can not find what is mistake. Please someone check it . https://codeforces.com/contest/1679/my
 » 2 days ago, # |   0 can someone tell me how to solve D plz
•  » » 2 days ago, # ^ | ← Rev. 2 →   0 Binary search the answer, then you need to judge if there is a cycle or a path with a length of at least k containing vertices with number <= answer. You can do toposort or dfs. My submission
 » 2 days ago, # |   0 I'm screwed!How to be better ?
 » 2 days ago, # |   0 Imao the limit on C has been too tight. Whether solution is accepted or not is up to constants and the judging machine. These two submits differ only in a tab (begining of main), however only one gets ACC: 157217055 157214568(Played with it after the round so there might be some diffrence but the point remains anyway.)
•  » » 2 days ago, # ^ |   +3 you are returning a string level by level in segment tree, which could be much slower. Change it to an enum and it will finish in ~300ms.
•  » » » 2 days ago, # ^ |   0 Thx a lot.
 » 2 days ago, # |   0 Can someone please help me figure out what went wrong with my solution on problem C?What i was doing is: - store how many free rows/cols we have upto a certain row lets say r and c (using 2 BITs) when u place a rook at row r and col c, u reduce the number of free rows and cols at row r and c when u remove a rook u add 1 free row/col to check if all rows and cols in a certain range are under attack by a rook simply check if there are 0 free rows or columns in that range
•  » » 2 days ago, # ^ |   0 You need to consider the case where two rokes are in one row. After removing one of them the other one is still on that row.
•  » » » 2 days ago, # ^ |   0 Got it thanks, realised the flaw in my approach now
•  » » 2 days ago, # ^ |   0 How to check if all rows and column in that submatrix is attacking by rook in log(n) time,beacuse it will take o(n) time
•  » » » 38 hours ago, # ^ |   0 You can keep track of how many free rows and cols are there in a certain range using BIT or Segment Tree (search operation logN). To handle the edge case of rook being placed in same row/col multiple times, I used a map to store number of rooks in a row and col. Then I only update the BIT when there are either 0 rooks in a row/col (means the row is free) or 1 rook (any more than this won't make the row unoccupied so only update it once).Here's my submission
 » 2 days ago, # |   0 Thank you for problem B, it was tougher than regular div 2 B problems ( according to me ), took me 30mins to think.THANKS A LOT
 » 2 days ago, # |   0 public class C { public static void main(String[] args) { FastReader sc = new FastReader(); int t = 1; while(t-- >0) { int n = sc.nextInt(); int q = sc.nextInt(); boolean rows[] = new boolean[n]; boolean cols[] = new boolean[n]; outer:while(q-->0) { int type = sc.nextInt(); if(type==1) { int x = sc.nextInt()-1; int y = sc.nextInt()-1; rows[x] = true; cols[y] = true; } else if(type==2) { int x = sc.nextInt()-1; int y = sc.nextInt()-1; rows[x] = false; cols[y] = false; } else { int x1 = sc.nextInt()-1; int y1 = sc.nextInt()-1; int x2 = sc.nextInt()-1; int y2 = sc.nextInt()-1; boolean done = true; for(int i=x1;i<=x2;i++) { if(!rows[i]) { done = false; break; } } if(done) { System.out.println("Yes"); continue outer; } done = true; for(int j=y1;j<=y2;j++) { if(!cols[j]) { done = false; break; } } if(done) { System.out.println("Yes"); continue outer; } System.out.println("No"); } } } } // Can anyone help me figure out the test case, where this solution would fail?
•  » » 2 days ago, # ^ |   +3 Put it in spoiler and don't spam?
 » 2 days ago, # |   0 Can someone tell me why my solution of Problem C is giving WA on Test Case 3?
•  » » 2 days ago, # ^ | ← Rev. 2 →   0 And even if it passed test case 3 it will get TLE for sure! Your solution is O(n^2) and the constraint is 2*10^5 Make sure to learn the Fenwick tree first to solve this problem
•  » » » 2 days ago, # ^ |   0 It can be solved with c++ set
•  » » » » 2 days ago, # ^ |   0 Please explain this solution in c++ set.
•  » » » » » 2 days ago, # ^ |   +1 For rows:store in set every value that is not covered by any rook.initially this set is obv full.to know whether there exists a row between x1 and x2 that is not covered you make use of set.lower_bound()if lower_bound(x1) is set.end() or its value is > x2 then all cells between x1 and x2 must be coveredsame for columns
•  » » » » » » 2 days ago, # ^ | ← Rev. 3 →   0 Nice Idea Thanks a lot. They should put this in the Tutorial Beside the Fenwick tree.
•  » » » 2 days ago, # ^ |   0 perhaps it can be solved using ordered set.
 » 2 days ago, # |   +3 For some reason I couldn't come up with using segment tree for C, instead I used a complicated data structure that contains every consecutive segments. I believe it is useful for some specific problems, but it was an overkill for this problem. It is implemented with a set> where each pair represents the endpoints of each segment. Each operation is implemented in these ways: To insert a new element x, check if there is a segment that contains x-1 and x+1, respectively. If a segment [l, x-1] exists, remove it and insert [l, x]. If a segment [x+1, r] exists, remove it and insert [x, r]. If both exist, remove both and insert [l, r]. If none of them exist, just insert [x, x] To remove an element x, search for a segment [l, r] that contains x. Remove this segment, and insert [l, x-1] and [x+1, r], if l != x and x != r, respectively. Every operation can be done in $\mathcal{O}(\log{n})$ time. Searching for segments around x can be done with set::lower_bound or set::upper_bound and decrementing the iterator if needed.AC code: 157170732
•  » » 47 hours ago, # ^ |   0 Forgot to mention the part that checks the answer. For a query [x1, x2], we just need to find a segment that includes x1, and see if that segment also includes x2.
•  » » 44 hours ago, # ^ |   0 Looks like a weakened version of Chtholly Tree (or to use a more accurate description, maintenance of connected color segments).
 » 47 hours ago, # |   +1 Can someone suggest similar problem like D
•  » » 47 hours ago, # ^ |   0
 » 47 hours ago, # | ← Rev. 3 →   0 Problem A 157243966 Can anyone check is this solution is correct or not because in verdict it is showing In Queue.
 » 46 hours ago, # |   0 great job never mind but u need better choice win better an do better code is life and a way to win so i will help if need job or help so win
 » 34 hours ago, # |   0 First,it's rating.It's because they would like to practice since there is no div.1 for it
 » 33 hours ago, # |   0 Can someone please explain why my solution from problem C is giving TLE. 157292933Thanks
•  » » 32 hours ago, # ^ |   0 put fast io here you go
•  » » » 31 hour(s) ago, # ^ |   0 Thanks
 » 33 hours ago, # |   0 My video editorial: https://youtu.be/Qa9gabukKqg