flamestorm's blog

By flamestorm, 3 months ago,

Thanks for participating!

1722A - Spell Check

Idea: mesanu, MikeMirzayanov

Tutorial
Solution

1722B - Colourblindness

Idea: flamestorm

Tutorial
Solution

1722C - Word Game

Idea: flamestorm

Tutorial
Solution

1722D - Line

Idea: flamestorm

Tutorial
Solution

1722E - Counting Rectangles

Idea: mesanu

Tutorial
Solution

1722F - L-shapes

Idea: MikeMirzayanov

Tutorial
Solution

1722G - Even-Odd XOR

Idea: mesanu

Tutorial
Alternate Tutorial Sketch
Solution

• +71

 » 3 months ago, # | ← Rev. 2 →   0 I didn't even think that Timur is lexicographically in order. What a brilliant solution!Edit: It isn't, but it's still an interesting solution to think of.
•  » » 3 months ago, # ^ |   +6 Its not.
•  » » » 3 months ago, # ^ |   +3 It should be Timru
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +29 i... totally knew that, good reading comprehension, well done, you passed the test
•  » » » » 3 months ago, # ^ |   0 there should be "Timru" instead of "Timur" in the editorial solution
•  » » » » » 3 months ago, # ^ |   0 it is sorted afterwards , so eventually it is Timru only
•  » » » » » » 3 months ago, # ^ |   0 Timru
 » 3 months ago, # |   +15 Problem D can also be solved in O(n) using two pointers
•  » » 3 months ago, # ^ |   0 exactly
•  » » 3 months ago, # ^ |   0 Can you give your solution here it would help
•  » » » 3 months ago, # ^ |   0 here if you need explanation feel free to ask
•  » » » » 3 months ago, # ^ |   0 Hello, I saw your solution but I didn't understand this line . What is it for > for (k;k<=n;k++) ans[k]=s;
•  » » » » » 3 months ago, # ^ |   0 let's suppose that it was already optimal like RRLL so in the line you mentioned it just sets the remaining indexes (which could not be covered in while loop cuz of being optimal) they will just get the previous value as we will not be changing them...
•  » » » » » » 3 months ago, # ^ |   0 Thank you.
•  » » » » » 3 months ago, # ^ |   0 Let's say the number of characters I needes to change was 8 and n is 10. I need go give an answer for all k such that 1<=k<=n so I just output for the remaining k
•  » » » » » » 3 months ago, # ^ |   0 I got it. Thank you so much.
•  » » » » » » » 3 months ago, # ^ |   0 You're welcome
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Check out my submission for problem D it might help you understand you the two pointer approach bettetb
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 Hi, I couldn't understand why you changed both the front and back pointer simultaneously in the while loop.Edit -> Nevermind, got it. Thanks.
•  » » 3 months ago, # ^ |   0 I solved it in O(n) aswell, but using prefix array170271299
•  » » » 3 months ago, # ^ |   0 Can u pls explain,how did u do it using Prefix arrays
•  » » » » 3 months ago, # ^ |   0 Take a look at the comments in the submission, if that doesn't help let me know once again.
•  » » » » » 3 months ago, # ^ |   0 Still i didn't get .M new to prefix array
•  » » » » » » 3 months ago, # ^ |   0 You can have a look at others two-pointer solution. It's almost similar. ExplanationHere you can go to this link for prefix array.Now, for this question in each move you make, you want to maximise the value you can get, so it makes sense to pick either the left-most or right-most direction that has to be changed.Take this example 12 LRRRLLLRLLRLSplit it into two half's, LRRRLL LRLLRLNow, for the left part, you want to make everything R, while for the right part you want everything to be L. (why? i will leave that to you)For the first part, we will work from left to right, for right part we will work from right to left. (This can be done with two pointer aswell)Now, whenever you find a value that has to be changed, remove what it was contributing to the sum, and add what it will contribute when changed the direction.Keep storing them in array. Then make a prefix array.Now, for each move from 1 to n, you can add their respective moves to the sum.
•  » » 3 months ago, # ^ |   0 Yes, I solved it in the same way.here
•  » » 3 months ago, # ^ |   0 What is two pointer approach... Can you share some resources from where I should learn... It would be a great help
•  » » » 3 months ago, # ^ |   0 Check Codeforces edu section. You can also read about it on USACO Guide
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Two pointer is basically using two indices to traverse through an array on the basis of some condition that you can apply on both the pointers(pointing to a particular index), like in the D part of the question we take one pointer at very start and one pointer at very end of the array and then we can check if we got a left viewer with first pointer then changing it to R will give a better score till n/2-1 and checking the same thing for the right pointer for the right side viewer till n-n/2, we can do this till left pointer is less than right pointer.To understand two pointers you should try solving problems for it instead reading about it, this link will work for basic problems Two pointers and problems on it
•  » » 3 months ago, # ^ |   0 i do it with queue :)
•  » » » 3 months ago, # ^ |   0 It can be done too, because there indices that must be changed before others right?
•  » » » 3 months ago, # ^ |   0 Super Cool Bro ,How did that idea come about?
•  » » 2 months ago, # ^ |   0 time O(n), space O(n) with a queue: https://codeforces.com/contest/1722/submission/174060421
 » 3 months ago, # |   0 Why is problem A $O(n)$? You check if $n = 5$ in $O(1)$; If it is, then sort the string which in this case will always have length $n = 5$ so sorting and checking is done in $O(1)$ (since the length is upper bounded). So overall $O(1)$, or am I missing something?
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 I think that's true. Change it, flamestorm.
•  » » » 3 months ago, # ^ |   0 You check if "T" is in the string, that can be done in $O(1)$ (since it only has 5 elements). Then you check if "i", also $O(1)$ And so forth. In total $5 \cdot O(1) = O(1)$
•  » » » » 3 months ago, # ^ |   0 You have to read the string size of n, so it is O(n)
»
3 months ago, # |
Rev. 2   +41

