Блог пользователя danya.smelskiy

Автор danya.smelskiy, 6 лет назад, По-русски

Привет, Codeforces!

В 24.11.2018 10:35 (Московское время) состоится Codeforces Round #524 (Div. 2). Раунд будет рейтинговым для второго дивизиона (рейтинг ниже 2100). Как обычно, участники из первого дивизиона могут написать контест вне конкурса.

На раунде вам будет предложено 6 задач и 2 часа и 15 минут на их решение.

Задачи были подготовлены мной, arsijo и stanislav.bezkorovainyi.

Спасибо большое Markellonchik, iSlava и Barichek за помощь в тестировании задач, Jajceslav за рисунки к задачам, а также MikeMirzayanov за замечательные платформы Codeforces и Polygon.

Раунд основан на II этапе Всеукраинской олимпиады по информатике, поэтому, пожалуйста, не обсуждайте задачи до начала системного тестирования.

UPD: Разбалловка: 500 — 750 — 1250 — 1750 — 2250 — 2500.

UPD2: Поздравляем победителей:

  1. Qingzhi_chan
  2. Laggay
  3. H-C-H
  4. lqs2015
  5. Trrui

UPD3: Разбор задач.

  • Проголосовать: нравится
  • +276
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

it is a good time for chinese,^_^

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

I will put my best effort to keep this green color :p

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

II. stage of Turkish Olympiad in Informatics is at the same time, clashes with the contest:((

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

good timing , coming expert i hope

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -25 Проголосовать: не нравится

:3

»
6 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Nice, it's been a while since we had pictures to the problems!

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

2 hours and 15 minutes is good for 6 problems.

:)

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

It's a very bad time for a Bangladeshi Participator. :(

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

Your rating graph is inspiring. Hope for a good contest. :)

»
6 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

it's good that no one will wake up that early to make a DDos-attack

»
6 лет назад, # |
  Проголосовать: нравится -57 Проголосовать: не нравится

Is it rated?

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

i wanna be green today.....

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good Luck To Everyone! :D

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Does CHelper work when the codeforces is in HTTPS? Any workaround? All of a sudden, codeforces is redirecting all the requests to HTTPS, and now, I'm unable to participate. :( Parse Contest feature doesn't parse test cases. So, that isn't an option as well.

»
6 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

E is 2500 points. Is the round wrong, or the announcement?

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +48 Проголосовать: не нравится

Never seen such one dimensionality in any contest in my life ever!!!

All questions from C to E involves a matrix and problems from A to D require some type of maths.

Really disappointing problemset.

(EDIT- On the top of that, really really unbalanced problemset. The gap between C and D is not really ideal. Clearly a bad contest.)

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

what a problem C is!

How to solve it?

  • »
    »
    6 лет назад, # ^ |
    Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

    https://stackoverflow.com/questions/19753134/get-the-points-of-intersection-from-2-rectangles
    First find how many white and black are initially on board.
    For both rectangles(white cand black colored) calculate its area (say W and B).(number of cells)
    Then find the intersection of two rectangles that many cells will be deducted from W count.(black color will overwrite white color)
    Now from this 3 information you can find final answer.

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    judge overlap

    If no intervals overlap

    I think u can solve it,its not very hard

    If exist, initialize the overlap, that is, turn the white part back to black.

    my code seem very stupid.....

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I just spend all time of contest for just finding the overlap area.

      • »
        »
        »
        »
        6 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Here is my code,its show how to find overlap area.

        scanf("%I64d%I64d",&n,&m);

        scanf("%I64d%I64d%I64d%I64d",&x[1],&y[1],&x[2],&y[2]);

        scanf("%I64d%I64d%I64d%I64d",&x[3],&y[3],&x[4],&y[4]);

        x[5] = max(x[1],x[3]); x[6] = min(x[2],x[4]);

        y[5] = max(y[1],y[3]); y[6] = min(y[2],y[4]);

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It was little confusing given coordinates were inverted.(Bottom left (1,1))

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I spent almost of the time just to find the overlap area oh god, first i had thought it 's really simple :(

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes,when i first to face the problem “how to find the overlapping area of rectangle”,it spent my 2 days....

      It impressed me, so I remember it very well......

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится -9 Проголосовать: не нравится

    C title topic: At the beginning, there is a checkerboard with black and white colors. Initially, the area of ​​area one (x1 y1) (x2 x2) (the points in the lower left and lower right corners form a rectangular area) are all painted white. Then apply the area of ​​area two (x3 y3) (x4 y4) to black. Find the number of black and white grids on the final board.

    answer:

    In the calculation area one (x1 y1) (x2 y2), there is a white grid w1 black grid b1 at the beginning. In the calculation area two (x3 y3) (x4 y4) area, there is a white grid w3 black grid b3 Calculate the area where the two areas intersect. The three (x5 y5) (x6 x6) area begins with a white grid w2 black grid b2

    At the beginning, there are orw white plaids on the board. Orb black plaids. 1. The area is painted white. orw += b1, orb -= b1 2. The area where the area two intersects with the area one or two is painted black. 2.1 Get the white of area two orb += w3, orw -= w3 2.2 Obtain the black of the intersecting part orb += b2, orw -= b2

    The number of black grids added on orb is w3 + b2 — b1 Corresponding. The number of white lattices reduced on orw is -(w3 + b2 — b1)

»
6 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

I am not enjoying codeforces short rounds anymore :(

»
6 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

seems like the authors love matrix and segments very much:D

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm so upset just 1 min and I would've submitted C I just wrote a variable instead of another damn it

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Implementationforces.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what is pretest 2 in problem C ?

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

The round is based on the II stage of Ukrainian Olympiad in Informatics,

that is why please do not discuss the problems before the system testing start.

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

It's only a mathforces round, why you hef to be so mad?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

I don't really understand why problems like C appears in contest like this. I could understand it, if contest would have 5h.

But excluding this task contest was really good prepared and there wasn't dos attack during the contest ;)

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Tedious and uninspiring problems. A, B, C are simply mathematical, formula based problems. E, a rather disappointing use case of Manacher's algorithm (as if author had to come up with a problem and worked other way round to "hide" the obvious use of Manacher's).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I actually hate chessboard problems they're not fun to think about at all

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    There was nothing related chess moves, just a rectangle in which adjacent colors are different, So you can't call it that.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

its not even mathforces :((((((((((((

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

its not even mathforces :(((((((((((

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Loved problem D. Hope it passes systest.

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

This contest is a brilliant!

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

hacking attempt failed for (A) 100000000 1 , 46153884

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I've sent my solution of problem C a couple of times, but each time the system returned WA on pretest #1 and didn't show this try in the scoreboard (like -1, -2, and so on). However, on my PC in code::blocks, my solution outputs the correct answer on the same pretest #1 (I checked it after the end). How could that happen?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Undefined behavior is a thing.

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    If the solution is not passed on pretest 1. Then the submission will not be considered as a submission or wrong submission. If solution passes at least one pretest then it will be counted as a submission and will be considered as wrong submissions if it doesn't pass all the test.

»
6 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

who can tell me when the system test will begin?

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

I think it wasn't clear that O(26 × R × C2) would pass for problem E. Exact number of operations is . I used hashing to get it in O(R × C2) after wasting so much time.

»
6 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Why Pending System Testing is still lasting?

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Disgusting problems :/

»
6 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

Whats the point in not discussing problems and delaying sys tests when the solutions are visible.

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

todays contest was about maths and implementation..XD

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

  • »
    »
    6 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

    I can tell you, but it was told to not discuss problems before systests. :(

    Edit:

    -Make a segment tree where in every node you keep a set containing the pair {left border, the minimum right border of an interval that starts after the current one(including the current one)} for every interval corresponding to that node

    -We can construct this tree in n log^2 n time and answer every query online in log^2 n by using the lower_bound operation on the set in the segment tree nodes.

    There is an log n per query solution too but this works too

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Why not let system testing start?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is it right participants have to wait for system testing to begin over an hour?

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

There should definitely be an official announcement in cases where system testing is supposed to start much later than the normal routine.

»
6 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

May be system testing will start after 5 hours from the ending of contest. As there is 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest running at GYM.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

System testing started!

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится -27 Проголосовать: не нравится

problem B are similar to 486A

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The two problems are very similar...

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    wow, why so many downvotes:( ? i just want to point out that the problem is copy-paste able (just add extra code for query and - f(l-1)) so codeforces will be more careful to choose problem, me and my friends who solved 486A just copy paste and modify the submission, maybe i should more clear about what i trying to say...

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the duration of 2h and 15 min . I managed to submit C at 02:08 .

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

На самой олимпиаде был полный проблемсет или только определенные задачи из данного контеста?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

re because of 1 character :(

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve problem E?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

fully calculation based, though set was cool

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

butthurt! 4 accounts of the top 5 are fakes!!

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

.