By BledDest, history, 3 months ago, translation, In English,

Hello Codeforces!

On September 05, 18:05 MSK Educational Codeforces Round 28 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.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day 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 prepared by Mikhail PikMike Piklyaev, Vladimir 0n25 Petrov and me.

Good luck to all participants!

UPD. Editorial can be found here.

Congratulations to the winners:

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

Congratulations to the best hackers:

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

169 successful hacks and 113 unsuccessful hacks were made in total!

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

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

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

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

Hopefully it wont have geometry problems :)

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

    ahahahahhahah xD

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

    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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

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

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

        checking whether dot product in 5D is >0
        geometry

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

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

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

            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

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

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

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

                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)

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

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

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

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

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

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

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

                  (meme is life)

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

                  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?

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

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

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

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

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

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

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

                  Gimme more MemeS!

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

    I bought an Geometry book after CF R 432

»
3 months ago, # |
  Vote: I like it -60 Vote: I do not like it

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

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

    So is it rated or not?

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

      Why must unintelligent specimen like you plague our CodeForces community?

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

        Unfortunately, attention seeking exists in almost all communities. They will stop if you ignore them.

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

      not

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

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

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

Why doesnt CF add Educational Rounds records to contest log

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

    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 months ago, # |
  Vote: I like it +53 Vote: I do not like it

Ban UWI please.

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

Ples senpais give me some up votess :v

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

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

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

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

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

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

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

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

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

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

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

i can only solve F

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

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

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

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

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

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

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

why is problem F a problem F

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

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

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

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

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

    Count number of ones after index i and number of zeros before index i. Now answer could be zeros+ones.

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

      why would that work. I could not solve anything. And still have no idea. I checked bmerry solution and he did the same. But why ;-;

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

        Because zeros should be before ones. Delete all zeros before i. Delete all ones after i.

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

          isn't that delete all 1s before i and all 0 after i. so at every iteration, I need to assume that its 1 and move accordingly??

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

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

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

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

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

      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;

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

(After Solving A)

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

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

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

Is it unrated round?

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

Is it rated round?

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

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

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

Hey guys I can't figure out problem A why the answer of this input is "4"? input : 0 1 0 0 1 It seems maximum possible is 3 011 or 001 could you help me?