problem G:

topic 1

Regardless of your correct answer, when you choose some elements and take their XOR, then the value will be equal to the XOR of the remaining elements. Why?
Sample: $(4,2,1,5,0,6,7,3)$ is one of answer for $n=8$, and $4 \oplus 0 \oplus 3 = 2 \oplus 1 \oplus 5 \oplus 6 \oplus 7 = 7$

topic 2

There exists a randomized solution.

Explanation
topic 3

For $3 \le n \le 6$, the answers are provided in the sample, so let's use them as a prefix.

• $n \equiv 0 \mod 4$ then prefix = $(2,1,3,0)$
• $n \equiv 1 \mod 4$ then prefix = $(2,0,4,5,3)$
• $n \equiv 2 \mod 4$ then prefix = $(4,1,2,12,3,8)$
• $n \equiv 3 \mod 4$ then prefix = $(2,1,3)$

After that, add $(100,101,102,103,\dots)$ until the length of the sequence becomes $n$. (note that the length of added sequence is a multiple of $4$ ) Then, you can get a correct answer.
Submission: 170321109

Why?
•  » » 3 months ago, # ^ |   0 master piece. i tried to construct a solution similar to topic 3, but unfortunately fell into tons of case work.however, instead we can take advantage of samples, XD
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 thanks a lot!!
•  » » 3 months ago, # ^ |   0 Thanks alot. Can you share the proof of topic 3 ?
•  » » » 3 months ago, # ^ |   0 proof with an exampleLet's see the bitwise expression for some examples. For $k=37$, $4k+0=148=10010100$ $4k+1=149=10010101$ $4k+2=150=10010110$ $4k+3=151=10010111$ The prefix of bitwise expression except the last $2$ digits are same, so their XOR is $0$. And the last $2$ digits are $00,01,10,11$, then their XOR is also $0$. So, overall XOR is always $0$.
•  » » » » 3 months ago, # ^ |   0 That's great! Thanks alot.
•  » » 3 months ago, # ^ |   0 A1⊕A3⊕⋯=A2⊕A4⊕… ↔A1⊕A2⊕A3⊕A4⊕⋯=0can you swap randomly and still have the equality?if yes, can you do the same in X ^ Y < A ^ B -> x ^ B < A ^ Y ?
 » 3 months ago, # |   0 The latex for $2^{30}$ is bugged in the tutorial of problem G. Aside from that, problem G is a really cool problem!
•  » » 3 months ago, # ^ |   +5 What no {} does to a mf
 » 3 months ago, # |   0 For anyone who is finding the solution of problem F, hard to understand/code, can take a look at my solution using DFS 170297341
 » 3 months ago, # |   0 D can be solved using two pointers.The main idea is that the first half of the line should look to the right and the second half to the left. We keep two pointers l and r on both ends and recalculate the sum whenever we encounter a position that needs to be changed.
 » 3 months ago, # |   0 Can we solve problem E using binary search?
•  » » 3 months ago, # ^ |   0 should give a TLE or difficult to pass since for every query you will traverse all 1000 (x) and BS for (y)which will give "1e5 * 1000* log(1000)"
•  » » 3 months ago, # ^ |   0 I did it this way because I didn't know about 2d sum prefixes. You need to keep a sorted 2d array, and then another 2d array of sum prefixes for 1..1000. Then you do two binary searches on the ranges to get your start and end.It was slow but I passed using Go at 3500ms.
•  » » » 3 months ago, # ^ |   0 May be that will fail system testing.
•  » » » » 3 months ago, # ^ |   0 It did TLE. I also solved with same approach and it TLEd.
•  » » » » 3 months ago, # ^ |   0 And yet somebody's n*q solution passes :clownface: https://codeforces.com/blog/entry/106478?#comment-948495
•  » » » » 3 months ago, # ^ |   0 Yup you were right.
•  » » » » » 3 months ago, # ^ |   0 Mine Problem C was also hacked due to TLE I used a very dumb method to solve that initially.
•  » » 3 months ago, # ^ |   0 I got TLEd for that
•  » » 3 months ago, # ^ |   0 I tried but I don't think it will pass with Python. https://codeforces.com/contest/1722/submission/170427049
 » 3 months ago, # |   0 Good contest, got sidetracked by D by trying to use two pointers. Your solution is much more elegant.
 » 3 months ago, # | ← Rev. 2 →   +18 Weak pretests for A , so many solutions got hacked.
•  » » 3 months ago, # ^ |   0 Your solution is weaker
•  » » » 3 months ago, # ^ |   +4 Agreed and that's a pity that such a solution passed.
 » 3 months ago, # |   0 How to write the code for Problem G with the alternate tutorial, I am unable to understand the approach
•  » » 3 months ago, # ^ |   0 underStood
•  » » 3 months ago, # ^ |   0 170326725 Here you are
 » 3 months ago, # | ← Rev. 2 →   -9 Simple implementation for problem G void solve() { int n; cin >> n; int xorr = 0; vector ans; for (int i = 1; i <= n - 2; ++i) { ans.push_back(i); xorr ^= i; } if (xorr != 0) { ans.push_back(1 << 30); ans.push_back((xorr) ^ (1 << 30)); } else { /* The maximum xor of all the elements from 1 to n-2 or n-3 will be less than 2**21. (So, you can choose any power of 2 from [21, 30) and replace n-2 with it) If we have XOR([1...n-2]) as zero, we can remove (n-2) and can push (1<<21) And now the XOR([1....n-3, (1<<21)]) will be some number having the 21st as set Now, we just need two more nos, that can be (1<<30) and XOR([1...n-3, (1<<21)])) ^ (1<<30) */ xorr ^= (n - 2); ans.pop_back(); ans.push_back(1 << 21); xorr ^= (1 << 21); ans.push_back(1 << 30); ans.push_back(xorr ^ (1 << 30)); } for (auto &i : ans) { cout << i << " "; } cout << nline; } 
•  » » 3 months ago, # ^ |   0 Thanks
 » 3 months ago, # | ← Rev. 3 →   -6 Problem F can be done using Surprise !DFS:D
