Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By PikMike, history, 4 months ago, translation, In English,

On Aug/03/2018 17:45 (Moscow time) Educational Codeforces Round 48 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 extented ACM ICPC rules. 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 7 problems and 2 hours to solve them.

The problems were invented and prepared by Ivan BledDest Androsov, Roman Ajosteen Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov and me.

Good luck to all participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 eddy1021 7 299
2 djp_cqq 6 240
3 halyavin 6 248
4 BigBag 6 250
5 IcePrince_1968 6 286

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 80:-21
2 Doriath 45:-10
3 antguz 25:-1
4 applese 12
5 Ne0n25 11:-2
236 successful hacks and 417 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A bazsi700 0:01
B bazsi700 0:05
C yjq_naiiive 0:17
D teja349 0:10
E yjq_naiiive 0:49
F eddy1021 0:41
G .................. 1:16

UPD: Editorial

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

»
4 months ago, # |
  Vote: I like it +76 Vote: I do not like it

Thanks to MikeMirzayanov for Codeforces and Polygon platform.

»
4 months ago, # |
  Vote: I like it -42 Vote: I do not like it

But is it rated?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    rated for the participants with rating lower than 2100

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

What's up with these two comments? They seem to be visible for a split second when I reload this page.

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +29 Vote: I do not like it

    Comments with extremely low rating don't get deleted, they only get style="display:none" applied to them when the page loads

»
4 months ago, # |
  Vote: I like it -37 Vote: I do not like it

But ?detaR tI sI

»
4 months ago, # |
  Vote: I like it -15 Vote: I do not like it

hope not a mathforces or hackforces

»
4 months ago, # |
  Vote: I like it -121 Vote: I do not like it

Downvoted the blog already. Because the last 2 educational rounds were shitty.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hey man you forgot to Thanks MikeMirzayanov for Codeforces and Polygon platform.

»
4 months ago, # |
  Vote: I like it +156 Vote: I do not like it

i will stop commenting ..

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

10 mins penalty or 20 mins?

»
4 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Some upvotes please...

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

Please do not disable problemset submissions during contest.

»
4 months ago, # |
  Vote: I like it -63 Vote: I do not like it

Some downvotes please, I want to reach desired 69 contribution.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I love how this actually worked, now I have 69 contribution.

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

8000+ participation just wow gonna be challenging :)

»
4 months ago, # |
  Vote: I like it +37 Vote: I do not like it

why 10 minutes delay :(

»
4 months ago, # |
  Vote: I like it -30 Vote: I do not like it

I love CodeForces delays ^___^

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

what's the reason behind the delay ??

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I HATE CODEFORCES DELAY

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

10 Min delay !! Welcome back codeforces <3

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

10 seconds --> F5 --> 10 minutes :)

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Codeforces site already running slow, even before contest has started.

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

I think there is a problem, contest is delayed but Hightail was able to parse 2 question's TC. Using this anyone can get extra time in these scenarios.

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

+10 minutes in my wasting time sad :(

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

502 Bad Getaway-- CF wants to make you late for school.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope there woudln't be any lagginess during the contest since we're having ~9k participants

»
4 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Educational rounds are useless !!

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Well 9000 participants ! Love codeforces and this competitive programmers family.

»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

"IS IT RATED?" in CodeForces is just the same as "Is ThIs Loss?" in reddit && other meme portals :)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

9k! Congrats!

»
4 months ago, # |
  Vote: I like it -16 Vote: I do not like it

