Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By pikmike, history, 7 months ago, translation, ,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 problems and 2 hours to solve them.

The problems were invented and prepared by ZiXuan Yan RDDCCD, Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Hello Codeforces!

This week we have two new blog posts and a reminder of our Data Science Scholarship!

BLOG:

OUR SCHOLARSHIP

We are offering fully-funded international scholarships for exceptional tech specialists from around the world. Accelerate your career by becoming an industry expert capable of making key data-driven decisions that add value and drive innovation within tech industries.

Harbour.Space University has partnered with SCG, a leading business conglomerate in the ASEAN region, to offer exceptional tech specialists the opportunity to work and study in two of the most dynamic and vibrant cities in the world. Join our progressive two-year program based in Bangkok, with 6 of the 24 months in Barcelona, to develop the international mindset needed to accelerate your career and redefine how data drives the businesses of the future.

Tuition fee:

2 years | €45,800

Education:

3 hours of study per day | 15h per week

Work Experience:

4 hours of internship per day at SCG | 20h per week

Living Allowance:

€16,800 euros | €700 per month living allowance

APPLY HERE→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 twitch.tv_wookje 6 209
2 Tweetuzkokodayo 6 219
3 socketnaut 6 220
4 mango_lassi 6 280
5 LJFOO7 6 288

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Rian_5900 60:-3
2 blaction 13
3 Fyodor 14:-5
4 Wolfy626 11
5 bmm 11:-2
216 successful hacks and 246 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A dorijanlendvaj 0:01
B dorijanlendvaj 0:02
C dorijanlendvaj 0:07
D lzoi.win 0:19
E PinkRabbit 0:16
F _Kuroni_ 1:19

UPD: Editorial is out

• +92

 » 7 months ago, # |   +19 Hope high rating to everyone <3
 » 7 months ago, # |   +73
•  » » 7 months ago, # ^ |   +59 getting wrong answer on pretest 2 ***
 » 7 months ago, # |   -34 Please Update the score distribution for all problems. Is there any interactive problem?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +30 Educational Contests are helds on ICPC rules, the problems have time no score.
•  » » » 7 months ago, # ^ |   -24 By mistake I haven't seen that it's an educational round. XD
•  » » 7 months ago, # ^ |   +3 Each problem is worth 1 point. And well I hope there are interactive problems, they are always challenging and fun unless they are binary search xD
 » 7 months ago, # |   0 Is RDDCCD a member of educational rounds problemsetters group now?
•  » » 7 months ago, # ^ |   +1 It's only this time I think.
•  » » » 7 months ago, # ^ |   0 I think some unused problemset of CF Round 602will be used in this round. Thats why RDDCCD is a writer of this round.
 » 7 months ago, # |   0 Please do the contest at 5:35 My school finishs at 3:45 and i must walk to my home (6 km) 4:35 is too early
•  » » 7 months ago, # ^ |   +77 Bruh, the probability of your school shutting down early due to an alien attack is higher than the probability of a cf contest being rescheduled because of a single participant!
•  » » » 7 months ago, # ^ |   +1 There is always hope. Let him take the chance
•  » » 7 months ago, # ^ |   +49 I, after lessons at the University
•  » » 7 months ago, # ^ | ← Rev. 2 →   +10 Hey they exteneded the start time by 15 min...may be now you can run from school and participate successfully (:
•  » » 7 months ago, # ^ |   +1 RUN brother . The round delayed 15 m
 » 7 months ago, # |   0 What's the reason for this unusual start time?
•  » » 7 months ago, # ^ |   -52 How can you say that this is an unusual timing? If so then everytime is unusual for some country.
•  » » » 7 months ago, # ^ |   +25 I never said unfavourable for some country, I just said unusual, anyways I hope this answers
 » 7 months ago, # | ← Rev. 2 →   -8 deleted
 » 7 months ago, # |   0 Who else thinks they will have a huge -ve delta today
•  » » 7 months ago, # ^ |   0 story of each and every educational round !!!
•  » » 7 months ago, # ^ |   +3 what is -ve delta ?
•  » » » 7 months ago, # ^ |   0 Negative rating change
 » 7 months ago, # | ← Rev. 2 →   -71 Delayed 15 minutes. I think they did that to gain 10,000+ participants.
 » 7 months ago, # |   -8 Did the contest time change? As far as I remember, the contest was supposed to start at 16.35 PST and now it is postponed by 15 mins.
•  » » 7 months ago, # ^ |   0 YES
 » 7 months ago, # | ← Rev. 2 →   +76 I'll just finish my homework then
 » 7 months ago, # |   0 How to solve D?
•  » » 7 months ago, # ^ |   +3 Binary search on the maximum number of soldiers, and then simulate the process to check if it is possible to take x soldiers.
•  » » » 7 months ago, # ^ |   0 How to simulate?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +5 You actually don't need to binary search at all. If you know how many soldiers you can bring using the $i$ most difficult traps, you can find out how many you can bring using $i+1$ traps in $O(\log n)$ time.EDIT: sorry, to be explicit, you don't have to do the binary search yourself. You can take the top $i$ traps and use a lower_bound call to find the number of soldiers you can bring.
•  » » » 7 months ago, # ^ |   0 I wonder the process of simulation. Attempts by various methods all failed.
•  » » » » 7 months ago, # ^ |   0 for the simulation at first before the binary search build an array of vectors each vector represents a segment and has the traps of it on it for example you have chosen k personfirst of all you need to choose the ones with the higher agility lets say the lowest agility among the k soldiers is xyou need to move n+1 times with your squad ans some time by yourself to defuse the trapsto calculate that you move from the beginning to the end and keep the farthest defuse spot youve seen till now (lets call it lst) if you are on it or it is in front of you , you need to go and defuse it by yourself so for going and coming back you need to take two more secondsthis is my code for more clarification.
•  » » » » 7 months ago, # ^ |   0 First sort the agility of soldiers in descending order,now the binary search query is can we transport first x soliders in t time? Consider all li and ri,which have di greater than the agility of the weakest soldier,we have to defuse all these. Consider it like intervals(li and ri),sort them,take union of intervals which have intersection,say it is lmax and rmax,now,ans+=(rmax-lmax+1)*2.
•  » » » 7 months ago, # ^ |   0 I did the binary search on the least agility and then check if it is possible to take some soldiers to the boss in the given time. And the number of soldiers is easy to get. But I failed on calculating the time needed...
•  » » » » 7 months ago, # ^ |   0 Same as me. I failed on test 4.
•  » » » 7 months ago, # ^ |   0 I tried same but got wrong in test 4. please help me to find the wrong. https://codeforces.com/contest/1260/submission/65867337
•  » » » » 7 months ago, # ^ |   0 1 9 2 20 1 2 3 2 7 9 2Check this test case,answer is 1
•  » » » » » 7 months ago, # ^ |   0 yeah. Got it.
•  » » 7 months ago, # ^ | ← Rev. 4 →   +10 Let's say we have a function check(N) which returns True if N soldiers can get to the boss in time, and False otherwise. Now, if check(n) returns True, check(n — 1) always returns True aswell. If check(n) returns False, check(n + 1) returns False too. Your task is to find maximum n when check(n) is True. Use binary search to do this.To check if N soldiers can get to the boss, I used next algorithm (this is basically check(N)):1) Go straight unless there's a bomb soldiers can't pass in front of you2) If there's a bomb in front of you, go get to the defusal spot and defuse it. If you meet another bomb along the way to defuse the first one, go to it's defusal spot and defuse that aswell. Continue unless you don't have any more bombs to defuse. Then get back to your soldiers and continue from step 1.Check() works in O(n) time, binary search in O(logn). Final complexity is O(n*logn)
•  » » » 2 weeks ago, # ^ |   0 Hi, can you spot a mistake in my code?84677601
•  » » 7 months ago, # ^ |   0 Non-binary-search method:Sort the traps by decreasing $d_i$. Initialize a sorted set / TreeSet starting with integers $1$ through $n$.Iterate through each trap. First remove all integers $[l_i, r_i]$ from the set. Care must be taken as to method; iterating through each integer in the range would be too slow, as you might try to remove many integers that have already been removed. (This is also why we can't use a boolean array.) Instead you must use a method that quickly finds the "next higher" element in the set in $O(\log n)$ time.Then do a check. The time you need to traverse the path, disarming this trap and all previous ones, is $n + 1 + 2(n - |S|)$, where $|S|$ is the size of the set. (This is because the removed elements correspond to the ranges where you must walk without your squad and back.) If it's greater than $t$, you don't have enough time to disarm this trap, therefore break the loop and only take the soldiers that have $a_j \geq d_i$.If the check passes for all the traps, you may disarm all the traps and take all your soldiers.Samples: 65882822 (explicit iteration) 65883050 (implicit iteration using library methods) One may recognise this as a classic union-of-segments problem; as such there are several other ways to solve it, e.g. with segment trees or path compression.
 » 7 months ago, # |   +3 How to solve C?
•  » » 7 months ago, # ^ | ← Rev. 2 →   -10 Suppose r<=b. (If rk, "OBEY" if b/r<=k.Otherwise, the answer is "REBEL" if b>(k-1)*a+1, "OBEY" if b<=(k-1)*a+1.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +6 My approach to C :let r <= b (swap if r > b)now we will paint all multiples of b (including those which are multiple of r as well as b) with same color.we can have atmost 1 fence divisible by 'b' between 2 consecutive fence divisible by 'r' (as r <= b)since length of fence is 10^100 (consider it infinite) , we need to find maximum number of 'r' fence that can occur between 2 consecutive fences of blet g = gcd(r,b)we can not have a multiple of 'r' and 'b' with difference < g (except for case when 0)so maximum number of divisors of 'r' in range of size ((2*b) — (b+g)) (say x);thus we need atmost val = ceil(x/r) fence of same colors.if(val >= k) ---> REBELelse ---> OBEY
•  » » » 7 months ago, # ^ |   +1 we can not have a multiple of 'r' and 'b' with difference < g (except for case when 0)so maximum number of divisors of 'r' in range of size ((2*b) — (b+g)) (say x);thus we need atmost val = ceil(x/r) fence of same colors.Can You Explain these lines with some example, please...
•  » » » » 7 months ago, # ^ |   +9 lets say we have some A = x.r , B = y.bnow A-B should be divisible by g (i.e gcd(r,b))thus difference between a multiple of 'r' and 'b' will be at least gnow to maximize count of 'r' in window , we will make first 'r' as close to 'b' as possiblethus we have a gap of (2b — b — g)now number of divisiors of 'r' in this gap will be ceil(gap / r)examble : a = 3 , b = 11 we have gap of (2b — b — g) and need to place 'a's in itthus val = ceil(10/3) ---> 4
•  » » » » » 7 months ago, # ^ |   +1 What if the minimum difference between A and B is actually a multiple of gcd in some case? In such a case solving by taking just gcd might give OBEY but actually might be REBEL when the actual minimum difference is taken. Is it possible to prove that in all cases min difference will be gcd and not a multiple of gcd?
•  » » » » » » 7 months ago, # ^ |   0 Slightly different approach here : https://codeforces.com/blog/entry/71755?#comment-560965
•  » » » » » » » 7 months ago, # ^ |   +3 Thank you! and apparently there's something called Bezout's identity which actually ensures that minimum difference between multiples of two numbers is their gcd.
•  » » » » » » 7 months ago, # ^ |   0 It might be a multiple of gcd. But since we have a length of infinite, we can be sure to expect all the different cases.Difference being exactly equal to GCD is worst case to find maximum number of 'r's that can occur between 'b's.
•  » » » 7 months ago, # ^ |   0 Its maybe very stupid question, but can you please tell why cant we just find the lowest number divisible by 'r' that is greater than b (like l = (ceil(b / r) * r) and add r if this value is divisible by b, because this point will be painted in 'b' color) and the greatest number divisible by 'r' that is lower than 2 * b (like h = floor(2 * b / r) * r and subtract r if this value divisible by b) so answer would be (h — l) / r + 1?
•  » » » » 7 months ago, # ^ |   +3 Apply this on r=8 b=13. It's not always optimal to consider b and 2b simply.
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Well it works on 8 and 13 but I got your point, number of r's between any consecutive b's is not equal, thanks a lot
•  » » » » » » 7 months ago, # ^ |   +3 Oops yeah. Task failed succesfully.
•  » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Can you provide an example why number of r's between consecutive b's is not equal ? (Excluding 0 to b and moving from 2b to 3b and so on)
•  » » » » » » » 7 months ago, # ^ |   0 Never mind :|
•  » » » 7 months ago, # ^ |   0 I don't understand why the maximum number of multiples of r between any two multiples of b will not be b/r (b>r). Can anyone please explain with a counterexample if possible?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 try 6 and 10 in the range 0 to 10 there will be only one fence. But in between 11 and 20 there will be 2 fence. so the gcd(r,b) is done to get the minimum starting point. here gcd is 2. So, number of consecutive color = 1 + (max(r,b)-gcd(r,b) -1 )/min(r,b) one is added for the first occurance here 12 for above example.
•  » » » 7 months ago, # ^ |   0 so maximum number of divisors of 'r' in range of size ((2*b) — (b+g)) (say x)Can you please explain why maximum number of divisors of 'r' will be in that range???mridul1809
•  » » » » 7 months ago, # ^ |   0 It's not about why It's about how many! We will have a gap of the specified value or less. But this the maximum gap we will get.
 » 7 months ago, # |   0 When will the problems be added to practice?
•  » » 7 months ago, # ^ |   0 they are already added
 » 7 months ago, # |   +5 Sadly, spent one hour thinking that the soldier agility will decrease d [i], when when he steps on a trap that is not more than his agility, in problem D.
•  » » 7 months ago, # ^ |   0 I don't think this should actually change the solution very much, conceptually. Instead of taking all soldiers whose agility is more than the max d you don't disarm, you just take all the soldiers whose agility is more than the sum of the d you don't disarm.
•  » » » 7 months ago, # ^ |   0 And how can you take the optimal cost for a specific sum?
•  » » » » 7 months ago, # ^ |   0 I wrote my solution in another comment below; the only thing to change in your case would be what is passed into the lower_bound call.
•  » » » » » 7 months ago, # ^ |   0 No, you can’t. In my case, greedy solution doesn’t apply. You can’t disarm the traps in descending way (the same logic as knapsack problem, where the time is your pack capacity and the dangers of the traps are the benefits and the distance of the trap are the costs).
•  » » » » » » 7 months ago, # ^ |   +16 Oh shoot, I’m sorry, you’re totally right. Disregard all my comments I guess.
 » 7 months ago, # | ← Rev. 2 →   +40 My solution to F (65866080):We'll calculate the expected value, then multiply this to get the result.Root the tree at $0$. Let edge $i$ be the edge from node $i$ to its parent. For convenience there will be an edge from the root to nowhere.Call the weight of a node $weight[i] = \frac{1}{b_{i}-a_{i}+1}$. We'll count the answer by looping over colours, and with a fixed colour for every edge adding the product $above[i] \cdot below[i]$ to the answer, where $above[i]$ is the sum of weights of nodes that can have the colour and are above edge $i$ in the tree, and $below[i]$ the same but below.This of course is too slow, but we can calculate this fast by using HLD and two range-add-sum segment trees to represent $above[i]$ and $below[i]$. We'll also maintain the current sum over edges.Change the colour intervals into events, where we add $weight[i]$ to node $i$ at time $a_{i}$, and subtract $weight[i]$ at time $b_{i} + 1$. When an unit of time elapses, add the current sum to the answer.When we add some value to a node, we want to update the current sum, above and below. Use HLD to get a path consisting of at most $\log(n)$ subpaths of nodes with adjacent indices. We'll add $v$ to $below[i]$ to every edge in this path, and add $v$ to $above[i]$ to every edge not on this path. Hence we have to update at most $2 \log(n)$ ranges to update above and below. When we add $v$ to $below[i]$, we add $above[i] * v$ to the current value. So to add $v$ to below in range $x, y$, we add $above[x, y] * v$ to the value, and increment $below[x, y]$ by v. We do similarly when adding $v$ to $above[i]$. The range-add-sum segment trees support these operations.Whenever we add to a node, we make $log(n)$ operations, and each operation takes $log(n)$ time, so the solution is $O(n \log^{2} n)$. The constants seem pretty bad: it took 2.3s/2.5s. Happy hacking I guess :Dd code#include #include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 7; // Segment tree for range addition and range sum. class SegTree { private: const ll NEUT = 0; vector seg, tag; int h = 1; // Returns length of interval corresponding to position i ll len(int i) { return h >> (31 - __builtin_clz(i)); } void apply(int i, ll v) { seg[i] = (seg[i] + v * len(i)) % MOD; if (i < h) tag[i] = (tag[i] + v) % MOD; } void push(int i) { if (tag[i] == 0) return; apply(2*i, tag[i]); apply(2*i+1, tag[i]); tag[i] = 0; } ll combine(ll a, ll b) { return (a + b) % MOD; } ll recGet(int a, int b, int i, int ia, int ib) { if (ib <= a || b <= ia) return NEUT; if (a <= ia && ib <= b) return seg[i]; push(i); int im = (ia + ib) >> 1; return combine( recGet(a, b, 2*i, ia, im), recGet(a, b, 2*i+1, im, ib)); } void recApply(int a, int b, ll v, int i, int ia, int ib) { if (ib <= a || b <= ia) return; if (a <= ia && ib <= b) apply(i, v); else { push(i); int im = (ia + ib) >> 1; recApply(a, b, v, 2*i, ia, im); recApply(a, b, v, 2*i+1, im, ib); seg[i] = combine(seg[2*i], seg[2*i+1]); } } public: SegTree(int n) { while(h < n) h *= 2; seg.resize(2*h, NEUT); tag.resize(h, 0); } ll rangeSum(int a, int b) { return recGet(a, b+1, 1, 0, h); } void rangeAdd(int a, int b, ll v) { recApply(a, b+1, v, 1, 0, h); } }; class HLD { private: vector par, siz, cmp, ind; void dfs1(int i, vector>& g) { for (auto& t : g[i]) { if (t == par[i]) continue; par[t] = i; dfs1(t, g); siz[i] -= siz[t]; if (siz[t] > siz[g[i][0]]) swap(t, g[i][0]); } siz[i] *= -1; } void dfs2(int i, int& x, const vector>& g) { ind[i] = x; ++x; for (auto t : g[i]) { if (t == par[i]) continue; cmp[t] = (x == ind[i]+1 ? cmp[i] : t); dfs2(t, x, g); } } public: // Assumes the tree is connected and r is the root HLD(vector> g, int r = 0) : par(g.size(), -1), siz(g.size(), -1), cmp(g.size(), r), ind(g.size()) { dfs1(r, g); int x = 0; dfs2(r, x, g); } // Returns intervals corresponding to the path between a and b, not necessarily in order vector> path(int a, int b) const { vector> res; for (;; b = par[cmp[b]]) { if (ind[b] < ind[a]) swap(a, b); if (ind[cmp[b]] <= ind[a]) { res.push_back({ind[a], ind[b]}); return res; } res.push_back({ind[cmp[b]], ind[b]}); } } }; ll modPow(ll a, ll b) { if (b & 1) return a * modPow(a, b-1) % MOD; if (b == 0) return 1; return modPow(a*a % MOD, b / 2); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; // HLD with segment tree on edges: Store weight below and weight above as a and b. Support range sum and addition for a and b. ll colc = 1; // Number of colorings vector weight(n); vector> evs; for (int i = 0; i < n; ++i) { int a, b; cin >> a >> b; evs.push_back({a, i+1}); evs.push_back({b+1, -(i+1)}); colc = (colc * (b-a+1)) % MOD; weight[i] = modPow(b-a+1, MOD - 2); } sort(evs.begin(), evs.end()); vector> g(n); for (int i = 0; i < n-1; ++i) { int a, b; cin >> a >> b; --a; --b; g[a].push_back(b); g[b].push_back(a); } HLD hld(g); ll cur = 0; ll res = 0; SegTree above(n), below(n); int c = 0; for (int j = 0; j < evs.size(); ++j) { int nc = evs[j].first; res = (res + cur * (nc - c)) % MOD; c = nc; int i = abs(evs[j].second) - 1; ll v = (evs[j].second < 0 ? MOD-1 : 1) * weight[i] % MOD; // Increment below for all edges above i // Increment above for all other edges vector> path = hld.path(i, 0); int pi = n-1; for (auto pr : path) { cur = (cur + v * below.rangeSum(pr.second + 1, pi)) % MOD; above.rangeAdd(pr.second + 1, pi, v); cur = (cur + v * above.rangeSum(pr.first, pr.second)) % MOD; below.rangeAdd(pr.first, pr.second, v); pi = pr.first - 1; } } res = (res * colc) % MOD; if (res < 0) res += MOD; cout << res << '\n'; } 
•  » » 7 months ago, # ^ |   +8 We can do optimize this idea to $O(n \log n)$ by centroid decomposition + doing a sweep through the intervals of colors. I'm guessing this is the expected solution?
•  » » » 7 months ago, # ^ |   +8 How would you get rid of sorting the events?
•  » » » » 7 months ago, # ^ |   +8 There are $2n$ events, two per node, we can sort them initially in $O(n \log n)$ and then sweep through them. When we are processing the color $c$, we can assume the centroid tree has the EV information of only those nodes whose intervals pass through $c$, so we can go up the ancestors to update our answer, and then update the values maintained in the ancestors themselves.
•  » » 7 months ago, # ^ |   +10 The std is similar, but instead of maintaining the contribution of edges, it maintains the expect value itself with HLD. It's also log^2 but works faster.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +34 Since the std is also $O(n\log^2 n)$, I think the TL is too tight. My solution is centroid decomposition with segment tree, it was TLE on 6 at first, after a few optimizations (on constants), it is TLE on 14 now.However, since there is an $O(n\log n)$ solution, the TL seems somehow reasonable.
•  » » » » 7 months ago, # ^ |   0 Try using fast_mod, my 65887298 is almost the same and only with fast_mod pass the testcase 14
•  » » » » » 7 months ago, # ^ | ← Rev. 3 →   0 Thank you for that, it's a bit faster, but still not enough.Also, my full-of-vectors $O(n\log n)$ solution got TLE on 9, I think I should do some optimizations tomorrow.UPD: it's not about constant, I wrote a wrong centroid decomposition, the $O(n\log n)$ solution got accepted now.
•  » » » » » » 7 months ago, # ^ |   +8 Your solution got AC :), I changed a bit your segment tree (it's not very efficient), It's so painful see one line with 1000+ characters :(
•  » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 I wrote that segmentTree template for convenience (and I thought that small constant is never needed on Codeforces). I thought I could get AC if I wrote a segment tree specifically for this problem, but I chose to write an $O(n\log n)$ solution.And I don't need to read my template when I use it, so I use indents to move them out of the screen, and compressed them so that I don't need to scroll too much. The origin one is here (or you can use something like Clang format to make it readable).
•  » » 7 months ago, # ^ |   +10 Hi! Your algorithm is indeed very efficient. The bad running time is only because you were using long longs all over the place. In case anyone is interested, I changed the long long to int in your code (except for modular multiplication), and the same code works in 1.4s. Here: 66453535
 » 7 months ago, # |   0 I thought I had good idea for D, but tons of debugging brought nothing to the table, anyone care for a challenge? http://codeforces.com/contest/1260/submission/65854863