•  » » 3 months ago, # ^ |   0 (￣︿￣)
•  » » 3 months ago, # ^ |   0 That’s what I did lmao
•  » » 3 months ago, # ^ |   0 Good!
•  » » 3 months ago, # ^ |   0 Can you please tell me where my submission 170342106 for problem E is failing?
•  » » » 3 months ago, # ^ |   0 I think your code is quite overcomplicated
•  » » 3 months ago, # ^ |   0 tgp07 Excellent editorial, better than official one! Could you please tell me if there is a way to solve E under the same time constraints for tighter dimensions of the rectangle say 1e5 or 1e9 or even higher?
•  » » » 3 months ago, # ^ |   0 That would be a lot tougher. I'm not immediately sure of any way to solve that.
•  » » 3 months ago, # ^ |   0 your G one is really good Thanks for sharing.
•  » » 3 months ago, # ^ |   +1 I think an improvement for F would be to extend adjacency to include diagonals, i.e., each cell has up to 8 neighbors for the purposes of DFS. Then all we need to do is make sure each connected component has size 3 and forms an L shape.This way, there is no need to check if different blocks touch by edge or corner, since the DFS would've merged such cases into larger components. (also, checking whether three cells form an L-shape can be done by simply checking if, for each of the three pairs of cells, the difference between the x- and y-coordinates is at most 1)
•  » » » 3 months ago, # ^ |   0 This seems smart, have you submitted a solution with this approach?
•  » » » » 3 months ago, # ^ |   0 I had a partially written code, but the contest ended and I didn't bother finishing it up. But your comment encouraged me to complete and submit it, so here it is: 170513958!
 » 3 months ago, # |   0 Why I am getting runtime error in problem C .Here is my solution
•  » » 3 months ago, # ^ |   0 Take a look at Ticket 16132 from CF Stress for a counter example.
 » 3 months ago, # |   0 My first contest solving more than 1 problem :) I was excited to realize I could use a max heap to solve problem D.
 » 3 months ago, # |   0 Can anyone tell me a testcase where my submission 170342106 is failing for problem E?
•  » » 3 months ago, # ^ |   0 Take a look at Ticket 16131 from CF Stress for a counter example.
•  » » » 3 months ago, # ^ |   0 got it thanks
 » 3 months ago, # |   0 What's hack ??! In the verdict of my submission it's written as hacked but earlier it was accepted any one care to explain what this hack is ??!
•  » » 3 months ago, # ^ |   0 Some of the corner test cases are not added while you submit the solution. And if you have not handled those cases and someone else break your code for any of those test cases means your solution is hacked .
 » 3 months ago, # |   0 Damn. I was not getting what was going wrong in the first question. Used a if condition, which updates a count and individually checked the letters with T i m u r. But, it gave me wrong results. If i had not lost time on this, 5 questions were quite easy to do
 » 3 months ago, # |   0 When will my rating appear, yesterday was my 1st contest.
•  » » 3 months ago, # ^ |   0 For div2, preliminary ratings are updated in 2-3 hours. For education rounds/Div 3/Div 4, we have an open hacking phase which lasts for 12 hours so yeah, expect waiting for atleast 18 hours.
•  » » » 3 months ago, # ^ |   0 Ok
•  » » » 3 months ago, # ^ |   0 bro I am new here.Can you tell me what is this open hacking phase?
•  » » » » 3 months ago, # ^ |   0 In div3/4 and Educational round, we have an open hacking phase for 12 hours. This means you can view others' code and find a test case where their code fails. If you hack their solution, the system will use this test case provided by you after these 12 hours during the system test (after which we get our final result, I hope you know the difference between system test and pretests). Hacking others won't give you extra points in the Edu round or Div 3/4. The only purpose of Open hacking phase is to promote hacking others' solutions and to understand others' writing styles. Hacking others will give you extra points in Div 2/1. To know more in detail, please use the codeforces search box. Searching is a good habit when on the path to becoming a competitive programmer. All the best!
•  » » » » » 3 months ago, # ^ |   0 @nikhilofindia thanks bro
•  » » » 3 months ago, # ^ |   0 usually div. 3 gets preliminary rating updates by now right?
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 Max to Max 5PM IST (from what I have experienced) This is worst case. Edit: Looks like we have a new worst
 » 3 months ago, # | ← Rev. 6 →   0 Hey!, can someone help me up solving question F, My logic for the solution was that for each * there can be only and only 2 '*' neighbors in all 8 directions(if a cell exists there) no more, no less than that. But it fails on test no. 4, 69th ticket. can someone help me find a test case where this fails. WA link — https://codeforces.com/contest/1722/submission/170290140Any help would be very appreciated.
