Автор BledDest, история, 3 недели назад, По-русски,

Привет, Codeforces!

5 сентября в 18:05 по Москве начнётся Educational Codeforces Round 28.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 6 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил PikMike Пикляев и Владимир 0n25 Петров.

Удачи в раунде! Успешных решений!

UPD. Разбор.

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

Rank Competitor Problems Solved Penalty
1 eddy1021 6 148
2 bmerry 6 168
3 uwi 6 173
4 fzzzq2002 6 183
5 wrinx 6 192

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 halyavin 74:-11
2 Dmit_riy 17
3 scaurb 12
4 winter545 12:-3
5 Benq 9

Было сделано 169 успешных и 113 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Problem Competitor Penalty
A eddy1021 0:02
B wrinx 0:06
C Rawnd 0:10
D alei 0:11
E chitanda 0:20
F HIR180 0:06

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

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

Hopefully it wont have geometry problems :)

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

    ahahahahhahah xD

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

    Don't worry, we don't like geometry as much as you do :) I guarantee nothing for this round, of course, we might have prepared such. Still you can check amount of these in our previous rounds.

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

    Did I miss some recent incident with a geometry problem? Or do you mean that both times Education Round had a geometry problem we had a lot of hacks (30 hacks were a lot back then...) / authors solution were not precise enough?

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

      I believe that it's because 432 round has 2 geometry problems in div.2

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

        checking whether dot product in 5D is >0
        geometry

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

          is there a way to solve that problem better than O(N3) ?

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

            It's actually O(n) since for any given point A there can be at most 10 points such that for each pair B, C angle between vectors AB and AC is greater then or equal to 90 degrees, so naive solution will find two points B and C for which angle between AB and AC is less than 90 among first 11 points

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

              It can be O(1) ;). We don't need to read input if n>=12

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

                no, i mean in general. Leave that n>=11 thing. Given n points can we do better than O(N3) ? Or just modify the question to: dot product >= C (some constant)

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

                  I don't get what you're asking about. If we consider question "dot product >= C" then it is completely different problem.

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

                @swistakk Big-o notation describes worst-case complexity, so more like Ω(1) as a best case scenario.

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

                  I know what big O stands for and I maintain my opinion that this task can be solved in O(1).

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

                  (meme is life)

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

                  Look, I'm not arguing for the point of arguing. It seems my knowledge of asymptotic notations is incomplete. May I ask why it's the upper bound?

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

                  Consider such algorithm:

                  int n;
                  cin>>n;
                  if (n >= 12) {
                    cout<<"0"<<endl;
                    return 0;
                  }
                  do_some_stuff_with_n_points();
                  

                  Running time of our algorithm for every n is bounded by constant which is running time for 11 points. Hence it's O(1).

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

                  I misread your comment earlier. Do you mean to say something like this: https://pasteboard.co/GJ0r6xP.png

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

                  I am not sure you get what O(1) is here. What is complexity of algorithm that for an input of length n does respectively: 100, 234, 12, 1243543, 1, 78945673657578458567, 5, 5, 5, 5, 5, 5, 5, ... operations (I mean, 100 operations for n=1, 234 for n=2 etc.)? It's O(1), because it runs in time at most 78945673657578458567 no matter the value of n is.

                  Now what is complexity of algorithm that does that many operations: 1^3, 2^3, ..., 11^3, 1, 1, 1, 1, 1, 1, 1, ...? It's O(1)! There no such complexity as "O(n) for n<=15 and O(1) for n>15", it's just O(1).

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

                  Gimme more MemeS!

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

    I bought an Geometry book after CF R 432

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

Is it rated ? No ofc. give me some down votes

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

Все мы радовались когда узнали что будут учебные контеста. Как вы думаете оправдались ли ожидание? Насколько полезно эти контесты?

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

I hope that today's round gives me feeling of competing on codeforces and not on geometryforces or implementationforces!

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

Why doesnt Educational round records are added to Contest log.

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

Why doesnt CF add Educational Rounds records to contest log

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

    We also have just discussed this topic. I plan to update all previous announcement blogs with this data after the results of current contest are up.

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

Ban UWI please.

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

Ples senpais give me some up votess :v

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

I m Gonna solve All six questions.......(Just Kidding)

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

I Have not solved more than 2 question in any Codeforces contest but Today i m gonna........Lol

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

Can't wait the contest to end so I can watch people getting hacked by uwi!

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

Don't worry guys contest are rate, try hardest and give UPVOTES PLZ!!!!

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

Don't worry guy contest is rate! UPVOTE ME PLZ!

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

Предвещаю опасность! Нет благодарности Мише!

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

is contet affect my rate?

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

How to solve the f**k problem A???

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

i can only solve F

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

please uwi dont hack my solutio.. wait a minute I did not solve any thing -_-

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

please uwi do not hack my solutions ... wait a minute I did not solve anything -_-

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

I have a lot problem with Engrisz

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

Here it goes! Here it goes! Let the hacking begin uwi!

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

I've made simple dp on tree in E but fail. I assume that because of long long overflow. Is that good solution?

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

why is problem F a problem F

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

    It's because there should have also been problem G, just didn't have enough time to prepare it.

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

Когда будет доступен подробный разбор задач?

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

Now coz its over somebody tell me A. I did nothing today :(

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

What's the test #6 of problem F?
Got RE all the time :(

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

Do not use cin in F!!
sigh.....

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

    Or use cin with ios_base::sync_with_stdio(0);

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

      But then i cant use printf safely.
      You know, sometimes printf is much more convenient than cout, such as printf("%d %d %d\n", i, j, k) vs cout << i << " " << j " " k << endl;

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

upd. Спасибо, исправили

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

Did someone solve problem D with a 2D Segment Tree?

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

    I solved it using 2D sparse tables, it used n^2logn memory, but O(1) queries :D

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

    It can be solved easily using 2d RMQ. You can check my submission

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

    It can also be solved with pure binary search. sort the times and binary search on the first event that makes the screen broken. in each check of the binary search, use a table of N by M and another dp one. fill it with 0's and put 1's on the places that were broken until that event. use dp to find in O(NM) the largest square completely made out of 1's. if its size is at least k, then at this moment of time the screen is already ruined, otherwise it's not.

    total time: O(NM * log(NM))

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

The problem F is too easy. It should be problem B.

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

It seems that the checker for the problem F is incorrect.
My solution got AC, even though the absolute error is more than 0.0001 on the testcase #15.

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

    (14792.348508-14792.3)/14792.348508 = 3.27926292e-6 < 1e-4.

    the statements says relative or absolute error, so in this case relative error is used.

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

      Previously only absolute was in statement, it was changed after this comment

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

It was nice round xD,although i was only able to Solve Problem A, and B was greedy but :/ welp

(After Solving A)

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

Today is my birthday. So please don't hack my solutions @uwi :)

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

Is it unrated round?

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

Is it rated round?

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

BledDest, you seem to have forgotten to add the editorial to contest materials, please add it so people can find it more easily. Thanks!

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

It is very good that such competitions are held in the world, they give a chance to young and talented people to show themselves restaurants near me