### ScarletS's blog

By ScarletS, 2 months ago,

Thank you for participating in our contest! We hope you enjoyed it. Implementations will be added soon (when Codeforces lets authors submit solutions!).

Please let us know what you thought of the problems by voting!

1758A - SSeeeeiinngg DDoouubbllee

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Feedback

1758B - XOR = Average

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial
Feedback

1758C - Almost All Multiples

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial
Feedback

1758D - Range = √Sum

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Video Editorial
Feedback

1758E - Tick, Tock

Hint
Solution
Implementation (C++)
Implementation (Java)
Implementation (Python)
Feedback

1758F - Decent Division

Hint
Solution
Implementation (C++)
Implementation (Python)
Feedback

• +66

 » 2 months ago, # |   -93 stupid constructive problems
•  » » 2 months ago, # ^ |   +5 Stupid?? How?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +82 we did inform you in the announcement, didn't we?
•  » » » 2 months ago, # ^ |   +45 omg saarang comment
•  » » » » 2 months ago, # ^ |   0 omg @saarang comment
•  » » » » 2 months ago, # ^ |   0 omg saarang comment
•  » » » 2 months ago, # ^ |   +1 I think you should still try to vary the problems a bit. Making a round where more than half of the problems are constructive doesn't make any sense. Maybe you could as well make a math contest.
•  » » » 2 months ago, # ^ |   -49 Since when did we start taking announcements seriously? you also hinted that there may be an interactive problem, but I can't find any. Maybe next time keep your constructive problems for your mom.
•  » » » » 2 months ago, # ^ |   -6 do you know what atmost 1 means just asking
•  » » » » 2 months ago, # ^ |   +12 skill issue
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 constructive algorithms and greedy are the part of problem-solving, They are not stupid.
 » 2 months ago, # |   +8 wow thanks for the quick editorial
 » 2 months ago, # |   +10 Very good round (even though I lost rating :cri:)
 » 2 months ago, # | ← Rev. 3 →   +12 I am proud to First Solve B today, it's my first time having such great experience.on D, I did not divide cases, instead I thought about two pointers. I set $L=\min$ and $R=\max$, and the total sum as $\frac{L+R}{2} \cdot n$. And then, I advanced $R$ and $L$ until I could find an answer. For the exact method, please see my accepted submission — 182519051. I am yet not sure how this method really works, but it did. Can anyone provide a formal proof on why this works?
