By PikMike, history, 2 weeks ago, translation, In English,

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.

Codeforces and Harbour.Space

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

 
 
 
 
  • Vote: I like it
  • +92
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Hope high rating to everyone <3

»
2 weeks ago, # |
  Vote: I like it +73 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is RDDCCD a member of educational rounds problemsetters group now?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It's only this time I think.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think some unused problemset of CF Round 602will be used in this round. Thats why RDDCCD is a writer of this round.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +77 Vote: I do not like it

    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!

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      There is always hope. Let him take the chance

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    I, after lessons at the University

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    RUN brother . The round delayed 15 m

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the reason for this unusual start time?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it -52 Vote: I do not like it

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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it -8 Vote: I do not like it

llj txdy! Hope everyone high rating!

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
Rev. 2   Vote: I like it -71 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

»
13 days ago, # |
Rev. 2   Vote: I like it +76 Vote: I do not like it

I'll just finish my homework then

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to simulate?

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      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.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
    Rev. 4   Vote: I like it +10 Vote: I do not like 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)

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C?

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    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.

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              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.

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Oops yeah. Task failed succesfully.

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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)

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the problems be added to practice?

»
13 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it +16 Vote: I do not like it

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

»
13 days ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

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
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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?

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      How would you get rid of sorting the events?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 2   Vote: I like it +34 Vote: I do not like it

      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.

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try using fast_mod, my 65887298 is almost the same and only with fast_mod pass the testcase 14

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              11 days ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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]

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve E?

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what was the mistake?

      • »
        »
        »
        »
        13 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
13 days ago, # |
  Vote: I like it +7 Vote: I do not like it

I found D simpler than C :(

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
13 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Look at what happens in that ...

    (hint: you get 4 in a row)

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    if you continue your sequence you get

    34 -> blue

    35 -> red

    40 -> red

    45 -> red

    50 -> red

    51 -> blue

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody provide some mathematical proof for C ?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    use pegionhole principle.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you elaborate please?

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it +20 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          how could you prove that the Xs will be split evenly between every partition of Y + 1?

          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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?

              • »
                »
                »
                »
                »
                »
                »
                »
                11 days ago, # ^ |
                Rev. 2   Vote: I like it +6 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the idea behind your approach?

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

»
13 days ago, # |
  Vote: I like it +12 Vote: I do not like it

Is anyone else having trouble viewing the hacks page here?

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the Hack for C?

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Today's Contest was Math based...

»
13 days ago, # |
  Vote: I like it -56 Vote: I do not like it

the worst contest ever

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
13 days ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like 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.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
13 days ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like 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.

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It helped ; thanks ! :)

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            10 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              9 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                9 days ago, # ^ |
                  Vote: I like it +8 Vote: I do not like it

                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.

»
12 days ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it +25 Vote: I do not like it

When will be rating table?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

gg

»
12 days ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    What a coincidence!

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
12 days ago, # |
  Vote: I like it +3 Vote: I do not like it

two more points,just two.....

»
12 days ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    He shouldn't be skipped and unrated. He is one of the genuine and hardworking coders i have seen in cf. Please return his ratings back.

»
12 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it -22 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the idea behind problem B

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
12 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Editorial?

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
12 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    12 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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