By awoo, history, 6 years 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 Roms 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 ppc_qjd 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 Neon 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 comfi 1:16

UPD: Editorial

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +76 Vote: I do not like it

Thanks to MikeMirzayanov for Codeforces and Polygon platform.

»
6 years ago, # |
  Vote: I like it -42 Vote: I do not like it

But is it rated?

»
6 years 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.

  • »
    »
    6 years 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

»
6 years ago, # |
  Vote: I like it -37 Vote: I do not like it

But ?detaR tI sI

»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

hope not a mathforces or hackforces

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +156 Vote: I do not like it

i will stop commenting ..

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

10 mins penalty or 20 mins?

»
6 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Some upvotes please...

»
6 years ago, # |
  Vote: I like it -63 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

why 10 minutes delay :(

»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

I love CodeForces delays ^___^

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

I HATE CODEFORCES DELAY

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

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

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
6 years 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.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

+10 minutes in my wasting time sad :(

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 years 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

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

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

»
6 years 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 :)

»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

is this a div1 contest!! :|

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any hints for C and D?

  • »
    »
    6 years 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

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

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

      • »
        »
        »
        »
        6 years 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.

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

          This was beautiful. Thanks for the nice contest :)

      • »
        »
        »
        »
        6 years 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.

        • »
          »
          »
          »
          »
          6 years 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."

          • »
            »
            »
            »
            »
            »
            6 years 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.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 years 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].

        • »
          »
          »
          »
          »
          6 years 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?

          • »
            »
            »
            »
            »
            »
            6 years 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.

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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

      • »
        »
        »
        »
        6 years 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.

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

          ....

          • »
            »
            »
            »
            »
            »
            6 years 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).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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 =(

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can sweep the entire column.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah :P it used prefix sums. So goddamn hard to implement and test, gosh, took me 20 minutes.

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years 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.

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

    Yes

  • »
    »
    6 years 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.

  • »
    »
    6 years 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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's 6 pretest for D?

»
6 years ago, # |
  Vote: I like it -24 Vote: I do not like it

»
6 years 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.

  • »
    »
    6 years 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

    • »
      »
      »
      6 years 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.

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What about long long main() ?

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

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

        • »
          »
          »
          »
          »
          6 years 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.

          • »
            »
            »
            »
            »
            »
            6 years 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).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Show unofficial isn't working!

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

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

»
6 years 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.

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

    Flow sounds a bit overkill

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

    How do you build the network?

    • »
      »
      »
      6 years 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.

      • »
        »
        »
        »
        6 years 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.

        • »
          »
          »
          »
          »
          6 years 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.

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

    That's why you are still blue.

»
6 years 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

  • »
    »
    6 years 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.

  • »
    »
    6 years 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.

»
6 years 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.me/contest/1016/submission/41190766

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E?

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Is It Rated?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nineteen minutes lagging i hate my internet XD

»
6 years 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?

»
6 years 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 ?

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Is It Rated or Contributed?

»
6 years 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

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

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

»
6 years 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).

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
6 years 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...

  • »
    »
    6 years 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?

    • »
      »
      »
      6 years 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.

      • »
        »
        »
        »
        6 years 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.

      • »
        »
        »
        »
        6 years 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

        • »
          »
          »
          »
          »
          6 years 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...

          • »
            »
            »
            »
            »
            »
            6 years 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.

»
6 years 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?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain C

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was really educated.

»
6 years ago, # |
  Vote: I like it -29 Vote: I do not like it

But is it contributed?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi!