Hello Codeforces!

On Nov/27/2019 16:50 (Moscow time) Educational Codeforces Round 77 (Rated for Div. 2) will start.

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*

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 |

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

Hope high rating to everyone <3

getting wrong answer on pretest

2***Please Update the score distribution for all problems. Is there any interactive problem?

Educational Contests are helds on ICPC rules, the problems have time no score.

By mistake I haven't seen that it's an educational round. XD

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

Is RDDCCD a member of educational rounds problemsetters group now?

It's only this time I think.

I think some unused problemset of

CF Round 602will be used in this round. Thats why RDDCCD is a writer of this round.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

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!

There is always hope. Let him take the chance

I, after lessons at the University

Hey they exteneded the start time by 15 min...may be now you can run from school and participate successfully (:

RUN brother . The round delayed 15 m

What's the reason for this unusual start time?

How can you say that this is an unusual timing? If so then everytime is unusual for some country.

I never said unfavourable for some country, I just said unusual, anyways I hope this answers

deleted

Who else thinks they will have a huge -ve delta today

story of each and every educational round !!!

what is -ve delta ?

Negative rating change

Delayed 15 minutes. I think they did that to gain 10,000+ participants.

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.

YES

I'll just finish my homework then

How to solve D?

Binary search on the maximum number of soldiers, and then simulate the process to check if it is possible to take x soldiers.

How to simulate?

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.

I wonder the process of simulation. Attempts by various methods all failed.

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 person

first of all you need to choose the ones with the higher agility lets say the lowest agility among the k soldiers is x

you need to move n+1 times with your squad ans some time by yourself to defuse the traps

to 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 seconds

this is my code for more clarification.

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.

Code:https://codeforces.com/contest/1260/submission/65905543

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...

Same as me. I failed on test 4.

I tried same but got wrong in test 4. please help me to find the wrong. https://codeforces.com/contest/1260/submission/65867337

1 9 2 20 1 2 3 2 7 9 2

Check this test case,answer is 1

yeah. Got it.

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 you

2) 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)

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.

How to solve C?

Suppose r<=b. (If r<b, you can swap r and b.)

If r==b, the answer is "OBEY".

Else divide r and b into gcd(r,b).

Then if b%r==0, the answer is "REBEL" if b/r>k, "OBEY" if b/r<=k.

Otherwise, the answer is "REBEL" if b>(k-1)*a+1, "OBEY" if b<=(k-1)*a+1.

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 b

let 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) ---> REBEL

else ---> OBEY

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...

lets say we have some A = x.r , B = y.b

now 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 g

now to maximize count of 'r' in window , we will make first 'r' as close to 'b' as possible

thus 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 it

thus val = ceil(10/3) ---> 4

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?

Slightly different approach here : https://codeforces.com/blog/entry/71755?#comment-560965

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.

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.

Its maybe very stupid question, but can you please tell why can`t 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?

Apply this on r=8 b=13. It's not always optimal to consider b and 2b simply.

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

Oops yeah. Task failed succesfully.

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)

Never mind :|

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?

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.

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

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.

When will the problems be added to practice?

they are already added

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.

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.

And how can you take the optimal cost for a specific sum?

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.

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).

Oh shoot, I’m sorry, you’re totally right. Disregard all my comments I guess.

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

codeWe 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?

How would you get rid of sorting the events?

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.

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.

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.

Try using

`fast_mod`

, my 65887298 is almost the same and only with fast_mod pass the testcase 14Thank 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.

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 :(

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).

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

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

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.

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]

I had same solution with O(N) complexity. 65873412

why are you posing wrong solutions ..

How to Solve B? I used greedy and it passed. How did you solved, can you explain your approach.

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.

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.

Got it. Thanks

Number of times you minus 1 from a = number of times you minus 2 from b = x

Number of times you minus 2 from a = number of times you minus 1 from b = y

y + 2x = a

x + 2y = b

After solving the simultaneous equations, if either one of x and y is negative or not an integer, the answer is "NO".

How to solve E?

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)$$$.

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

what was the mistake?

Oh, I did the hack myself after talking with a friend. Just needed std::multiset. The solution should be the same.

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?

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)$$$

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.

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]$$$.

You can find task B here: https://cses.fi/problemset/task/1754

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?

Because you have to pick up your squad.

I found D simpler than C :(

What's wrong on this binary search of problem D? I can't get it. https://codeforces.com/contest/1260/submission/65867337

It is not optimal to "rush" for the last disarmer. Consider the case

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/65882237Hey, 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.

Why is the test case in C

1 5 17 4

REBEL?

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?

Look at what happens in that ...

(hint: you get 4 in a row)

35, 40, 45, 50 is painted red and no blue fences between them.

if you continue your sequence you get

34 -> blue

35 -> red

40 -> red

45 -> red

50 -> red

51 -> blue

Can somebody provide some mathematical proof for C ?

use pegionhole principle.

can you elaborate please?

My Logic :

Let A<=B

X/(Y+1) + (X%(Y+1)?1:0)Submission : 65867808

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!

That's the most intuitive solution I've came across

I bothered myself so much with gcd == 1 and gcd != 1 cases before submitting my solution

how could you prove that the

`X`

s will be split evenly between every partition of`Y + 1`

?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.

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`

?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$$$

what does $$$B - 1$$$ represent in here?

Integers between $$$2$$$ multiples of $$$B$$$

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 to

check 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.

Thanks for this explanation. ❤️️

By Bezout’s identity,there exists x,y s.t.ax-by=gcd(a,b)

Here is my submission (I submitted after contest) for C: 65874604

I 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 :)

What is the idea behind your approach?

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.

Thank you!!! I think I get it now :)

Is anyone else having trouble viewing the hacks page here?

Using vpn I managed to see hacks page

C Can someone please find in what test case will my code give wrong answer?

1

3 5 2

answer is REBEL but your one is OBEY

proggerkz Thanks a lot :-)

i'm guessing that the idea for problem B was taken from https://atcoder.jp/contests/abc145/tasks/abc145_d

Today's Contest was

based...`Math`

the worst contest ever

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.

Why are we doing gcd of r and b in C? I cannot understand C though there are some explanations here.

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

itsnumbers 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.

How to solve "A" ? I am a newbie :( It will be helpful if you provide blog/tutorial that help me to solve the problem.

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.

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

now accumulate the square of each integer in array 'arr' and print it.

My c++ solution: Problem A Solution

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

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.

Well this may sound a bit silly ; but can you please explain how :

( b-1+a-1 )/a = ceil ( ( b-1 )/a )...?

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.

It helped ; thanks ! :)

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.

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].)

Sorry if it sounds silly How should we sure about answer won't change after dividing the numbers by gcd ? Thanks

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.

"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?

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.

will it going to increase/ decrease rating?? if yes, then when?

When will be rating table?

gg

。

What a coincidence!

QAQ

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)

two more points,just two.....

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.

Finally saw cyan for the first time after this round, i know this is a small thing for many, but we gotta start somewhere :)

How much time it will take for me to reach 2100 :(

Can someone please explain the idea behind problem B

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.

Editorial?

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.

Why does this approach for Problem D fails on test #8? -> 65903924 Changing it a bit gives AC -> 65918839

Isn't the two ways of using check function equivalent? One is calculating contribution of point i separately and the other as a whole.

This is a simple countercase:

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).

Understood, thanks a lot! :D

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).nice problem C!

I wonder how many people come here because of NOI online?