### GlowCheese's blog

By GlowCheese, 6 weeks ago,

1993A - Question Marks

Hint
Solution
Code (python)

1993B - Parity and Sum

Hint 1
Hint 2
Solution
Code (python)

1993C - Light Switches

Hint 1
Hint 2
Solution
Code (C++)

1993D - Med-imize

Hint 1
Hint 2
Solution
Code (C++)

1993E - Xor-Grid Problem

Hint 1
Hint 2
Solution
Code (C++)

1993F1 - Dyn-scripted Robot (Easy Version)

Hint 1
Hint 2
General idea
Solution
Code (C++)

1993F2 - Dyn-scripted Robot (Hard Version)

Solution
Code (C++)
• +208

 » 5 weeks ago, # |   +7 Wow really fast editorial thank you
 » 5 weeks ago, # |   +8 D is cool
•  » » 5 weeks ago, # ^ |   0 agree although i didn't solve it
 » 5 weeks ago, # |   +15 thanks for fast editorial
 » 5 weeks ago, # |   +6 can someone explain C
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +12 Realize that all the chips are activated after the max(a_i). Let's call the interval corresponding to this max time as interval I, and the chip corresponding to it as chip i. So, since the entire pattern of the intervals being on/off is periodic, we know that there is nothing special (i.e. different) that happens later (after interval I). So, we know that, if the intervals all overlap at some point, it will happen in this first occurrence of chip i being on, over interval I. So, we can just maintain the intersection of the ON intervals (within I) across all the chips, using a high and low. If we end the intersection with a valid interval, the answer is the earliest time in that interval, otherwise the answer is no.
•  » » » 5 weeks ago, # ^ |   +9 C was Easy but not so Easy
 » 5 weeks ago, # | ← Rev. 2 →   +19 It's so refreshing to see all the participants solving the contest I'd tested.Thank you GlowCheese for inviting me to become a tester.
 » 5 weeks ago, # |   +3 Thanks for the Editorial The problems are really fun :D
 » 5 weeks ago, # |   0 can we use binary search for problem C ? :)
•  » » 5 weeks ago, # ^ |   0 No, it's not a linear function :D
•  » » 5 weeks ago, # ^ |   0 Yes, I used it in my solution
•  » » » 5 weeks ago, # ^ |   0 what did you use for the decision making in your binary search approach?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 I just found that if the answer exist, all the lights will be turned on somewhere in the range [mx ; mx + k — 1], where mx is the biggest element in the array. So I used binary search to find for each element in the array the nearest minute (z) where at the minute z the current element will be turned on and the range [z ; z + k — 1] is intersect with the range [mx ; mx + k — 1]. and if the intersect exist for all elements then the answer exist and it is the first point of the range resulting from the intersections. I hope this is helpful.
•  » » » » » 5 weeks ago, # ^ |   0 Hey Sandman10,How are you ensuring that you are only checking for even numbers, Like ai, ai + 2*k , ai + 4*k, because light will be ON only on even points.For doing so we need to dofor (ll i = 0; i <= 1e9; i += 2) { arr.pb(i); }and this will result in MLE.
•  » » » » » » 5 weeks ago, # ^ |   0 Exactamento!
•  » » » » » » 5 weeks ago, # ^ |   0 u dont need to, since every segments of length k, with the leftmost point congruent to a[i] modulo 2*k, which means u only need to care about the remainder of every a[i], divided by 2*k (and of course, the largest value in the array)
•  » » » » » 5 weeks ago, # ^ |   0 Honestly i feel like its not required. Implementing BS in that is like giving the TC extra logn factor to deal with instead we can just divide the distance from max(a) to a[i] by k and get the range for intersect based in the parity easily. I mean like ur solution is correct and u avoided the mathematical calculations successfully by integrating BS in ur solution but the TC increases by some multiple.
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   0 Problem C was really funny.. thx :)
•  » » 5 weeks ago, # ^ |   0 You're welcome ;)
 » 5 weeks ago, # | ← Rev. 2 →   -28 Really great problems with nice observations, why is the editorial getting downvotes ? Is it because you guys are mad not able to solve the problems ?
•  » » 5 weeks ago, # ^ |   -19 Bro ur post is also getting downvoted!! Funny to see it.
•  » » » 5 weeks ago, # ^ |   +1 Ahem ahem
 » 5 weeks ago, # |   +20 I enjoyed solving D and E very much :) which is quite rare for a div2 roundThanks a lot
•  » » 5 weeks ago, # ^ |   +9 I think you should have lowered constraints in E though since my and probably many others n^4 2^n did not pass, and the optimization is just boring
•  » » » 5 weeks ago, # ^ |   0 $O(n^4 2^n)$ still passes though as I set the time limit pretty high (5 times how intended solution should run), but you may find some luck to get it AC
•  » » » » 5 weeks ago, # ^ |   0 Take a look at submissions, you will find a lot of TLEs.5x from n^3 2^n doesnt mean it will pass since going purely theoretically, its 15xMy n^4 * 2^n took 13s on cf custom invo. I removed the factor of n to get it to 1.6s
•  » » 5 weeks ago, # ^ |   0 I'm glad that you liked it :D
 » 5 weeks ago, # |   0 Wow fast Editorial
 » 5 weeks ago, # |   0 wish i solved D, but really fun contest nonetheless!
 » 5 weeks ago, # |   -56 algorithm contest -> ❌ math contest -> ✅
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +36 It was never supposed to be an algorithm contest, this is a thinking and problem solving contest. Also which problem exactly needed math?
•  » » » 5 weeks ago, # ^ |   -54 "it was never supposed to be an algorithmic contest" what a stupid thing to say
•  » » » » 5 weeks ago, # ^ |   +1 It's true, though. Contests are all about entertaining those who like to solve problems for fun. Some like algorithms, while others like weird tricks. Thus, contest creators must find the perfect balance to entertain both groups.
•  » » » 5 weeks ago, # ^ |   -16 The number of using the word "mod" in the solution was more than the total number of questions.
•  » » » » 5 weeks ago, # ^ |   +22 That is because it can be modeled in mathematical terms and that way the solution is easier to understand, it doesn't mean the solution is math based.
•  » » » » » 5 weeks ago, # ^ |   -12 how can you say C is not math?
•  » » » » » » 5 weeks ago, # ^ |   0 It's not, in the editorial it is modeled mathematically to be precise. This was my thinking process: If there is a possible time, it will be in the first turned on interval of the maximum $a[i]$. So i will bring every $a[i]$ so that it intersects with the maximum $a[i]$ and update the left and right bound of the answer.
•  » » » » 5 weeks ago, # ^ |   0 and still some of those can be solved without mod at all. C has mod in editorial but can be solved with a different approach that doesn't require mod
•  » » » » » 5 weeks ago, # ^ |   0 Yes, I use some trick with the brain to solve it without mod 274409368, but still you need some good insight for the problem just to solve it :3
•  » » » » » » 5 weeks ago, # ^ |   0 I also had the same approach. Honestly, I couldn't still understand how people could think of a solution involving modulus during the contest itself. Great thinking
•  » » » » » » » 5 weeks ago, # ^ |   0 Actually, people choose to use modulus is it's better to understanding the problem in that way, and you can prove it's correct while my approach may get hack if there is an edge case :3
 » 5 weeks ago, # |   0 Thanks for fast editorial!
 » 5 weeks ago, # |   0 Ah, I should've been able to do B. Don't know where my code went wrong. Anyway, Thanks for the editorial.
•  » » 5 weeks ago, # ^ |   0 in your code, whenever the "if(store < a)" is true, you can just print out the amount of even numbers+1. the solution will always be either 0, the amount of even numbers, or the amount of even numbers+1.
•  » » » 5 weeks ago, # ^ |   +1 Yes, I understood my mistake. I should've thought of this. Thanks for replying, buddy!
•  » » » 5 weeks ago, # ^ |   0 hey could you pls tell why my code for B is wrong?
•  » » » » 5 weeks ago, # ^ |   0 in case of the "if(o>e)" giving false, your code doesnt really handle it properly. whenever that if returns false, you can just break out of the for loop and print p+1, where p represents the amount of even numbers. Otherwise if that if never returns false, you can just print p. Hope this clears it up a bit
•  » » » » » 5 weeks ago, # ^ |   0 sorry again but if possible, could you pls provide a test case where my code fails
•  » » » » » » 5 weeks ago, # ^ |   0 1 3 1 2 6Your code outputs 4, while the answer is 6. Thats because you go from the smallest even to the largest even number. Which is correct, unless the if statement ever returns false. In that case, you can always break out of the for loop, and just p+1.
•  » » » » » » » 5 weeks ago, # ^ |   0 aight got it thank you so much!
•  » » » » » » » » 5 weeks ago, # ^ |   0 btw i made a mistake for some reason, i meant to say the answer is 3, sorry.
•  » » » » » » » » » 5 weeks ago, # ^ |   0 yea I saw that lol that's ok
 » 5 weeks ago, # |   0 Nice Solutions.
 » 5 weeks ago, # | ← Rev. 2 →   +9 The solution for F1 (and F2) is really elegant and tricky! I enjoyed (attempting to) solve the problem very much. Hope to see more of such problems.
 » 5 weeks ago, # |   +7 Editorial is high quality. Nice problems too, been a while since I've seen a moving interval one (C).
 » 5 weeks ago, # | ← Rev. 3 →   +1 274419542 why i didnt get TL for C task? Its O(n*k)
•  » » 5 weeks ago, # ^ |   0 you got uphacked though
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I think sorting is the difference try without sorting and it will get TLE
 » 5 weeks ago, # |   0 I don’t understand why binary searching works on D They aren’t even checking whether the bs element is present in array or not?
•  » » 5 weeks ago, # ^ |   +1 You are checking if the answer can be at least mid.
 » 5 weeks ago, # | ← Rev. 2 →   0 Can someone please explain in problem D if I am doing binary search on median and getting that number "mid" should be in middle, how am I even able to check by dp if I can remove segments accordingly, please explain the check function in simpler terms. Thanks in advance!
•  » » 5 weeks ago, # ^ |   0 mid should not be in middle, it should be less than or equal to median. Means we are binary searching on the predicate: f(mid) -> is mid lying to the left of median? and we can do that by counting elements greater than mid, if they are greater than half the size of array, then it will return true.
 » 5 weeks ago, # |   +1 in C, I did linear search in the range max(array)to max(array)+k and got the answer. the check function i used for every numbers in the range is- ~~~~~ functioncheck=[&](int t){ for(int i=0;i
•  » » 5 weeks ago, # ^ |   0 very weak tests i think, i saw some O(n*k) solution got hacked, so i think that its just really weak tests.
 » 5 weeks ago, # |   0 E is really a good problem
 » 5 weeks ago, # |   +1 Why, in problem C, the solution with time complexity O(nk) not giving TLE?I first submitted O(nk) solution (274384802). Then later, submitted O(n) solution (274394074).After the system testing, I again submitted my O(nk) solution just to check if it is passing or not, and it got passed. I think the test cases were quite weak for Problem C
•  » » 5 weeks ago, # ^ |   0 just submitted your code and got a TLE274432933this is not a contest but rather a clown fest
•  » » » 5 weeks ago, # ^ |   0 the first O(nk) just pass the pretest you are not a pupil but rather a idiot
•  » » » » 5 weeks ago, # ^ |   +2 274425542Say that again :clown:
 » 5 weeks ago, # |   0 B- Parity and Sumcan someone please help me understand why my solution was WA on test case 2C++ solution: #include using namespace std; #define ll long long // Code By VibhuGodson int main () { ios::sync_with_stdio(false); cin.tie(nullptr); ll t=1; cin>>t; while(t--){ ll n; cin>>n; vectorevn; ll mxod=-1; ll x; for(ll i=0;i>x; if(x%2) mxod=max(mxod,x); else evn.push_back(x); } sort(evn.begin(),evn.end()); ll ans=0; if(evn.size()==0 or evn.size()==n){ cout<mxod){ mxod=2*i+mxod; ans+=2; }else{ mxod = i+mxod; ans++; } } // cout<<"---------------"; cout<
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 It's was my first try too. The problem in this solution is that sometimes choose the biggest even number from evn, it's better than a smaller one. Because if you take $a > b$, which is at the end of evn, then you increase mxod and now mxod = mxod + max_elemen(evn), so now mxod is in 100% of cases is greater than any evn and you don't need anymore ans += 2
 » 5 weeks ago, # |   0 What is the dp state in the editorial of problem D?
 » 5 weeks ago, # |   +7 As usual, thanks to the authors for this round ! Here is my advice about the problems: AGood problem, not random lcm problem but not A + B either. BI feel like it's very hard to come up with a good B, this one is perfect imo. CI guess it does the job as a C. The problem felt a bit weird though. Also, there are way too many solves for C so maybe it could be better ? idk DGreat great great problem! It is a little bit of a "troll" problem though but the idea is cute and interesting. It felt enlightening. Btw, I don't think it is too hard for D EI did not think more than 10mn about it but wtf? This looks super cursed (but the problem might be cool)It seems that E is a bit too hard though (looking at the solve count).
 » 5 weeks ago, # |   0 In Problem D they did not specify that sum of k is less than 5e5, so after I got pretests accepted with O((n + k) * log(1e9)) per testcase solution, I assumed that it whould fail the system test because of the Time Limit. I fixed and resubmited the solution with O(n * log(1e9)) time complexity and it passed the system tests, but it seems like there was not any test case in the system tests that results in a TLE. So if anybody wants to get free hacks for problem D, they can easily construct a testcase where t = 1e4 and n = 1, k = 5e5 for each test case.
•  » » 5 weeks ago, # ^ |   +5 If k>n, the solution is trivial. O(n*log(n)) if you sort the array for finding the median
 » 5 weeks ago, # | ← Rev. 3 →   0 For D. My solution https://mirror.codeforces.com/contest/1993/submission/274431244 is giving RTE on the following test case:1 1 500000 3169420But when I am running it locally it is working just fine. Can anyone please help me?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +3 for(int i = 0 ; i < k ; ++i){Your solution looped $k$ independently from $n$, and will fail if $k > n$.
•  » » » 5 weeks ago, # ^ |   0 Thanks a lot!
 » 5 weeks ago, # | ← Rev. 4 →   0 I solved C, in a slightly different way1) If the answer exists it's always going to be from (max(a), max(a)+k-1). (Observation from provided test cases).2) so we add (2*k*r(some integer) to each element a[i] in place, such that a[i]+2k is just greater than max(a).(2k because in every 2k intervals the light will be on)3) we need to find two things if(max(a)-min(a)>=k) the answer will be -1, else the answer is max(a).
•  » » 5 weeks ago, # ^ |   +1 this ecxactly what i did, more easy to think and code,just greedy, no math no algorithm
•  » » 5 weeks ago, # ^ |   0 thanks man. I also got some intution like this but was unable to do. In the example testcases it can be seen that the output was close to the max(a). So we didn't need to go very far checking different numbers but just a observation was needed.
 » 5 weeks ago, # | ← Rev. 2 →   0 Correct me, if I'm wrong, but shouldn't we choose both n+1th row and m+1th column at the same time to correctly calculate R and C?I mean, e.g. when calculating C, we need at the same time remove one row (to look for the best solution on n remaining rows) and remove one column (because otherwise distance between rows cannot be calculated correctly). Hence complexity should be somewhat $O((n+1)(m+1) \cdot ((m+1)^22^{m+1} + (n+1)^22^{n+1}))$ or $O(n^42^n)$
 » 5 weeks ago, # | ← Rev. 4 →   0 I think the editorial for problem B is for another version of the problem where we can make operations on numbers having the same parity ? You could fix it by just removing the part talking about that x)Btw it's quite cool that the editorial was writen that much in advance!
 » 5 weeks ago, # |   0 Guys i have a doubthttps://mirror.codeforces.com/contest/1993/submission/274430880Im getting wrong answer on the above submissionbut my other solution (https://mirror.codeforces.com/contest/1993/submission/274433114) is getting accepted why? i understand the logic of the 2nd one but whats wrong with my first submission?
•  » » 5 weeks ago, # ^ |   0 Consider test case with n = 3, a = [1, 2, 6]. Your algorithm would first set maxodd to be 1, then it would use 2 operations to turn 1 -> 3 and 2 -> 5, then 2 more operations to turn 5 -> 11 and 6 -> 17. But in an optimal answer you never need to use 2 operations on an even number more than once, so the actual answer is 3 and not 4.
•  » » » 5 weeks ago, # ^ |   0 Thanks a lot man, but now you made me feel stupid T_T
•  » » 5 weeks ago, # ^ |   0 If maxodd is less than v[i], you should add the largest even number to maxodd, instead of v[i]. Adding v[i] may lead to extra operations.
 » 5 weeks ago, # |   +8 There's typo in editorial of D, it should be: $b[i]=1$ if $a[i]≥x$ right?
 » 5 weeks ago, # |   +12 Funny thing is: there is a recent video with 3blue1brown which mentioned general idea from F (they called it quite popular but i'm not really into geometry so idk)With that video in mind it was much easier to think up the solution
 » 5 weeks ago, # | ← Rev. 2 →   0 In problem B you must take numbers such that have distinct parities. So you can remove even + even & odd + odd options from editorial. EDIT: I'm a bit late to tell it first. I thinkA, B, C are OK but gap between C & D is not OK.
 » 5 weeks ago, # |   -11 ~~~~~~~~~~~~~~~~~~~ import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0) { int n=sc.nextInt(); int []a=new int[n]; for(int i=0;i0){ olarge=max; } if(count1==n || count2==n) { System.out.println("0"); } else{ if(olarge>esmall) { a[m]=max+esmall; max=a[m]; count=count+1; } else { a[j]=max+esmall; max=a[j]; a[m]=max+esmall; count=count+2; } for(int k=0;ka[m]) { a[m]=a[k]+a[m]; a[k]=a[m]+a[k]; a[m]=a[k]; count=count+2; } } System.out.println(count); } } }~~~~~~~~~~~~~~~ can someone please tell me what is wrong in this only the last test case of test case 1 is showing wrong answer
 » 5 weeks ago, # |   -11 1) why the fuck is not k <= n in problem D, it makes no sense 2) why do tests not have k = max, and 1e4 tests???? How do you miss that in the tests. My solution uses an array of k size and passeed the initial tests https://mirror.codeforces.com/contest/1993/submission/274400595
•  » » 5 weeks ago, # ^ |   +14 Wdym makes no sense? Makes enough sense to troll some careless coders :D
•  » » » 5 weeks ago, # ^ |   -11 Troll didnt even work due to weak tests :)
 » 5 weeks ago, # |   0 Problem D might be my favourite problem ever.
•  » » 5 weeks ago, # ^ |   0 its very common algorithm in Vietnam.If you can do it, your level is equivalent to a fairly good high school student in Vietnam
•  » » » 5 weeks ago, # ^ |   0 What's the algorithm called?
•  » » » » 5 weeks ago, # ^ |   0 its calling binary search on result, that you find the minimal result can be, and the maximum result can be, and binary search on it with a bool check(), remember that the answer must be linear, that is, if one position is satisfied, then the whole in front or behind it must also be satisfied. it is effective for problems that require finding something that is largest or smallest, or the answer involves something that is linear.
•  » » » » » 5 weeks ago, # ^ |   0 I guess binary searching on the result wasn't the tricky part for me, it was more translating the given array into 'b' where 'b[i]' is if the element is greater than the desired median or not.
•  » » » » » » 5 weeks ago, # ^ |   0 bro you missed the check for correct parentheses problem XD
 » 5 weeks ago, # | ← Rev. 2 →   0 Can anyone help me figure out what the time complexity is for my solution to D?I used recursion with memoization to solve for the answer. Let the initial size of the array be N. I start with the full array, and using recursion I get the answer for every possible array of size N-K, and so on. I store the maximum answer. I keep doing that until the size of the array is smaller than or equal to K. Then I find the median of the array. I have an map which stores the indices that I have removed. I'm thinking the time complexity is O(N^2log(n)). My reasoning is that there are ~ N^2 subbarays of different sizes, and the sort takes log(N) time. Is that correct.This is my code: https://mirror.codeforces.com/contest/1993/submission/274435465
 » 5 weeks ago, # |   0 B Video Editorial : https://youtu.be/xTb58OEZnJMC Video Editorial : https://youtu.be/6xtmLO43mD4
 » 5 weeks ago, # |   0 Can anyone please tell me where I am going wrong in this code I am always taking the maximum odd number and updating it whenever required and storing the value in ans variable. 274393002
 » 5 weeks ago, # |   0 Problem D was cool. Approached the problems in a million ways. But didn't think in this way.Was thinking about BS + some sort of greedy Also thought about some DPBut nice technique of reducing this problem only to a simple dp sum problem.
 » 5 weeks ago, # |   0 in D it should be x<=a[i],right?
 » 5 weeks ago, # |   0 Was C that easy? I am unable to find any clue to solve even after seeing the comments and editorial
•  » » 5 weeks ago, # ^ |   0 it wasnt that hard, but also alot of O(n*k) solutions passed for some reason, because of really weak tests.
 » 5 weeks ago, # |   0 HelloCan someone help me with my solution for C? I'm getting wrong answer on test 2 on the 2003rd test, so there's an off by one error somewhere. Here's the link to my submission: https://mirror.codeforces.com/contest/1993/submission/274445861I take the time of the light being installed as lowerbound and that time + k as the upperbound, and I set the lowerbound in an array to be +1 and the upperbound as -1 However if the lowerbound to upperbound contains 2k in the middle, then it loops around after the mod, so i set the lowerbound to +1 and the 0th index to +1 and the new upperbound to -1 to account for this loop around Then I add in the array as I go until I find the first index that has the value n (meaning all lights are on at this moment) and at the end I check if index 0 was an answer, then I shift the answer to put it after max(a)
 » 5 weeks ago, # | ← Rev. 3 →   0 why is this code for problem C not giving correct output on codeforces compiler? Link to Submissionwhile same code gives correct output on my local vscode and also on codechef online c++ compilerfor the 1st test case it is giving correct output as given in the problem My Code#include #include #include using namespace std; using namespace __gnu_pbds; #define int int64_t #define fl(i, a, b) for (int i = a; i < b; i++) #define rl(i, a, b) for (int i = a; i >= b; i--) #define all(s) s.begin(), s.end() #define uniq(v) (v).erase(unique(all(v)), (v).end()) #define mem1(a) memset(a, -1, sizeof(a)) #define mem0(a) memset(a, 0, sizeof(a)) template using oset = tree, rb_tree_tag, tree_order_statistics_node_update>; // os.order_of_key(k) the number of elements in the os less than k // *os.find_by_order(k) print the k-th smallest number in os(0-based) int mod = 1000000007; int mod2 = 998244353; void solve() { int n, k; cin >> n >> k; vector a; fl(i, 0, n) { int num; cin >> num; a.push_back(num); } sort(a.begin(), a.end()); int mx = a[n - 1], mn = a[n - 1] + k - 1, f = 0; map> mp; fl(i, 0, n) { mp[a[i] % (2 * k)].push_back(a[i]); } fl(i, 0, k) { if (mp[i].size() > 0 and mp[i + k].size() > 0) f = 1; } if (f) { cout << -1 << endl; return; } vector cnt(4 * k + 5, 0); fl(i, 0, n) { int diff = a[n - 1] - a[i]; int num = a[i] + (diff / (2 * k)) * 2 * k; if (num + k < a[n - 1]) num += 2 * k; cnt[num]++, cnt[num + k]--; } int ans = -1; for (int i = a[n - 1] - k; i <= a[n - 1] + k; i++) { if (i > a[n - 1] - k) cnt[i] += cnt[i - 1]; if (cnt[i] == n and i >= a[n - 1]) { ans = i; break; } } cout << ans << endl; return; } main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int tc = 1; cin >> tc; while (tc--) { solve(); } } 
•  » » 5 weeks ago, # ^ |   0 did you try different c++ compilers on codeforces?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 yes, I tried 14, 17 & 20. none of them workedplease let me know if it is working on your pc
•  » » » » 5 weeks ago, # ^ |   0 yep, its working on my pc. its something weird with the codeforces compiler, very unlucky.
•  » » » » » 5 weeks ago, # ^ |   0 oh, okay thank you
 » 5 weeks ago, # | ← Rev. 2 →   0 I solved C in an another way. As the answer should be at least the maximum number of the array a and every 2k minutes the condition of the light in the apartment is repeated, I decided to build a segment tree, where in each segment of time I save one of three numbers:0 — means during this segment of time there's no time when all of the lights in the apartment are on1 — means during the whole segment of time all of the lights are on2 — means during a part of the segment of time all of the lights are onThe information in the segment tree is updated by running through the array and performing some mathematical operations. Including that the total time which we are looking through is 2k, the time complexity of the algorithm is O((n + k) * logk).Code: 274409062
 » 5 weeks ago, # |   0 A very intuitive solution for C:We can see that our lights are on only when minute / k is even. The first k minutes the lights are on. And the second k minutes they are off. This is applicable for every light. And if a lower light cannot reach a higher light within higher light's first appearance, than it cannot ever reach it. (You can see it using pen and paper). Now, this problem comes down to is it possible that all the lower minute lights reach the highest minute light (last one) within it's first appearance? We can find it out by (diff / k). "diff" here is the difference between lower and highest minute lights. if the result of this is even, than it means the next k will be odd. Thus we get our L is equal to the starting of highest minute and R is equal to where the next k ends (k * (diff + 1)). Now, if the result of the division was odd, then our L will be our current minute + k + 1. by adding k + 1 another time we get to our minutes where our lights are on and our R will be end of the largest minute light.Now we will check if all our segments intersect, We will do it by checking if our maximum of L is lesser than minimum of R. If it is, then our result will be L, otherwise -1. link to my submission
 » 5 weeks ago, # |   0 In C we also could have taken everything mod 2k and added 1 everywhere light is on and subtracted 1 everywhere light is off using prefix sum array . Now we had to check at which indices mod 2k val is equal to n means all the ranges intersect.