•  » » 3 months ago, # ^ |   0 Check out my solution maybe it’ll help you
•  » » » 3 months ago, # ^ |   0 Thank you, nice code
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 1 3 3 .*. *.* .*.
•  » » » 3 months ago, # ^ |   0 Thanks a lot, how do you come up with such cases, like how do you think of cases where our code might fail, how to develop that? any tips on that would be very helpful.
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 If it's after the contest, you can simply view the test cases in your submission. Often the input would be truncated, but you can often still find a way to reveal it. Modify your code by adding conditions to specifically check for the problematic test case, and then use it to print the result. In this case, for example, you can see that in Test #4, the first case has n = m = 3, unlike the earlier Test Suites. So you can write your program such that if the first test case begins with n = m = 3 (you can use scanf for this, if desynced with cin), then you call a different function that reads the first 68 cases while printing absolutely nothing (not even the answers), and then reads the 69th case to print the complete test case details. When submitting, this should pass Tests #1-3, and then print the problematic test case in #4 for you to view. This can be cumbersome sometimes, but at least it's a generally definite approach to finding the test case that breaks your program. I haven't yet encountered a situation where I was unable to expose the problematic test case this way.
•  » » » » » 3 months ago, # ^ |   0 That's an awesome way to find a test case, Thanks a lot
 » 3 months ago, # |   0 1722A - Spell Check Hacking not done properly, go through it once
 » 3 months ago, # |   0 My idea for G : XOR of 4 consecutive numbers starting from 0 is 0. 2^20 is greater than 2e5 which gave me sufficient power of 2's to play with. Requires just some more case work for the remaining element. Approach
 » 3 months ago, # |   0 for problem Gfor n = 5,the solution: 0 1 33554433 2 33554434 is valid or invalid???
 » 3 months ago, # | ← Rev. 2 →   0 My code for C using sets concepts in maths. t = int(input()) for _ in range(t): tot_words = int(input()) * 3 s1 = set(x for x in input().split()) s2 = set(x for x in input().split()) s3 = set(x for x in input().split()) only_in_s1 = len(s1 - s2 - s3) only_in_s2 = len(s2 - s1 - s3) only_in_s3 = len(s3 - s1 - s2) in_s1_s2_s3 = s1 & s2 & s3 s1_s2 = len((s1 & s2) - in_s1_s2_s3) s2_s3 = len((s2 & s3) - in_s1_s2_s3) s3_s1 = len((s3 & s1) - in_s1_s2_s3) score_of_s1 = (only_in_s1 * 3) + (s1_s2 + s3_s1) score_of_s2 = (only_in_s2 * 3) + (s2_s3 + s1_s2) score_of_s3 = (only_in_s3 * 3) + (s3_s1 + s2_s3) print(score_of_s1, score_of_s2, score_of_s3) 
•  » » 3 months ago, # ^ |   0 Funnily I completed sets chapter only yesterday.
 » 3 months ago, # | ← Rev. 3 →   0 fst
 » 3 months ago, # | ← Rev. 2 →   0 Is it only Me or anybody else also noticed that F was comparatively easy E for those who till now havent encountered problem based on 2-D PREFIX Sum . I am feeling very frustrated as I spent more than one hour on E and also during the contest F have least successful submission so I just dont focused on F
 » 3 months ago, # |   0 problem D can also be solved in O(n) time using two pointers using a greedy approach. in the first half of the string, we can get better answer by converting the leftmost 'L' to 'R' and in the second half of the string, we can get better answer by converting the rightmost 'R' to 'L'. link to my code — 170257607
 » 3 months ago, # | ← Rev. 2 →   0 A very simple and easy solution of G .
 » 3 months ago, # |   +1 Alternate solution for Problem G: Observe that $a \oplus b$ $=$ $\sim a \oplus \sim b.$ Now you can construct a sequence $a0$, $\sim a_0,$ $a_1,$ $\sim a_1,$ $a_2,$ $\sim a_2, \dots$ (upto n terms) where $n \equiv 0$ ($mod$ $4$). For $n = 4k+1$ or $4k+2$ or $4k+3$, just take some prefixes of length $1$ (0), $6$ (4,1,2,12,3,8), and $3$ (2, 1,3) respectively from the given testcases itself and the remaining sequence will be of length $4k'$. Note that $a_0$, $a_1$, $\dots$ can be taken to be $13,$ $14,$ $15,$ ... as none of the prefixes contain elements $>13$. Also, $\sim a$ represents 1's compliment of $a$ inverting all 32 bits of $+a$, although (even the first 20 bits would work considering the constraints on $a_i$)
 » 3 months ago, # |   0 On Problem 1722B Colourblindness I had the same Approach But still got WA on test case 3 #include using namespace std; #define ll long long; #define vi vector #define pb push_back #define all(x) x.begin(),x.end() #define rep(i,a,b) for(int i=a;i> len; char upper[len],lower[len]; cin>>upper; cin>>lower; rep(i,0,len) { if(upper[i] == 'R' && lower[i] != 'R')return "NO"; if(lower[i] == 'R' && upper[i] != 'R')return "NO"; } return"YES"; } int main(){ ios::sync_with_stdio(1);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); #endif int tc=0;cin >> tc; while(tc--)cout << solver() << endl; return 0; } 
 » 3 months ago, # |   0 what is the use of greater() in the sort function of the D problem?
•  » » 3 months ago, # ^ |   0 Its a comparator which defines how you want it be sorted. You can read more about it here
•  » » » 3 months ago, # ^ |   0 thanks
 » 3 months ago, # |   +1 In the problem E, trivial $O(n q)$ solution passes due $\mathrm{TL} = 6 \mathrm{s}$: 170297542
•  » » 3 months ago, # ^ |   0 I wonder how your fastIO works...My BF solution 170407110 could pass only when adding your fastIO code. (And on test 4, it is 15 times faster than simply using untie cin/cout). It seems impossible because IO shouldn't be the bottleneck of this problem. I'm really confused about this.
•  » » » 3 months ago, # ^ |   0 We need optimize any constant in time complexity of solution. And it is fastest I/O (on Windows) that I have been seen. In it, I completely abandoned small buffers (usually ~2KiB) that lead to a lot of file operations, and also decided to completely abandon non-system I/O functions due to overhead. Large buffers allow your program to use two file operations during work.And when -O3 is specified, gcc inlines my function ReadInt32, but no printf and std::cin.
•  » » » » 3 months ago, # ^ |   0 I discuss this with some friends and get a weird conclusion. You can see the difference between 170435459 and 170435486. Seems that when we replace the last cin with a function (although we still use cin to read), the compiler will use SIMD to optimize the if statement. Replace function with inline function even macro gets the same result. But just using cin or scanf won't trigger optimization. I have no idea why this happens :(
 » 3 months ago, # |   0 I solved 3 problems but my rating doesn't change. my rating point is still 0point
 » 3 months ago, # | ← Rev. 3 →   +1 I solved problem G quite differently from the editorial method utilising the property that XOR of consecutive numbers x and y is always 0 when x is an even number (if you didn't know this, it's easy to see why, by taking a few consecutive numbers and looking at their binary representation).Let set a and b represent respectively the set of numbers at even positions and the set of numbers at odd positions. Then we break solution into 4 cases depending on the remainder of n on dividing by 4. Case 1.) n%4 = 0Here both sets have an even number of elements. So we can just keep pairing two consecutive numbers and that will suffice. Case 2.) n%4 = 1In this case, set a will have 1 more element than set b. In order for them to have the same end result (xor), we can just insert a 0 in set a as 0 is a neutral element. Now we just have to put pairs of consecutive numbers as in above case. Case 3.) n%4 = 3This case is similar to Case 2 but set a will have an even number of elements and set b will have an odd number of elements. We can make up for the lack of a pairing element in set b by just inserting element 1 (which was to be the result of the XOR of two consecutive elements anyway). Case 4.) n%4 = 2Here both sets will have odd size. That means they will both need a single extra element that can't be paired. That element can't be the same (that's why minimum n is not 2 in the problem).We can break any such n into a combination of 3's and 2's, there will be a trio of 3 numbers and all the rest are pairs. Minimum n is 3, so this will fit. We can find 3 such numbers for both the sets s.t. they are all different and their XOR is same. I just looked at the samples which happen to have this test case for n = 6. So I took the numbers from the sample solution (set a : 2, 3, 4 ; set b : 1, 8, 12), their XOR is 5. The remaining elements can all be pairs of consecutive numbers as described above.I think some of the cases can probably be combined for a simpler solution. Please let me know in the comments.Not so elegant and repetitive implementation : 170369765
•  » » 3 months ago, # ^ |   0 I solved in the same way
 » 3 months ago, # | ← Rev. 3 →   0 In E, I'm getting MLE if I put prefix array in the heap memory, but the solution passing when I put the prefix array as a global array. Why is that so?170374285 int main() { ll** pt = new ll*[1001]; ll** dp = new ll*[1001]; for(int i=0;i<=N;i++){ pt[i] = new ll[1001]; dp[i] = new ll[1001]; } //...... } vs170372939 ll pt[1001][1001]; ll dp[1001][1001]; int main(){ //..... } 