•  » » 7 months ago, # ^ |   +10 Imagine you have two traps, one with [l, r] as [1, 2] and the other with [l, r] as [100, 101]. You don't want to run all the way from 1 to 101 and then back without your squad. Instead, you want to run from 0 to 2, then back, then 0 to 99 with squad, then 99 to 101, then back, then 99 to end with squad.
•  » » 7 months ago, # ^ |   +3 When two traps are far apart, it's actually better to deactivate first trap, bring troops to second trap and then deactivate second trap, instead of deactivating both in one go and taking your troop to the boss. The two traps could be , say, [1,2,100] and [50,51,100]
•  » » 7 months ago, # ^ |   0 I had same solution with O(N) complexity. 65873412
•  » » » 5 weeks ago, # ^ |   0 why are you posing wrong solutions ..
 » 7 months ago, # |   0 How to Solve B? I used greedy and it passed. How did you solved, can you explain your approach.
•  » » 7 months ago, # ^ |   +3 If (a+b)%3!=0, the answer is NO because the sum of the numbers that is subtracted to one operation is a multiple of 3. And if a>2*b||b>2*a, the answer is NO. Otherwise, the answer is YES.
•  » » 7 months ago, # ^ |   0 In one go we are decreasing x from one number and 2x from other number. So, in one go, we are decreasing a total of 3x . Let we have to do this n times to reach 0. so we will decrease 3nx from the two numbers . it means sum of two numbers should be multiple of 3. morever one number should not be more than twice of other.(you can check this condition by observation) (a+b)%3==0 && 2*a>=b , assuming b>a.
•  » » » 7 months ago, # ^ |   0 Got it. Thanks
•  » » 7 months ago, # ^ | ← Rev. 2 →   +5 Number of times you minus 1 from a = number of times you minus 2 from b = xNumber of times you minus 2 from a = number of times you minus 1 from b = yy + 2x = ax + 2y = bAfter solving the simultaneous equations, if either one of x and y is negative or not an integer, the answer is "NO".
 » 7 months ago, # |   +10 How to solve E?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +16 Note that you need to beat the player with the highest strength at some point. This gives the greedy insight to compete with the strongest player at the last stage, and use them to make your previous matches as cheap as possible. You can recursively apply this property to solve in $O(n)$ or $O(n \log n)$.
•  » » 7 months ago, # ^ |   +24 My solution was something like this (this is pretty hand-wavy):Let $k = \log_2(n)$.First notice that we can simply let all the $a_i$ below our friend be 0 and then make our friend the weakest player in the tournament.Next, we notice that we must pay $a_{n}$ at some point, and it would be best to do it in the finals so that they can knock out as many people as possible. You can extend this concept to say, "of all the $a_i$ I end up choosing, I should fight these opponents in increasing order".If you have cheap fighters at the top, then the problem is pretty easy, so instead let's think about the case when all the fighters have nondecreasing costs in accordance with their strength. We only consider fighters $2, ..., n-1$. We can't pick the $k-1$ cheapest fighters, because it wouldn't be possible to fight all of them (they would lose before we would get a chance). Thus, we can pick the cheapest fighter, and know that the second cheapest fighter would lose. Then, we can pick the third cheapest fighter, and so on, and we notice that we would pick the first, third, seventh, etc. cheapest fighters.Now, there's the issue of the fact that the strengths aren't nondecreasing. We basically want the $k-1$ cheapest fighters such that you don't have more than 1 out of the first two, more than two out of the first four, more than three out of the first eight, etc. We can iterate backwards with a set to get these fighters.65872935
•  » » » 7 months ago, # ^ |   0 what was the mistake?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Oh, I did the hack myself after talking with a friend. Just needed std::multiset. The solution should be the same.
•  » » » 7 months ago, # ^ |   0 I don't think I fully understand why we're adding n / 2 strongest fighters in the first step. Does that simulate 1 phase of the competition or second to last phase of the competition?
•  » » » » 7 months ago, # ^ | ← Rev. 3 →   0 I'm not sure how to prove it rigorously, but with some pen-and-paper simulations it is possible to show that the weakest fighters your friend can choose to fight (assuming he's in position $1$; if he isn't, you can always zero-out fighters below him and move him there) are in positions $2$, $4$, $8$, $16$, etc. And through an exchange argument, you can choose to "move" any number of these indices rightward to reduce your cost, but never leftward.Here's a DP-based implementation I made where I enforce the limit of number of defeatable fighters by limiting the size of the DP array in each step: 65895737 . Complexity is $O(n \log n)$ due to the average number of transitions per step being in $O(\log n)$
 » 7 months ago, # |   0 Solution for D:I thought it was a little fishy that the disarming position was called $r_i$, because $(l_i, r_i)$ typically signifies some sort of interval, but there didn't seem to be any intervals here.However, thinking about the problem for a bit, we notice that if we only had one trap, then we would want to walk with the squad up until $l-1$, then run by ourselves to $r$ and back, then walk to the end from $l-1$ with our squad. The total distance would be $n+1 + 2*(r-l)$.Now, let's think about the case when we have two traps. We definitely want to walk with the squad till the smaller $l$ minus 1. Then, there are two cases. Either, we can go to the farther $r$, or we can go to the nearer $r$, come back, and reduce to the case of one trap. We want to minimize the number of times we run over the same spot, so we actually notice that if we consider $[l_1-1, r_1]$ and $[l_2-1, r_2]$ to be intervals, we want to merge the intervals if intersecting and walk along that distance. Thus, we can create all the different intervals associated with all the traps, merge them until we have disjoint intervals, and calculate the total sum.This means we can actually add a new trap online in $O(\log n)$ time, so to get the answer we just iterate through the traps in descending order of difficulty, and we can find how many soldiers we can bring with a lower_bound call.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 You can actually think about it as intervals.Firstly, it is easy to see that, you never take the squad backwards. So, squad ( along with you ) is definitely going to move $n+1$ steps forward. Then, for each trap $(l_i,r_i,d_i)$ you encounter, firstly we preprocess a bit, and for each $i$ from $0$ to $n+1$, we construct an array $A$ such that $A[i]$ stores maximum of $d[j]$ over all traps $j$ such that $l_j <= i <= r_j$ ( take max danger values on the intervals of the trap ).Now, considering minimum agility of squad is $ag$. We see that, wherever we have $A[i] > ag$, we must go back and forth. So you just need count of number of values in array $A$, that are greater than $x$. This is easy, by making a frequency array, and taking backwards cumulative. Thus, required time is $n+1+2*greater[ag]$.
 » 7 months ago, # |   +6 You can find task B here: https://cses.fi/problemset/task/1754
 » 7 months ago, # |   0 for problem D , in the example why do you have to go back to 0? do you have to be on 0 when the level finishes?