•  » » 2 months ago, # ^ |   -52 I C how your solution for B matches the same solution on YouTube and more over your template and Language keep on changing with every other problem. Do you feel guilt? Shit anyway.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +48 I C how your solution for B matches the same solution but I was literally first solve. I can't be copying anyone else if I'm the first one to solve LOLUPD: proof
•  » » » » 2 months ago, # ^ |   0 That me on that pic??!?!?!
•  » » » » » 2 months ago, # ^ |   +13 Yep, looks like you're there, though I didn't really intend on targeting anyone specifically in the screenshot.
•  » » » » » » 2 months ago, # ^ |   0 I just was too excited that I'm one of the first who solved B
•  » » » » 2 months ago, # ^ |   +3 Cool I was 5th apparently
 » 2 months ago, # | ← Rev. 2 →   +21 Here's a simple solution for D. For example, if $n = 5$, we use $[2, 3, 4, 5/6/7/8/9, 10]$. We can add 1 to all numbers to change sum without changing the LHS. To change the value $\mod n$, we can choose the correct integer in the 4th location. Using this we can get all integers above some value. And the square of max — min is provably larger than the current sum. So it works.
 » 2 months ago, # |   -10 Nice problemset!! got +ve delta :)..stuck on D though!
 » 2 months ago, # |   0 I hate my life
 » 2 months ago, # |   +5 C was amazing. Took me 40 minutes but made that..
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 Can any one Point out the mistake i have done : As x was missing from there original position .I am trying to place next multiple (i.e. x2)at that place and repeating the same for next place. codevoid chal() { ll n,x; cin>>n>>x; vector aa(n+1,0); Fo(i,1,n+1){ aa[i]=i; } aa[1]=x; aa[n]=1; ll j=x; while(2*j<=n){ aa[j]=2*j; j=2*j; } if(n!=j){ cout<<-1<
•  » » » 2 months ago, # ^ |   0 You have to check for the factors of n and then iterate over factors to replace the xth element with the next factor of n..Check my code and you will understand, Code
•  » » » 2 months ago, # ^ |   +3 Video Solution for Problem C Hint:Answer is impossible is n is not divisible by xStart with the identity permutation 1,2,3,...,nNow we know, p[1] = x, p[n] = 1, so p[x] = n. So, we get x,2,3,..,x-1,n,x+1,...,n-1,1 The only task left is to make this lexicographically smaller.Now elements from 2,3,...,x-1 are fixed, so to make this lexicographically smaller, which element can you swap?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 hey i am also doing the same(and getting WA) ...what did you find wrong in this logic? 182912947
•  » » » » 2 months ago, # ^ |   0 You should see the example given in the editorial. You will get it. By my logic, there is no answer but there is an answer. But as per the editorial place n at x and then increase the size which also seems to be logical. Spoilervoid chal() { ll n,x; cin>>n>>x; if(n%x!=0){ cout<<-1< aa(n+1); aa[1]=x; aa[n]=1; Fo(i,2,n){ aa[i]=i; } if(x!=n){ aa[x]=n; } debug(aa); ll y=x; for(ll j=x+1;j
•  » » » » » 2 months ago, # ^ |   0 thanks..i got the tc the above logic failing Input 1 12 4Output 4 2 3 8 5 6 7 16 9 10 11 1Answer 4 2 3 12 5 6 7 8 9 10 11 1
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Hey hydra_cody, Can you tell me what is wrong with this logic? I also use the same logic you described above (i.e.,x2). Here is my code-184297340
•  » » » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16556 from CF Stress for a counter example.
•  » » » » » 7 weeks ago, # ^ |   0 Thanks, I find my mistake and submit successfully.
 » 2 months ago, # | ← Rev. 2 →   +46 My solution for D: 182515472Let's assume that the minimum element is $x$ and the maximum element is $y$. Then we have a lot of freedom to change the elements in the middle without changing the range. The smallest sum is when the array is $[x, x+1, x+2,\ldots, x+n-2, y]$ and the largest sum is when the array is $[x, y-n+2, \ldots, y-2, y-1, y]$. We can achieve any sum between these extremes using a greedy algorithm. Start with the array with the smallest sum, visualize the elements as points on a number line, and move elements to the right one by one, where you move it as far as possible without making the sum exceed the target.So if we have values for $x$ and $y$ such that it is possible, we can construct one possible array with the above approach. Now, how do we choose values of $x$ and $y$ for each possible $n$?Let's assume we know $x$. Then we can iterate $y=x+n-1, y=x+n, y=x+n+1,\ldots$ until one of them is valid. We just test validity by making sure the range squared $(y-x)^2$ is between the minimum possible sum $(n-1)x+y+(n-2)(n-1)/2$ and the maximum possible sum $(n-1)y+x-(n-2)(n-1)/2$.I assumed that it will always work when $x=2n$ and I assumed that $y(n) \le y(n+1)$ so that I can use two pointers in $O(n)$ time instead of iterating every possible $y$ for every possible $x$, which I believe would be $O(n^2)$.
•  » » 2 months ago, # ^ |   0 I have iterated over every possible $x$ and every possible $y$ here.https://codeforces.com/contest/1758/submission/182516630
 » 2 months ago, # |   +8 Auto comment: topic has been updated by manish.17 (previous revision, new revision, compare).
 » 2 months ago, # |   0 This is my first time i get standing in top 500. As a pupil, i think this contest is easier than the previous div 2 contests. Anyone think so ?
•  » » 2 months ago, # ^ |   0 Probably because the problems were constructive, which comes easier for some people
 » 2 months ago, # |   0 Putting 69 in B's 1st test case answer was intentional.
 » 2 months ago, # |   +11 E is a really nice problem
 » 2 months ago, # |   0 In problem B , for n=4, why answer can not be 1 1 3 2. ScarletS
•  » » 2 months ago, # ^ | ← Rev. 2 →   +12 The average of 1, 1, 3, 2 is 7/4The XOR of 1, 1, 3, 2 is 11 != 7/4
•  » » » 2 months ago, # ^ |   0 XOR of 1,1,3,2**** = 1
•  » » » » 2 months ago, # ^ |   +6 I fixed it about 4 minutes before you replied...
•  » » » 2 months ago, # ^ |   0 Got it Bro, but in query clarification section you guys said that we have to take real number calculation, acc. to which 7/4==1, that's the only confusion I had. Btw, Thanks again for clarifying here.
•  » » » » 2 months ago, # ^ |   +3 7/4 is a real number :)
•  » » » » » 2 months ago, # ^ |   0 Oh shit:(, I just overthink, Btw Thanks once again.
 » 2 months ago, # |   +15 My solution for D https://codeforces.com/contest/1758/submission/182529333Let's say you want to make the sum of all the numbers as (2*n)^2 then on average all the numbers should be 4*n, now you want max — min as 2*n take max as 5*n and min as 3*n, now if you see all the remaining number still averages out to be 4*n, if n is even, distribute the number like 4*n-i,4*n+i and same for odd just 1 number would be 4*n
•  » » 2 months ago, # ^ |   0 i did the same approach.
•  » » 2 months ago, # ^ |   0 If there's any ans/ approach if I want to take the sum of the nums as n^2?
 » 2 months ago, # |   +1 My solution for C : we can think of a permutation as follows  X,2,3..__....,n-1,1 ( '__' denotes there is no element on the xth index) here at the first index there is x and at the last index there is 1, and all other indices except xth index are filled with permutation[i] = i , i != x; Here only x index has no element in it , and we have not placed n in our list , so we have to place n to the as right as possible. so we can just start iterating from (x+1)th index to (n-1)th index and see if n can be placed at that index and this index can be moved to xth index , if yes then we change x to j. for example n = 12 and k = 2, list = {2,empty,3,4,5,6,7,8,9,10,11,1} now we can see that for 4th index , you can move 4 to the empty place , list = {2,4,3,empty,5,6,7,8,9,10,11,1} and at the empty place you can put n = 12; now you can not shift the empty position to the right so just place n over there list = {2,4,3,12,5,6,7,8,9,10,11,1} Note : You will have to take care of other edge cases as well ! My submission : 182552063
 » 2 months ago, # |   0 what's wrong with my solution for C here?? I can't figure out
•  » » 2 months ago, # ^ |   0 failed test-case:  1   20 2 your output: 2 4 3 10 5 6 7 8 9 20 11 12 13 14 15 16 17 18 19 1correct output: 2 4 3 20 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1
 » 2 months ago, # |   -23 Four constructive tasks... If you can't come up with normal tasks, why are you doing a contest?
 » 2 months ago, # |   0 All the submission I made for problem C in the contest got WA. After contest ended I submitted one and got accepted :(
 » 2 months ago, # |   0 My solution for C #include #define int long long int void solve(){ int n, x; std::cin >> n >> x; std::vector v(n+1); std::iota(v.begin(), v.end(), 0ll); v[x] = n; v[1] = x; v[n] = 1; int i = x+1, j = x; while(i < n){ if(v[j]%i == 0 && i%j == 0){ std::swap(v[i], v[j]); j = i; } i += 1; } bool ok = true; for(int i=1; i> t; while(t--){ solve(); } } If p[1] != n and p[1] = k, p[k] = n then try to place n as further as possible If p[1] = n then no need
 » 2 months ago, # |   0 thanks for the fast editorial and for putting in hints.
 » 2 months ago, # | ← Rev. 4 →   0 My approach for task D: Assume we construct our initial sequence as M, M+2, M+4, .., M+2*(N-1). Difference between endpoints = d = 2*(N-1). Now let's define the Deficit as: sum — d*d. deficit = M*N + N*(N-1) - 4(N-1)^2 We can observe that deficit increases with increase in M, and it increases in multiples of N. So we can binary search for that point where deficit first becomes negative. At this point, absolute value of deficit is <= N. So we can cover the deficit by shifting the in-between elements by 1.
•  » » 2 months ago, # ^ |   0 Your name justifies you
 » 2 months ago, # |   +3 The bound in the editorial for F is indeed quite loose. A simple way to improve it:To remove something we must have added it first so operations are at most 2*(number of added intervals). Case 1 adds one interval, case 2 adds two intervals, however case 2 operations can be at most half of the operations (since they pair with a corresponding case 1 operation). Therefore the described solution will do $3n$ operations at most.
 » 2 months ago, # |   0 another opportunity to feel dumb
 » 2 months ago, # |   0 Can anyone please Point out the mistake I have done? 182566417
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16557 from CF Stress for a counter example.
 » 2 months ago, # |   0 Can someone please explain why this solution 182516763 works for E?
 » 2 months ago, # |   -17 Welcome to ConstructForces. I love it.
 » 2 months ago, # |   0 another solution for problem D For even number n: same as official solution, the answer is [n-n/2, n-n/2+1, ... ,n-1, n+1, ... ,n+n/2-1, n, n/2+1]. For odd number n: construct y = n*4, answer is [y-n, y-((n-1)/2)-1, ... , y-2, y-1, y, y+1, y+2, ... , y+(n-1)/2+1, y+n]. notice the first and the last is special. for instance: 7: y = 28, answer is [21, 26, 27, 28, 29, 30, 35], the max — min = 14, sum = 196 = 14 * 14.
 » 2 months ago, # |   0 I really liked problem d Although it took me every single cell in my brain to solve it But it was worth the effort
 » 2 months ago, # |   0 Why is complexity O(nlogn) instead of O(n) in C?
•  » » 2 months ago, # ^ |   0 Using sieve(if used) .. complexity is O(nloglogn) in avg cases.. in worst cases it will be O(nlogn)..Feel free to correct!!
•  » » » 2 months ago, # ^ |   0 You only need to factorize one number, which can be done in o(sqrt(n))
•  » » » » 2 months ago, # ^ |   0 may be author solution use precomputation of smallest prime factor of all numbers...just like in my soln 182512680
 » 2 months ago, # |   0 great round thanks for quick editorial.
 » 2 months ago, # | ← Rev. 2 →   +3 There's an another quite interesting solution for problem B: a_i=\left\{ \begin{aligned} 1&,i=1 \\ n+1&,i∈[2,n] \end{aligned} \right.In this situation, $XOR = Average = n$.
•  » » 2 months ago, # ^ |   +8 Not true for n = 3: 1 4 4. Average is 3, XOR is 1.
•  » » » 2 months ago, # ^ |   0 Oh sorry, to be more clearly, that's solution for even numbers.As for odd numbers, let $a_i=1$.
•  » » » » 2 months ago, # ^ |   +16 No it's my bad, that should have been obvious. Maybe I shouldn't reply to CF comments while sleep deprived :)
•  » » 2 months ago, # ^ |   0 Can you explain how? my average is coming--> n+1 and XOR= 0 maybe im missing something
•  » » » 2 months ago, # ^ |   0 that's solution for even numbers.
•  » » 2 months ago, # ^ |   0 How did you get the intuition for this?
•  » » » 2 months ago, # ^ |   0 Well, Maybe $(a-1)(a+1)=a^2-1$ inspired me.
 » 2 months ago, # |   0 Very good problems for me, thanks a lot!
 » 2 months ago, # |   +6 For $D$, here is another solution.If $n$ is odd, we can let $[a_1,a_2,\dots, a_n]=[3n,4n-{n-3\over2},\dots,4n-2,4n-1,4n,4n+1,4n+2,\dots,4n+{n-3\over2},5n]$If $n$ is even, we can let $[a_1,a_2,\dots, a_n]=[3n,4n-{n-2\over2},\dots,4n-2,4n-1,4n+1,4n+2,\dots,4n+{n-2\over2},5n]$$\displaystyle\sum_{i=1}^na_i=4n^2,\max-\min=5n-3n=2n$182509063
•  » » 2 months ago, # ^ |   +14 wow thx an elegant and nice solution :D
 » 2 months ago, # |   0 Alternative Solution for D: Let req = (right — left)^2 For a section of n elements spread over a range of length len (len = max — min) and beginning from 1, we can find the min and max possible values that can be obtained by shifting values in this range. ​ Eg: len = 5, n = 3. min = [1, 2, 5] = 8, max = [1, 4, 5] = 10. We run an infinite loop for satisfying the condition min <= req <= max. It can be easily proved that if this condition is satisfied, we'll always be able to find an appropriate solution for req. Now, if max < req, then we'll need to 'boost' (add an offset to all elements), as that is the only way of satisfying the equation. My Solution
•  » » 2 months ago, # ^ |   +3 PS: The infinite loop is only for avoiding extra case work. The equation should be satisfied in only a couple of iterations.
 » 2 months ago, # |   0 what's wrong with my solution for C 182586576 .. i am not able to figure out
•  » » 2 months ago, # ^ |   0 Hey buddy, if you try this test case: 1 16 2 your code will produce this result: 2 4 3 16 5 6 7 8 9 10 11 12 13 14 15 1 which is not optimal as you still have to swap between 8 and 16 to get the minimal permutation. It is not enough to put some number m in place of x and put n in place of m, you may have to do the same process multiple times. In the test case above for example, you need to put 4 in place of 2, 8 in place of 4 and 16 in place of 8 to get the right answer: 2 4 3 8 5 6 7 16 9 10 11 12 13 14 15 1 I hope I was helpful :D
 » 2 months ago, # |   0 182497978 Can anyone explain what i did wrong on Question C Almost All Multiples
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16558 from CF Stress for a counter example.
 » 2 months ago, # |   0 This contest was amazing! Thanks to everyone who contributed to its preparation :D
 » 2 months ago, # | ← Rev. 2 →   0 Guys you need to improve a lot in editorial language. All I read in C editorial was Ohh It must be something high level; I'm not upto this problem. The Solution to C is very simple and intuitive. The basic intuition is just check if a number is already taken and if taken check for multiples who are divisible by n and if yes take that multiple and move on. It's just that simple. I am not good in writing answers as a newbie but man as a newbie reading your answers make me feel like maybe this problem is too tough for me. Take it as constructive and positive criticism. I love the work the Codeforces Team is doing and am grateful for it.
 » 2 months ago, # | ← Rev. 4 →   0 Here is my approach for D — https://codeforces.com/contest/1758/submission/182611450 The explanation is commented out in the code.
 » 2 months ago, # |   0 What's wrong in my solution for C ? here anyone can help??
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16559 from CF Stress for a counter example.
 » 2 months ago, # |   0 Short greedy solution for Problem C: https://codeforces.com/contest/1758/submission/182634632
 » 2 months ago, # | ← Rev. 2 →   0 For Problem D, I am doing Binary search on range and for fixed range we have multiple options [1,range] [2,range+1] , [3,range+2] ... 1) For every option we need to take only n-2 elements(excluding min and max because min and max are fixed as range is fixed) 2) Now For picking n-2 numbers, I am taking min sum possible using n-2 numbers and max sum possible using n-2 numbers 3) min sum is picking first n-2 numbers(excluding first which is reserved for min), and similarly max sum is picking n-2 last elements(excluding last) 4) Now we get a range of possible sum [MIN,MAX] MIN->min sum, MAX->max sum for each option ([1,range],[2,range+1]) etc.. 5) For Any option if range*2 falls into [MIN,MAX] then we found a solution 6) But we cant check for every option linearly, can we do binary search again on array of options which I described above? 7) can someone who followed on similar lines share your code or the approach is not feasible ? 
 » 2 months ago, # |   0 Another solution of D:Start process from 1 2 3 4 5 ... array. At each step, we increase either all elements by 1, or the last element by 1, depending on which part of the equality is smaller. After we have increased the maximum at least once, we get the space to adjust the sum by value = max_cnt_up * (n-2) (by increasing the elements in the middle). If this value is enough, we stop the algorithm.There can be problems only with small n, for example, if n=2 we do not have the opportunity to adjust the sum at all, but fortunately algorithm converges.
 » 2 months ago, # |   0 1758C — Almost All Multiples 182522546Please can anyone help me to figure out why my solution is giving the wrong answer? Thank you in advance.
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16560 from CF Stress for a counter example.
 » 2 months ago, # | ← Rev. 3 →   0 for question D, the sqrt(sum) question. My solution was like this. My solution for the even is the same but for the odd solution i did as like this: my sequence will be in the form of n/2+1,n+3,n+3,n+2,n+2,n+2,n+2,...,3*n/2+2, its sum is equal to n^2 + 2n + 1proof: i did some maths adn made sure that 3*n/2+2>=n+3 for all n (>=2 stated in the question) max-min=n+12*(n+3)+(n/2+1+3n/2+2)+(n-4)(n+2)=4n+9+n^2-2n-8=n^2+2n+1someone pls tell me why am i wrong xd
 » 2 months ago, # |   0 I get the solution for B but can someone please explain their thinking process that lead them to this solution?
 » 2 months ago, # |   0 can someone help me to find mistake in my logic for question C.Logic: I am storing all the numbers from 2 to n except x in a unordered map and then I am writing a for loop and checking if the number equals to idx is present in map or not. if it is not present then I am checking for presence of (idx*2) and also checking if it divides n or not.if it do not divide and if idx divides n then just put n at position idx.
•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16561 from CF Stress for a counter example.
 » 2 months ago, # |   0 1758C — Almost All Multiples — implementation(C++) and implementation(Python) are equal, i mean links are the same, can u correct it pls, thanks for blog btw!!
•  » » 2 months ago, # ^ |   0 Fixed.
•  » » » 2 months ago, # ^ |   0 ty!!
 » 2 months ago, # |   0 my submission D:182975484 case n=2 (1 3 or 6 10...) case n>2 create an array of n odd numbers (1, 3,...,2n-1), add 2 to the last element to max-min=2n array will become (1,3....2n+1) (1+3...+2n-1) = n^2 then the sum of the above array is n^2+2 (max-min)^2=4n^2. the missing part of the above array is 3n^2-2 add the first and last elements of the array 3*n-1 and the elements between the 3*n we get the required array
 » 2 months ago, # | ← Rev. 2 →   0 For problem E, I have doubts related to the sample input. in the question for the sample row=2 col=3 hour=4 1 0 - 1 -1 -1 2 it's mentioned that the following is the configuration. Can anyone tell me how this configuration is reached?For the first sample, this is a possible configuration for the clocks: 1 0 3 0 3 2 Any help will be appreciated. Thanks.
•  » » 2 months ago, # ^ |   0 Perhaps you are misunderstanding the problem. The problem is about counting the number of ways to replace each of the $-1$s with integers in the range $[0, h - 1]$ such that the configuration is solvable.
 » 2 months ago, # | ← Rev. 2 →   0 In D just write numbers from 1 to n ,then increase n by (n-1) ,then see how much more required to get (max-min)^2 ,let it be K so first add K/n in all numbers ,but there is till k%n left but that's not a prblm,just add it to the second last number and it won't create collision and remove distinction as at the beginning we freed upto n-1 spaces by increasing last number (n) by n-1 XbirCode of My Solution
 » 7 weeks ago, # |   0 Easy Solution for problem Dhttps://codeforces.com/blog/entry/109416?#comment-975682
 » 7 weeks ago, # |   +5 Nice B question. Nicely explained, good approach.
 » 7 weeks ago, # | ← Rev. 4 →   0 Alternative approach to problem E:Set up nxm bipartite graph, G. There is an edge from ith LHS vertex to jth RHS vertex of weight w iff there is a clock at (i, j) with value w. An edge also exists in the opposite direction with weight -w. Set up UFDS for G as well.Perform dfs on G instead using the same logic of finding contradicting modulos. If so, just output 0.Now iterate through all pairs in G, if ith LHS vertex isn't already in the same UFDS set as jth RHS vertex, there are exactly h possible clocks you can now insert at cell (i, j), then union these two sets.