•  » » 3 months ago, # ^ |   0 The same thing was happening with me.https://www.geeksforgeeks.org/why-global-array-has-a-larger-size-than-the-local-array/Hope this helps!
 » 3 months ago, # |   0 A much simpler (in my opinion) and more readable solution for Problem F with necessary comments : 170377676
 » 3 months ago, # | ← Rev. 2 →   0 Another way to solve F: L-shapes:ref: https://codeforces.com/contest/1722/submission/170380611Note that, a 2x2 grid will contain L shape if and only if there are exactly 3 '*' in it.1)Firstly for all 2x2 subgrid that contain L-shape, check whether its surrounding has any '*' in it, if so, then the ans is NO. [except for the corner along void position(exactly one such position) of 2x2 grid , eg: '#' in below picture [and ^ is void position] ]...#.*^..**.....2)Now the only problem is, there can also be any other shapes than L-shapes. To find that, In logic1, just whenever current 2x2 subgrid contain L,(ie:exactly 3 '*' in it) , mark those positions as #.So that all L shapes will be marked, and if there exist any other shape than L shape then it will remain unmarked(ie:remains *).So, atlast traverse the whole grid to find any such unmarked position,if so, the ans is NO,Otherwise YES.
 » 3 months ago, # |   0 Can somebody explain solution E, I have never seen use of prefix sum like this. I dont quite get it what thay have exactly done here
•  » » 3 months ago, # ^ |   0 suppose you have a data structure which stores 2D-prefix sums, such that sum of rectangles with height <= H and width <= W = pref[H][W]then if you wanna know the sum of areas of rectangles with height < Hb and width < Wb (condition — i) then that would equate to pref[Hb — 1][Wb — 1]now say you want the sum of areas of rectangles which have height <= Hs and width <= Ws(condition-ii) the rectangles which satisfy both condition i and ii is the required answerfor learning about 2D-prefix sums I would suggest going through the USACO guide, they have detailed and easy to understand content, https://usaco.guide/silver/more-prefix-sums?lang=cpp#2d-prefix-sums
•  » » » 3 months ago, # ^ |   0 Thanks mate, U r a lifesaver
 » 3 months ago, # |   0 Why didn't my ratings update ? :'(
•  » » 3 months ago, # ^ |   0 NVM LOL
 » 3 months ago, # |   0 My Solution for Fdid the same thing as mentioned in the editorial but is easier to understand.
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 My solution : 170453262 for problem F
 » 3 months ago, # |   0 The first problem can be solved with a frequency array, by calculating the frequency of each character while taking inputs. Then check whether the frequency of each character of "Timur" is equal to one or not.
 » 3 months ago, # |   0 I got wa on F test 3 170393551 can somebody say the problem
•  » » 3 months ago, # ^ |   0 Take a look at Ticket 16138 from CF Stress for a counter example.
•  » » » 3 months ago, # ^ |   0 Tnx
•  » » » 3 months ago, # ^ |   0 170377578
•  » » » » 3 months ago, # ^ |   0 Lol, what's that supposed to mean?
•  » » » » » 3 months ago, # ^ |   0 Submission no
•  » » » » » » 3 months ago, # ^ |   0 Unfortunately, I do not respond to personal requests. You can always consider purchasing a subscription if you need instant help. If you want the community to help you instead, you need to describe your approach/issue with proper links to your submission. Just dumping the submission ID won't do it.
 » 3 months ago, # | ← Rev. 2 →   0 There is O(n) (I believe it is, at least amortized) solution for problem D https://codeforces.com/contest/1722/submission/170241642
•  » » 3 months ago, # ^ |   0 Check out my solution which is straight O(N)
 » 3 months ago, # |   0 Is there anywhere I can view solutions in java?
•  » » 3 months ago, # ^ |   0 The status page (https://codeforces.com/contest/1722/status) lets you filter by language.
 » 3 months ago, # |   0 It was a nice contest though F was quite exhaustive
 » 3 months ago, # | ← Rev. 3 →   0 Here is a bit shorter code for F: 170427907 SpoilerObserve that for a valid construction:1- Each * has exactly three neighboring *2- Maximum connected chain of * is of length 3second condition is neccesay to avoid patterns with shapes close to "circular" like these: .*. *.* .*. .**. *..* *..* .**. 
 » 3 months ago, # |   0 In Spell Check Why do we need to sort name too? Because if I'm not sorting name then I'm getting an error Please can anyone explain what I'm missing here
•  » » 3 months ago, # ^ |   0 because its not lexicographic "Timur" -> "Timru" is lexicographic.
 » 3 months ago, # |   0 Is there any other way to solve #C without using a map?
•  » » 3 months ago, # ^ |   0 Use sets, check out my submission here at https://codeforces.com/contest/1722/submission/170192052
•  » » 3 months ago, # ^ |   0 Yes. I solved it using unordered_set.c++ code: 170218148
•  » » 3 months ago, # ^ |   0 Ahh, thanks (:
 » 3 months ago, # |   0 anyone , where can i get some greedy questions like "Line question", where need to handle edge cases and stuff like that?
 » 3 months ago, # |   0 Here you can see the promble F be sloved by using BFS.
 » 3 months ago, # | ← Rev. 3 →   0 Problem E can also be solved with offline queries and binary search on segment tree, which gives O(t*n*logn) that satisfied arbitrary large height and width of the rectangles.
 » 3 months ago, # | ← Rev. 2 →   0 Simple Solution for 1722F -L-shapes problem without DFS or BFS. ApproachNote: Using 1-based indexing for matrix. Traverse the elements of the matrix. If at index (i, j) star is present, then let's take cntStars for the count of stars around index (i, j) in its neighbor region of 3 x 3. Let sumX and sumY be the sum of x and y coordinates of neighbors of (i,j) where star '*' is found. If (cntStars != 3) or (sumX == 3 * i) or (sumY == 3 * j), then we break traversal and print "NO". Otherwise print "YES". Above 4th point explanation: If there are 3 stars in a 3x3 region around index (i, j) and at index (i, j) star is also present. If the stars do not form an L-shape, then they will be aligned in a straight line and either sum of x coordinates or y coordinates will be thrice of i or j respectively. C++ code: 170466848
•  » » 13 days ago, # ^ |   0 Hello.A question : why isn't enough to check only if the cntstars ==3 ?what is the corner case ? 181822571
 » 3 months ago, # |   0 My solution for G:xor of 2x (even no.) and 2x+1 is always 1.Case 1: n%4 == 0: A simple solution would be 20,20+2n,21,21+2n,22,22+2n,....Case 2: n%4 == 1: Just add a 0 at the end of Case 1Case 3: n%4 == 2: Just add 4 1 2 12 3 8 this sequence at the end of Case 1 (Provided in sample input for n=6)Case 4: n%4 == 3: Just add 2 1 3 this sequence at the end of Case 1 (Provided in sample input for n=3)
 » 3 months ago, # |   0 https://codeforces.com/contest/1722/submission/170472565 Can anybody tell me the mistake in my code for Problem F
•  » » 3 months ago, # ^ |   0 Take a look at Ticket 16145 from CF Stress for a counter example.
•  » » » 3 months ago, # ^ |   0 Thanks you sir for the help!
 » 3 months ago, # | ← Rev. 2 →   0 I got it
 » 3 months ago, # |   0 D in linear time : 170362765
 » 3 months ago, # |   0 Chekout the solution for Problem E 170565433
 » 3 months ago, # |   0 Upvote if you love competitive programming by heart.
 » 3 months ago, # |   0 Error Report:: For the 1722E ( Counting Rectangles ) Tutorial, the corners to consider should be top left and bottom right, instead of lower left and upper right!
 » 3 months ago, # |   0 I am not able to solve 4 th question . can anybody help to solve it?????
 » 3 months ago, # |   0 why does the another approach worked in G can anyone explain please?
 » 5 weeks ago, # |   0 can u tell why m i getting runtime error for qstn B ?? [submission:178089241] 
 » 3 days ago, # | ← Rev. 2 →   0 although it was 3 months later but I have to say that the tutorial of G has a little mistakeI think it should be $2 ^ {30}$ here but it's $2 ^ 30$ :)anyway, good problems and good tutorial !