•  » » 5 weeks ago, # ^ |   0 that's what I was trying to do: Link to Submission
•  » » 5 weeks ago, # ^ |   0 my first thought was prefix sum array, but in the end i didnt solve it like that. very nice solution
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 also you can do this range update thing to get the intersection using a map so you don't even need mod 2k thing you can just work with the original intervals
 » 5 weeks ago, # |   0 Thank you for the fast editorial!
 » 5 weeks ago, # |   0 can anyone help me point the mistake in my B solution ?
•  » » 5 weeks ago, # ^ |   0 In the case maxodd is less than ai we should do two operations and add the largest even number to it so that we can add all remaining even numbers in one operation each
 » 5 weeks ago, # | ← Rev. 2 →   0 Here is my submission for problem C it is just implement 274378520
 » 5 weeks ago, # | ← Rev. 2 →   0 Please help me figure out what is wrong with my code of problem C 274418452. By using binary search i am trying to find out the current active range, Here active range is the range where all my bulbs are on, My assumption is that i will have this active range always between [max,max+k-1].UPD: Figured out what was going wrong, there was an integer overflow for k>500 because i used r=1e18. here is the updated AC code 274529145
 » 5 weeks ago, # |   0 This contest is very inspiring, I love it.
 » 5 weeks ago, # |   0 Can someone tell if the problem C can be done with binary search on answer or is it not possible to do it by binary search on answer i tried but could not get a correct solution.??
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   0 Anyone who is looking for binary search solution for C. Can see my solution(if it helps)..https://mirror.codeforces.com/contest/1993/submission/274476133
 » 5 weeks ago, # |   0 I think there's an easier solution for problem D. Instead of trying to leave as many large elements as possible, we try to leave as few small elements as possible. to prevent the resulting sequence becoming empty, we define dp[i][j] (0 <= i <= n, j = 0 or 1) as the least number of alive elements less than x. refer to my code for dp transition. https://mirror.codeforces.com/contest/1993/submission/274378351
 » 5 weeks ago, # |   0 Can someone explain the dp in problem D in more detail?What does the state represent?Why are the transitions the way they are?Thanks in advance.
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I have an alternate DP definition. A subsequence is called good if the gap between each consecutive elements is divisble by $k$.Define $dp[len]$ to be the maximum sum of a good subsequence of length $len$. Suppose you append an element $a[i]$ to the array. How do you refresh the DP? The only subsequence that we haven't considered are the ones ending at $i$. If the subsequence ends at $i$, there are exactly $i$ elements to the left. Hence, $i\%k$ elements would remain after the operation. Therefore, if a subsequence ends at index $i$, it has to have length equal to $len = 1 + (i\%k)$. Therefore, we only need to refresh $dp[len]$ from $dp[len - 1]$.The answer would be $dp[r]$ where $r$ is the number of elements that you want to retain at the end. vector dp(k + 1, -inf); // dp[len] is the maximum sum of a good subsequences of length len. dp[0] = 0; for (int i = 0; i < n; i++) { // If the subsequence ends at i, then its length is predetermined. // There are i elements to the left. From these elements, you // need to remove blocks of size k. int prev_cnt = i; int len = 1 + prev_cnt % k; dp[len] = max(dp[len], dp[len - 1] + a[i]); } return dp[req_len]; Full Code
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Meaning at each position i%k, you only take the one element with the highest value, right?
•  » » » » 5 weeks ago, # ^ |   0 Yes, correct.
•  » » » » » 5 weeks ago, # ^ |   0 Oh thank you very much
•  » » » 5 weeks ago, # ^ |   0 Wow, it's so useful, thanks a lot! I think you broke my mind
 » 5 weeks ago, # |   0 Excellent editorials for D and F1, learnt a lot
 » 5 weeks ago, # |   0 Seems a typo in solution for D: $b[i]=1$ if $x\ge a[i]$, otherwise $b[i]=−1$.if $sum(b)>0$, then the condition $x\le med(a)$ is satisfied. Should it be $b[i]=1$ if $x\le a[i]$?
•  » » 5 weeks ago, # ^ |   0 Yeah you're right. I've fixed the typo in the solution. Thank you for pointing that out!
 » 5 weeks ago, # |   0 Why is my solution for problem C wrong? Someone help! 274434816
 » 5 weeks ago, # | ← Rev. 2 →   0 Can someone please explain C, why my code fails. It says expected -1 and getting some value on some test case.My logic — sorted the vector, then I took the maximum value The answer has to be in the range [maxValue , maxValue + (k-1)] .... so I made a range using variables l and r Iterated over all the remaining elements of the vector Calculated the overlapping segments (either the segments overlap from left, or right, or whole) Shirinked my segment by updating the Values of l and r If there is any segment that doesn't overlaps at all => (count << -1;) not possible case Else after the loop ends => (cout << l;) as it will be the smallest possible value in the segment.
•  » » 5 weeks ago, # ^ | ← Rev. 8 →   0 Problem C solution  int m = *max_element(all(a)), l = m, r = m + k - 1; for ( auto i : a ) { int g = (m + k - i - 1) / (2 * k), h = i + 2 * k * g; l = max(l, h), r = min(r, h + k - 1); } 
 » 5 weeks ago, # |   0 Hi Can anyone help me understand why this line :-  for k in range(2*K,3*K): imos[k%(2*K)]+=imos[k]   imos=imos[:2*K]  was added in this solution — 274364071
 » 5 weeks ago, # |   0 I don't understand how I can be sure I deleted enough [n/k] subarray in DP in problem D
 » 5 weeks ago, # |   +4 A solution to F2 withou CRT: First, calculate the mininum $i_x,i_y$ such that $i_xx_n \equiv -x_j \pmod {2W},i_yy_n \equiv -y_j \pmod {2H}$. We could use exgcd to solve this. Second, calculate the mininum $p_x,p_y$ such that $p_xx_n \equiv 0 \pmod {2W},p_yy_n \equiv 0 \pmod {2H}$. At last ,the problem is calculate how many $x \in [0,k-1]$ satisfiying $x = r_xp_x + i_x = r_yp_y + i_y$ ($r_x,r_y$ is any non-negative integers). This is the same as CF710D, we can solve it using exgcd too. Thus this problem is solved in $\mathcal O(n \log V)$.
•  » » 5 weeks ago, # ^ |   0 orzBTW do you have a submission implementing this idea? Due to my skill issue I'm struggling to implement the exgcd part.
•  » » » 5 weeks ago, # ^ |   0 274418932the function int work() is copied from a random submission from CF710D :)
 » 5 weeks ago, # |   0 problem B, why the case only happens most once that t > s ?
 » 5 weeks ago, # | ← Rev. 2 →   +6 It would be better if it had been guaranteed that $k \leq n$ in D.
 » 5 weeks ago, # |   0 https://mirror.codeforces.com/contest/1993/submission/274528860The tc of above solution is 0(n*log(1e9)) but it is giving TLE for Question-D.Please help!
 » 5 weeks ago, # |   0 Can anyone explain, why in D, we are having to separately consider the case when I % k == 0,This is my code as I don't understand where it goes wrong: Code:#include using namespace std; using i64 = long long; void solve() { i64 n, k; cin >> n >> k; vector a (n); for (i64 i = 0; i < n; ++i) cin >> a[i]; auto check = [&] (i64 m) -> i64 { vector dp (n + 1); for (int i = 1; i <= n; i++) { dp[i] = dp[i - 1] + (a[i - 1] >= m ? 1 : -1); if (i >= k) { dp[i] = max(dp[i - k], dp[i]); } } return dp[n] > 0; }; i64 l = 0, r = 1; while (check(r)) r *= 2; while (r - l > 1) { i64 m = l + (r - l) / 2; if (check(m)) l = m; else r = m; } cout << l << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); i64 T; cin >> T; while(T--) solve(); return 0; } 
 » 5 weeks ago, # |   0 Very educational round. Problem D and Problem F1 are interesting. Tricks used in Problem D amazed me. Apart from that, the editorial explains clearly.
 » 5 weeks ago, # | ← Rev. 3 →   0 Small typo: in the editorial for F1,"Let's call $t_k=(x_k,y_k)$ how much the robot moves (in direction) after executing the first $i$ commands of the script."should be"Let's call $t_k=(x_k,y_k)$ how much the robot moves (in direction) after executing the first $k$ commands of the script."Doesn't impact the solution that much though. Pretty elegant and cool idea, worthy of an ARC or even AGC.
 » 5 weeks ago, # |   0 Problem D is very impressive, It's nature is very interesting, I need more like this.
 » 5 weeks ago, # |   0 Hello! Can someone please help me understand how the check function in D is monotonic? I get that it will be monotonic when not deleting segments, but I'm not exactly sure how it would be monotonic when we consider the fact that we are deleting segments.Thanks for everything, really appreciated :)
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 When we check if a $x$ is less than or equal $med(a)$ after deleting segments, we want $sum(b)$ to be as large as possible. Note that $b[i] = 1$ only if $a[i] \ge x$; that means if $x_1 > x_2$ and $b[x_1] = 1$, then $b[x_2] = 1$ also, which leads to $sum(b)_{x_1} \ge sum(b)_{x_2}$. The smaller $x$ gives the larger $sum(b)$ so yes, the check function is monotonic!
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for your answer! I am beginning to understand now! But still I'm unsure as to how you can be sure that at the end, hi will be the number such that sum(hi) is precisely 1 (if (n-1)mod k + 1 is odd) and 2 (if (n-1)mod k + 1 is even), because ultimately hi should be the highest possible median.
•  » » » » 5 weeks ago, # ^ |   0 That is how I usually implement binary search. Remember in the code I wrote: if (check(mid)) { lo = mid + 1; } Which means mid can be the median we're finding but later we set lo = mid + 1. In the end, lo <= hi is no longer true, which means hi = lo - 1 = (med(a) + 1) - 1 = med(a). That's it ;)
•  » » » » » 5 weeks ago, # ^ |   0 Thank you!
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Oh and just one last question :) How do we ensure that at the end, we have only considered a total of (n-1)modk + 1 many +1's and -1's? Thank you for everything!
 » 5 weeks ago, # |   0 Can someone tell me how to solve problem E in O(n^3 2^n)enumerate the deleted line and row: O(n^2)let f[i][j] be the answer with bitmask i, last choose is j, dp in O(n^2 2^n)total: O(n^4 2^n)how can I do it faster?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Make a matrix such that matrix[x][y] = the answer if you don't use the xth row and yth column. Final answer is obviously the minimum element in this matrix.Calculate the optimal sum between horizontally adjacent elements for each x and y. You do this by looping over which row you don't use, then do bitmask dp on the columns. This is n^2 * 2^n for each row, so n^3 * 2^n total. After calculating the dp (dp[mask][last] = minimum horizontal differences such that you use the columns in mask and the last column is last), you update the matrix like this: let's say you are currently calculating the answer such that you don't use row rno. matrix[rno][c] += min(dp[mask with all ones except for c][last]) over all values of last.Then repeat for vertically adjacent elements. Thus you optimize from n^4 * 2^n to 2 * n^3 * 2^n.274629969 Hope this helps
 » 5 weeks ago, # |   +8 The solutions are excellent!!!!!!!
 » 5 weeks ago, # |   +8 E is really beautiful
 » 5 weeks ago, # | ← Rev. 3 →   -8 in problem B, i found something that i can't understand. lets see case [3, 2, 2, 8, 24]. then, array will be change like this3 2 2 8 24 maxodd = 3 -> initial value3 5 2 8 24 maxodd = 53 5 7 8 24 maxodd = 73 5 15 8 24 maxodd = 153 5 15 23 24 maxodd = 233 5 15 47 24 maxodd = 473 5 15 47 71 maxodd = 71so, minimum operation number will be 6. but, answer code says it is 5. also, i can't understand why solution code use "break;" when t > s (t = now even number, s = max odd number)this is valid when t > s only appears once in whole array. #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tc; cin >> tc; while (tc--) { int n; cin >> n; vector a(n); for (int i = 0; i < n; ++i) cin >> a[i]; // 최대 홀수 s ll s = -1; // 짝수를 저장하는 v vector v; for (ll x : a) { if (x % 2 == 0) v.push_back(x); else if (x > s) s = x; } // 짝수는 오름차순으로 처리한다. sort(v.begin(), v.end()); // 전부 짝수인 경우나, 전부 홀수인 경우 -> 조작할 필요가 없음. if (s == -1 || v.empty()) { cout << 0 << "\n"; continue; } // 일단 짝수 번 만큼은 조작이 당연히 필요함(최소 1회 조작, 최대 2회 조작) int ans = v.size(); for (ll t : v) { // 현재 짝수 < 최대 홀수 : 짝수 -> 홀수, 조작 1회(이미 count) if (t < s) s += t; // 현재 짝수 > 최대 홀수 : 조작 2회 필요. else { ans += 1; break; } } cout << ans << "\n"; } return 0; } this code is which i got AC in problem B. but, I think the answer code would be like this. #include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tc; cin >> tc; while(tc--) { ll n; cin >> n; ll count = 0, max_odd = 0; vector a(n), even; ll idx = 0; for(ll i = 0; i < n; i++) { cin >> a[i]; if(a[i] % 2 != 0) { max_odd = max(a[i], max_odd); } else even.push_back(a[i]); } sort(even.begin(), even.end()); ll size = even.size(); if(even.size() == 0 || even.size() == n) cout << 0 << "\n"; else { while(size) { if(max_odd > even[idx]) { count++; max_odd = max_odd + even[idx]; idx++; size--; } else { count++; max_odd = max_odd + even[idx]; } } cout << count << "\n"; } } return 0; } can anyone please explain why my code got WA on test 2. thanks for reading!
 » 5 weeks ago, # |   0 in $D$ it was a bit unclear to me how this $dp[i]$ ensures that the answer will be calculated only among all possible subsequences of length $(i - 1)$ $mod$ $k + 1$.since i didn't find any mention of this, that's how i explained it to myself:when $1 <= i <= k$ we can't delete anything so $dp[i]$ is the answer among all possible subsequences of length $i$ (which is just a prefix of length $i$)when $i = k + 1$ we now that we must delete segment of length $k$ to get length $1$ and $dp[i] = max(dp[1], b[i])$. thus we ensure that now length is $1$ and we kind of returning to case $1 <= i <= k$ because if $i = k + 2$ length will be $2$, when $i = k + 3$ length will be $3$ and so on
 » 5 weeks ago, # |   0 It seems like the official code for Problem D can be hacked.Specifically, let's consider the following input: 1 5 4 100 5 5 5 100 In the above example, the length of the original sequence is $5$ and the $k$ is $4$. Since the length of the operated sequence should be at least $k+1=5$, thus we should not perform any operation and the final sequence should be as same as the original one, which is $[100, 5, 5, 5, 100]$.Obviously, the median of such a sequence is $5$, but the official solution of Problem D will output $100$, which is wrong.
•  » » 5 weeks ago, # ^ |   0 Since the length of the operated sequence should be at least $k+1=5$, thus we should not perform any operation The length of the sequence is at least (and exactly) $k+1=5$.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for pointing out! I found that I misunderstood the problem...
 » 3 weeks ago, # |   0 E is really magic