getting wrong answer on pretest 2 ***

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

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

It's only this time I think.

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!

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

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

story of each and every educational round !!!

what is -ve delta ?

YES

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

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.

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

they are already added

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.

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?

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.

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

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

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.

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

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

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

Because you have to pick up your squad.

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://mirror.codeforces.com/contest/1260/submission/65882237

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

use pegionhole principle.

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

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.

Using vpn I managed to see hacks page

1

3 5 2

answer is REBEL but your one is OBEY

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.

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.

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.

What a coincidence!

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)