•  » » 7 months ago, # ^ |   0 Because you have to pick up your squad.
 » 7 months ago, # |   +7 I found D simpler than C :(
 » 7 months ago, # |   0 What's wrong on this binary search of problem D? I can't get it. https://codeforces.com/contest/1260/submission/65867337
•  » » 7 months ago, # ^ |   +1 It is not optimal to "rush" for the last disarmer. Consider the case 4 15 3 20 1 2 3 4 5 5 2 10 10 3 14 14 2 Your program results in 2 while the correct is 3 because you can get as close as possible to trap with your army, then use 2 moves to disarm and go back and continue, losing only 2 moves on 3 traps = 6 moves instead of going through almost all cells twice (though this strategy is not optimal for other cases). I'm not sure about modeling optimal strategy but my solution uses the fact that in an optimal solution for every interval l..r each cell in that interval will be visited extra two times (no matter in how many intervals this cell is included already) https://codeforces.com/contest/1260/submission/65882237
•  » » » 7 months ago, # ^ |   0 Hey, I am also having some difficulty in this question, and I am having correct answer on the test case you provided, I have made many submissions and do not understand what is wrong now, submission link — https://codeforces.com/contest/1260/submission/65897985 It's getting wrong on test case 4. I would be really grateful if anyone can provide any counter test case or pinpoint the part I am getting wrong.
 » 7 months ago, # | ← Rev. 3 →   0 Why is the test case in C1 5 17 4REBEL?If I understand task correctly we need to color fences 0,5,10,15,17,20,25,30,34,35... So if we paint first in one, then next 3 in another color and then repeat that process... how it is not possible?
•  » » 7 months ago, # ^ |   +1 Look at what happens in that ...(hint: you get 4 in a row)
•  » » 7 months ago, # ^ |   +1 35, 40, 45, 50 is painted red and no blue fences between them.
•  » » 7 months ago, # ^ |   +2 if you continue your sequence you get34 -> blue35 -> red40 -> red45 -> red50 -> red51 -> blue
 » 7 months ago, # |   0 Can somebody provide some mathematical proof for C ?
•  » » 7 months ago, # ^ |   +2 use pegionhole principle.
•  » » » 7 months ago, # ^ |   0 can you elaborate please?
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +20 My Logic :Let A<=B The answer has to be between 2 LCMs of A and B. X = Number of A's between 2 LCMs = LCM/A — 1 Y = Number of B's between 2 LCMs = LCM/B — 1 X will be >= Y because A<=B Y will create Y + 1 partitions between 2 LCMs, so X needs to be split into Y + 1 groups. ANS = Max number of A's in a single group would then be X/(Y+1) + (X%(Y+1)?1:0) If ANS >= K : REBEL else OBEY Submission : 65867808
•  » » » » » 7 months ago, # ^ |   0 hmm, i didn't see zarif_2002 solution before asking, i think that his solution also use ceil((b — gcd(a, b)) / a), and my question is how pigeonhole principle used in that solution..But anyway nice solution, thanks!
•  » » » » » 7 months ago, # ^ |   0 That's the most intuitive solution I've came acrossI bothered myself so much with gcd == 1 and gcd != 1 cases before submitting my solution
•  » » » » » 7 months ago, # ^ |   +6 how could you prove that the Xs will be split evenly between every partition of Y + 1?
•  » » » » » » 7 months ago, # ^ |   0 This statement is not true.X's won't split evenly in all the cases, hence [+ (X%(Y+1)?1:0)] to factor in the unevenness.
•  » » » » » » » 7 months ago, # ^ |   0 You misunderstood my question!What I meant was how could you prove that between every two partitions at most X/(Y + 1) + (X % (Y + 1) != 0)exist? that's what I meant by even distribution, how did you prove that between every two partitions the count of numbers multiple of A differ by at most 1?
•  » » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   +6 When $A \le B$, between 2 multiples of B:$\lfloor\frac{B - 1}{A}\rfloor \le \text {Multiples of A} \le \lceil\frac{B - 1}{A}\rceil$Since both fractions are the same the difference must be $\le 1$
•  » » » » » » » » » 7 months ago, # ^ |   +5 what does $B - 1$ represent in here?
•  » » » » » » » » » 7 months ago, # ^ |   +3 Integers between $2$ multiples of $B$
•  » » » » 7 months ago, # ^ |   0 let's say, a <= b. We have to calculate colours from 1 to lcm(a,b). Use colour blue in lcm(a,b). occ_b = lcm(a,b)/b. occ_a = lcm(a,b)/a — 1. then, we have tocheck if ceil(occ_a/occ_b) < k or not. If yes, then OBEY. if no, then REBEL. Now, why we would take ceiling, simple commonsense. You have occ_b intervals and you have to put occ_a things in the interval. Then, what would you do? ceiling. That's it.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Thanks for this explanation. ❤️️
•  » » 7 months ago, # ^ |   +1 By Bezout’s identity,there exists x,y s.t.ax-by=gcd(a,b)
 » 7 months ago, # | ← Rev. 2 →   0 Here is my submission (I submitted after contest) for C: 65874604I have done a different approach and not very sure if it is correct. Can someone try and hack it/ let me know where it's wrong(if it's wrong). Thaanks :)
•  » » 7 months ago, # ^ |   0 What is the idea behind your approach?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +5 Done. The minimum offset between start and i*b in your code is equal to the gcd of the 2 numbers and 2000 iterations isn't enough to find that.
•  » » » 7 months ago, # ^ |   0 Thank you!!! I think I get it now :)
 » 7 months ago, # |   +12 Is anyone else having trouble viewing the hacks page here?
•  » » 7 months ago, # ^ |   0 Using vpn I managed to see hacks page
 » 7 months ago, # |   0 C Can someone please find in what test case will my code give wrong answer?
•  » » 7 months ago, # ^ |   +4 13 5 2answer is REBEL but your one is OBEY
•  » » » 7 months ago, # ^ |   0 proggerkz Thanks a lot :-)
 » 7 months ago, # |   0 i'm guessing that the idea for problem B was taken from https://atcoder.jp/contests/abc145/tasks/abc145_d
 » 7 months ago, # |   +7 Today's Contest was Math based...
 » 7 months ago, # |   -56 the worst contest ever
•  » » 7 months ago, # ^ |   +3 Even though I failed miserably, the contest was actually quite good. The problems weren't impossible, but some of them were tricky — such contests are a great learning experience.
 » 7 months ago, # | ← Rev. 2 →   +4 Why are we doing gcd of r and b in C? I cannot understand C though there are some explanations here.
•  » » 7 months ago, # ^ |   +4 Let's assume $r \ge b$. Now let's ignore the numbers which are divisible both by $r$ and $b$ (imagine we can paint them in some third colour for now). Then, if we will have $k$ numbers of same colour in a row, they must be the ones that are divisible by $b$ (since $b$ is the smaller one, and intervals between its numbers will be smaller). This means that $k$ numbers divisible by $b$ are located between two numbers divisible by $r$, in other words, $rx < by$ and $b(y + k - 1) < r(x + 1)$.These inequalities kinda describe the problem, but in order to be complete, they need to handle extreme cases (include $\le$ signs). That means that $rx < by$ is not enough, we need to write something like $rx + 1 \le by$. But, in fact, the next number after $rx$ that has a chance to be divisible by $b$ is $rx + gcd(r, b)$. This is my intuition behind it.
 » 7 months ago, # |   0 How to solve "A" ? I am a newbie :( It will be helpful if you provide blog/tutorial that help me to solve the problem.
•  » » 7 months ago, # ^ |   -8 I agree, I think problem statement translations need serious rethinking! I could not understand how a radiator has different sections. A house would have different sections called rooms, and radiation’s would not have sections in a real world. Regis made the goulash had to digest. I expect the total cost to heat the house based on berles to be related to the sections’ in the radiators. Confusing. Really confusing. When tutorial comes out, verify your thoughts against the solution, then work the problem.
•  » » 7 months ago, # ^ |   0 Actually there is a straight forward solution for Problem A. get c & sum and break sum into c small number that will adds up the number "sum". This can be done like create a array of size c and  i=0; while(sum--){ arr[i%(c)]++; i++; } now accumulate the square of each integer in array 'arr' and print it.My c++ solution: Problem A Solution
 » 7 months ago, # |   +2 Anyone can help with problem C ? I have read some solutions and ideas but still didn't get it? How do we get to this formula if((b-1+a-1)/a>=k)---->Rebel else obey ??? Thanks
•  » » 7 months ago, # ^ |   +7 Note that (b-1+a-1)/a reads "ceil of (b-1)/a". With swapping and dividing by gcd, we can assume a < b and (a, b) are coprime.Here, b-1 is "how many consecutive panels you cannot paint with color b". Like if b=10, it is [1, 2, 3, 4, 5, 6, 7, 8, 9]. Then, ceil of (b-1)/a is "how many panels from those b-1 panels you have to paint with color a". If a=3 and b=10, b-1 panels are [1, 2, 3, 4, 5, 6, 7, 8, 9], thus the worst case is like [1, 4, 7] or [3, 6, 9] then the answer is 3. If a=3 and b=11, b-1 panels are [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], thus the worst case is [1, 4, 7, 10] then the answer is 4. (Note that this worse case will surely happen because (a, b) are coprime.) This is ceil of (b-1)/a.
•  » » » 7 months ago, # ^ | ← Rev. 3 →   0 Well this may sound a bit silly ; but can you please explain how :( b-1+a-1 )/a = ceil ( ( b-1 )/a )...?
•  » » » » 7 months ago, # ^ |   +1 Sorry it may have been very confusing: the slash in the left hand side is an integer division, and the slash in the right hand side is an accurate (real or rational) division.In this post I will denote an integer division // and accurate division / . (10//3 = 3 and 10/3 = 3.333). What I am going to say is that ceil(n/m) = (n+(m-1))//m.If n = km, the term "+(m-1)" has no effect and then the answer is just k. If n = km+r and r ≥ 1, the term "+(m-1)" surely has an effect and the answer turns to be k+1. This is nothing other than how ceil(n/m) should behave.For example if m=10, floor(n/10) = n//10, round(n/10) = (n+5)//10, ceil(n/10) = (n+9)/10.
•  » » » » » 7 months ago, # ^ |   0 It helped ; thanks ! :)
•  » » » » » 7 months ago, # ^ |   0 hey can you give an example where the ceil((b-1)/a) changes the answer. like you told when b=11 and a=3 [1,4,7,10] but this. the number of numbers divisible by 3 between 1-10 will always be floor((b-1)/a) not ceil. For example if a=6 and b=9. can you give the value of pos to pos+k where there are ceil((b-1)/a) values divisible by a. 1 2 3 4 5 6 7 8 9 there is only 1 number divisible by 6 which is 6 , similarly between 9-18 there will only be one no divisible by 6 i.e. 12.
•  » » » » » » 7 months ago, # ^ |   0 Well you are right, when a=6 and b=9 it will never happen that he paints a plank of number 1 (mod 9; i.e. 1, 9+1, 18+1, 27+1, ...) in red. That comes from the fact that 6 and 9 are not coprime. And that is exactly the reason why we have to divide a and b by gcd at the beginning, so that they would be coprime. In this case, we would take a=2, b=3.When a and b are coprime, like a=7 and b=9, there is some [9n+1, 9n+2, ..., 9n+8] such that contains ceil((b-1)/a) red planks. (In this case [28, 29, 30, 31, 32, 33, 34, 35].)
•  » » » » » » » 7 months ago, # ^ |   0 Sorry if it sounds silly How should we sure about answer won't change after dividing the numbers by gcd ? Thanks
•  » » » » » » » » 7 months ago, # ^ |   +8 Okay, let's think of a=50 and b=70. This case a and b has a common divisor 10.In this case, red planks are 50, 100, 150, 200, 250, ... and blue planks are 70, 140, 210, 280, .... Since 50 and 70 are both multiple of 10, the player will never paint any planks other than 10n. Then the planks that we must take care of are those planks of 10n. Now we can rename those planks 10, 20, 30, 40, 50, ... as just 1, 2, 3, 4, 5, .... After this renomination, a=50 and b=70 will now called a=5 and b=7.This is what is called dividing by gcd.
•  » » » » » » » 8 days ago, # ^ |   0 Why a and b need to be coprime?
•  » » » 4 months ago, # ^ |   0 "this worse case will surely happen because (a, b) are coprime." would you please prove that? how can we be sure that worse case will be ceil((b-1)/a) if gcd(a, b) == 1?
•  » » » » 4 months ago, # ^ |   0 Okay, now let there be (b-1) panels [1, 2, 3, ..., b-1] and he start painting at panel i. Then he will paint panels [i, i+a, i+2a, i+3a, ...] until he reaches the last panel b-1. The worst case is when he starts at 1. Here "starts at 1" means "some panel, whose index is ≡1 mod b, is to be painted with color a". This means that there exists some panel that has index ≡1 mod b and at the same time ≡0 mod a.Above is possible when a and b are coprime, because -- When they are coprime, [a mod b, 2a mod b, 3a mod b, 4a mod b, ..., (b-1)a mod b] are (b-1) pairwise distinct nonzero numbers. Then Pigeonhole Principle leads that one of them is 1.
 » 7 months ago, # |   +1 will it going to increase/ decrease rating?? if yes, then when?
 » 7 months ago, # |   +25 When will be rating table?
 » 7 months ago, # |   0 gg
 » 7 months ago, # | ← Rev. 2 →   -17 。
•  » » 7 months ago, # ^ |   +6 What a coincidence!
•  » » » 7 months ago, # ^ |   0 QAQ
•  » » 7 months ago, # ^ |   0 If you think the reason for your solution being skipped is that the system thinks you copied code from each other and you haven't copied, how have you found this submission that just so happened to be the same as yours, except for the distribution of spaces? (disclaimer: I'm not saying you copied, but saying that either you copied or the reason for your solution being skipped is something else)
 » 7 months ago, # |   +3 two more points,just two.....
 » 7 months ago, # | ← Rev. 2 →   +4 Why did i get last place and skipped if i didn't cheat? My submision for D is the first one, i didn't copy from anywhere.I get it why i am unrated but why last place when i didn't cheat.
 » 7 months ago, # |   +10 Finally saw cyan for the first time after this round, i know this is a small thing for many, but we gotta start somewhere :)
 » 7 months ago, # |   -22 How much time it will take for me to reach 2100 :(
 » 7 months ago, # |   0 Can someone please explain the idea behind problem B
•  » » 7 months ago, # ^ |   0 The sum of the integers must be a multiple of $3$ because they both reached $0$, no matter what $x$ we choose, the changes after each query should be a multiple of $3$. But, beware of a situation where even letting the smaller one change as slow as possible won't make it enough to make the larger one change to $0$, in this case we get a negative answer.
 » 7 months ago, # |   +17 Editorial?
 » 7 months ago, # |   0 hahaha... When I found out my bug in problem C, I could not hold back a laugh. It was just round off error in divide.
 » 7 months ago, # | ← Rev. 3 →   0 Why does this approach for Problem D fails on test #8? -> 65903924 Changing it a bit gives AC -> 65918839Isn't the two ways of using check function equivalent? One is calculating contribution of point i separately and the other as a whole.
•  » » 7 months ago, # ^ |   0 This is a simple countercase: 1 3 1 8 5 1 3 10 `Your code outputs 1, but the correct answer is 0. (It takes 4 seconds to go straight (0 -> 4); and if they deside to disarm the trap it takes 6 extra seconds (0 -> 3 -> 0)).This is because your code resets the variable 'right' every time for new i, so when your code comes to i = 2 it believes that there is no trap, that means it takes only 4 seconds to disarm the trap (0 -> 2 -> 0).
•  » » » 7 months ago, # ^ |   0 Understood, thanks a lot! :D
 » 7 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 7 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 2 months ago, # |   0 nice problem C!
 » 2 months ago, # |   0 I wonder how many people come here because of NOI online?