is this a div1 contest!! :|

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Any hints for C and D?

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

    D: You don't have to fill the entire table, just try to fill exactly one column and exactly one row, other cells are 0

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

      Why does this method work? Any intuition or proof? Thanks :)

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it +21 Vote: I do not like it

        Suppose you constructed an answer with some number x in cell [i, j].

        Then you may:

        1) Set ans[i, j] = ans[i, j] xor x

        2) Set ans[i, 1] = ans[i, 1] xor x

        3) Set ans[1, j] = ans[1, j] xor x

        4) Set ans[1, 1] = ans[1, 1] xor x

        Then all xor-values of all rows and columns will remain the same, but we will get rid of some non-zero number.

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

          This was beautiful. Thanks for the nice contest :)

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

        I think it's like this;

        Let a = (first column) xor (all rows from 2 to n)

        and b = (first row) xor (all columns from 2 to m)

        Both a and b represent cell(1,1) xor submatrix((2,2) to (n,m)), so they should be equal.

        If they are not equal then it's impossible to construct a matrix that satisfies the given constraints.

        And if they are equal, then we can fill all the submatrix((2,2) to (n,m)) with zeros and no contradiction will occur.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you elaborate the last line — "And if they are equal, then we can fill all the submatrix((2,2) to (n,m)) with zeros and no contradiction will occur."

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You're right, I didn't know how to explain that part very well.Let me try again.

            At first I thought; what can stop us from filling all of that submatrix with zeros? the only "possible problem" will be at the cell (1,1) because of the two values a and b(from the above comment); they represent the same thing but have different expressions that depend on the two input arrays.So they must be equal(or else no matrix will be correct no matter the values you choose).

            Now that the submatrix is all zeros, and the value at cell (1,1) is fixed, can we have another "possible problem" or "contradiction" with the other cells ? (cells (1,2) to (1,m) and (2,1) to (n,1)).

            No, because the xor of any of these columns/rows(columns [2,m] and rows [2,n]) only depends of the first cell in that column/row and the zeros, so in other words no column/row will touch the first cell in any other column/row.

            So for any of these columns/rows nothing is stopping us from putting the value of it's first cell as the xor of all it's cells(since all the others are 0s, the result will be correct).

            Try to come up with counterexamples and you'll get it.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          what will be there in cell(1,1)?

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            We chose to fill the submatrix from (2,2) to (n,m) with zeros, so a and b(from the above comment) will both be equal to the value in (1,1).

            Using the two input arrays;

            a = b1 ^ a2 ^ a3 ^ ... ^ an

            b = a1 ^ b2 ^ b3 ^ ... ^ bm

            You need to verify if they are both equal.

            If they are, fill that submatrix with zeros, fill the first row like this:

            matrix[1][i] = bi for i in [2,m] and matrix[i][1] = ai for i in [2,n].

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          @glays I wanted to know can you give any proof/surety that by following above strategy there is no way such that if you use use some other strategy you can make a matrix while this method returns "NO" i.e answer doesn't exist using this strategy?

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

            I understand what you mean, try reading these comments:

            first

            second

            Cleaner and better proof from BledDest

            Also re-read the editorial.The first equality in it must be true, because both expressions represent the xor of all elements in the matrix, so they must be equal.If not, it's just impossible i.e. these constraints can not form a matrix.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Well, first off I didn't AC problem C but I hope my approach was correctly. Basically, you can observe that since there are only 2 rows, and you need to visit every glade exactly once, you need to travel in a snake-like pattern from the start (going down, left, up, right, down, etc.). But you can also go all the way to the last glade of the row and 'loop' back to visit all the other unvisited glades in the other row. Please correct me if this approach doesn't work! Thanks.

    Edit: I suck and created an array too small. It passed afterwards.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i thought exactly that but could not implement it...like : for going all the way to n... same cell can be multiplied with different number like 1 if we come straight from 0 or 3 if we zigzag like : 0->up->right->down....how do calculate for such different values

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        Yeah that was tricky for me as well. Let's say you're at row 1 column 3 (1 indexed). You can get here and multiply by 2 (by going right from the start) or by 4 (if you zigzag down from the start). When you calculate going all the way to the last column of the row and return on the second row from this glade, you can notice that the difference between going right from glade (1, 1) and right from glade (1, 3) is the sum of all the numbers from ((1, 3) to (1, n) + (2, n) to (2, 3)) * (4 — 2). Hence, you can use prefix sums here to speed up the computation.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
          Rev. 5   Vote: I like it -9 Vote: I do not like it

          ....

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

            You multiply by (4-2) because if you reach glade (1, 3) and multiply by 2 (and then go all the way to the last column and return), then you multiply the subsequent numbers by 3, 4, 5, etc.

            If you reach glade (1, 3) and multiply by 4 (going to the last column and return), then you multiply the subsequent numbers by 5, 6, 7, etc.

            Since you are multiplying the same set of numbers in the same order, by putting the multiples side-by-side you can notice the following:

            First situation: 3, 4, 5, 6...

            Second situation: 5, 6, 7, 8...

            Each number in the first situation is multiplied 2 less than each number in the second situation. Thus, the difference between the sums of the two situations is (sum of numbers from (1, 4) to last column and return) * 2, with 2 being the same thing as (4-2).

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

    Consider every point as "End" cell where vasya will end his journey and also the fact that each cell could be visited only once. You'll notice only possible end points are indices with (i+j) "ODD". (First move in a zig-zag manner to the adjacent cell at same column and traverse all the way round back to the End cell). P.S Zig-Zag manner means move to unvisited cell at same column and from there to adjacent cell at next column(Repeat). Please do ask if its not clear.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is one pattern of going only: Zigzagging up to the ith column, then go all the way to column n and return. I don't want to get in details of how to calculate this, pretty long. But yeah you get the basic idea

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I got it, but couldn't find that ith column fast enough =(

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it +14 Vote: I do not like it

    Suppose you're at cell (1,1), there are three possible ways.Either you;

    • go straight to (1,n) then down to (2,n) and back to (2,1).

    • go down to (2,1) then straight to (2,n) and up to (1,n) then back to (1,2).

    • zigzag your way to (2,1) then (2,2) then (1,2) then (1,3).Now that you're at (1,3), repeat.

    The first two can be precalculated using (painful and annoying) prefix and suffix sums.But it's not obvious at first.

    By the way, there are only n different routes.

»
4 months ago, # |
  Vote: I like it +16 Vote: I do not like it

In F, you always put edge at same place right?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think so, but i got WA. :(

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

      I am missing some corner case. Mine gets WA on 23rd so I think I am right.

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

    Yes

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't have time to implent anything, but I figured the same too. It seems weird though, because if it's true, then the queries make zero sense.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, there is always one optimal place that the edge should always be placed

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's 6 pretest for D?

»
4 months ago, # |
  Vote: I like it -24 Vote: I do not like it

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

I changed all long long into int, all long double into double, then I passed problem E instead of TLE. But I submitted it when the contest was already finished.

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

    And you still leave endls in your code. I changed endl to \n and it got AC in 750 ms instead of 1980

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

      I tried several times again. I got TLE on 8 with long long, long double and endl. 1980ms with int, double and \n. 1590ms with long long, long double and endl. 1434ms with int, double and \n. 311ms with printf.

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What about long long main() ?

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

        you can replace int main() with int32_t main();

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Or you can just write main(). By defaualt it assumes int. and No it's not undefined behaviour.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's also not something supported in the C++ standard. In might work in GCC (or at least the version of GCC that codeforces uses), but it won't work on other compilers (try visual studio and clang).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Show unofficial isn't working!

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

    Because it's Educational and after hacking phase you can choose division.

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Problem D can be solved using flow. Bits are independent of each other, so treat one at time. Do matching to see where to put the 1's. XOR into some matrix and check at the end.

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

    Flow sounds a bit overkill

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe, but solution is quick when you've seen similar problem.

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

    How do you build the network?

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

      First consider simpler problem. Limit values to 0 and 1. If we want the values in a row to XOR to 1, there must be an odd number of 1s in that row; if we want it to XOR to 0, there must be an even number of 1's. It is the same for columns.

      The number of elements in a row depends on how many columns there are, and vice versa.

      There are some cases to consider. Let number of columns be c. If c is even, and we want some row to XOR to 1, there can be at most c - 1 1's in that row; if we want to XOR to 0 and c is even, we can put all c ones in that row. The other cases follow from this and are easy to work out. These values become the capacity of edges from source to row and and column to sink...

      For edges in between, place edge between each row and column. Saturating the edge is like putting a 1 in the cell that is the intersection of that row and column. Obviously we can only put a single 1 or 0 in a cell so those edges have unit capacity.

      Now we run max flow on this bipartite graph. Saturated edges represent cells with 1 in them.

      ...

      Now we take the same problem for general case of numbers, not just 0 and 1. Note that all bits in binary representation of number are independent, as I said before.

      So we take the simpler problem I described above and do it 30 times, for bits indexed 0 to 29, because the problem is bounded by a billion in the problem statement, the base-two log of a billion is just over 29.

      Do all the flows and put the resulting values in the matrix. To check if there even exists a matrix we simply validate the matrix produced by XORing its rows and columns and comparing to inputted XOR values.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for explaining. Still confusing because there seems to be no explicit constraint on parity. For example, nothing prevents an edge of capacity 8 going to sink from saturating to 7.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          We want the maximal flow, so it’ll saturate fully if it can. That’s what we want.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    That's why you are still blue.

»
4 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Why "wrong answer 154th numbers differ — expected: '-0.0000000', found: '-0.0000000', error = '-0.0000000'"?

Submission

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it

    This is one of the standard checkers from polygon, there should be no bugs. However, its output on par with the integer sequence one is definitely broken now. It looks like it checks fine, just outputs the wrong thing.

  • »
    »
    4 months ago, # ^ |
    Rev. 3   Vote: I like it +31 Vote: I do not like it

    Like take a look at any wrong submission for problem B or F, output of the checker is wrong while the answer is also wrong.

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

can you show me that why my code in Problem C got WA in test 7, please :(((((. I think my code WA in bignum but can't fix it :(((( http://codeforces.com/contest/1016/submission/41190766

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I submitted a hack but the verdict is still not shown (spinner for the last 10 minutes). How much time does it usually take for hacks to show the verdict?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E?

  • »
    »
    4 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    consider query point Q. find intersection of AQ and BQ with x-axis. The amount of x-axis covered in this range is proportional to shade time. To get actual shade time multiply by (y - sy) / y. I think my logic is correct although I couldn't debug my code.

»
4 months ago, # |
  Vote: I like it -32 Vote: I do not like it

Is It Rated?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nineteen minutes lagging i hate my internet XD

»
4 months ago, # |
  Vote: I like it -35 Vote: I do not like it

I saw some solution use hashing with only 1 modulo and got hacked on problem B. I am considering which type of test did hackers use to hack?

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

    Lol why did you use hashing here? n00b

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why there's no * after those orange or higher people ?

All participants are official ?

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

    Yup, it's been like that for a while now. Everyone is official, rated status doesn't depend on that.

»
4 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Is It Rated or Contributed?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will there be a tutorial? Anyway, I will try to solve more problem myself. :p

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

Congrats to djp_cqq, who managed to gain a 450+ rating change after his first contest!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please help me with my E problem? No idea how to make it work faster, O(nlogn).

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where are the solutions?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the judge for E broken? I do not think this submission should TLE...

I even tested the solutions of people on my friends list who got it AC, and they also get TLE...

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell me which submissions have got AC, but now is catching TLE?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      adedalic See here for the AC one, and the copy-pasted one I submitted that TLEs.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Seems that compilers differ, maybe C++11 one has slower iostream functions than C++17? Probably it's worth trying getting rid of cout for printf or submitting in C++17.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        More over, it seems that IO operation more than twice slower in C++11 in comparison to C++17

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I barely get my initial submission accepted in C++14 and it still TLEs in C++17.

          cin/cout with the special speedup should be on par with printf though...

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Lol the problem was taking in floating-point numbers instead of integers, if you take the input as integers it still passes C++11 (I know from stalking vamaddur's submissions)

            Apparently difference is so great, taking in floating point makes the whole program (which is nlogn) take more than 2x runtime.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No editorial?

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Can somebody explain for problem D why the greedy always works/doesn't mess up the impossible case?

»
4 months 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).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain C

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was really educated.

»
4 months ago, # |
  Vote: I like it -29 Vote: I do not like it

But is it contributed?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi!