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

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

On Sep/20/2018 17:45 (Moscow time) Educational Codeforces Round 51 (Rated for Div. 2) 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. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. 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 Roman Ajosteen Glazov, Ivan BledDest Androsov and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space University is proud to announce new partnerships for this year’s Hello Barcelona Programming Bootcamp — VTB and Indeed Tokyo, with the addition of team sponsors Phaze Ventures and Spark Labs.

VTB, the largest international bank based in Eastern Europe, continues to be an official partner of our Hello Programming Bootcamp series, adding further quality to the 3rd edition of the Hello Barcelona Programming Bootcamp by bringing their own participants, as well as by supporting top teams from around the world.

Indeed Tokyo is Japan’s branch of the #1 employment website in the world, giving job seekers free access to millions of jobs from thousands of company websites and job boards. As they sponsor for the second year in a row, Indeed continues to offer the best job opportunities to the boot camp participants as they gather in Barcelona from September 26 to October 4, 2018.

UPD: There was a bug in testset and validator for problem F, we are currently fixing the issue. The statement included the correct resrictions. We will rejudge all the solutions as soon as possible. The round can become unrated, we are discussing this at the moment.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 kmjp 6 210
2 MrDindows 6 223
3 elykuil 6 242
4 Nisiyama_Suzune 6 274
5 Fekete 6 274

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 299:-14
2 Laggy 100:-10
3 greencis 29:-2
4 Volkov_Ivan 19
5 dorijanlendvaj 13
694 successful hacks and 497 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A traxexeuler 0:03
B answhldkd 0:02
C ainta 0:06
D greencis 0:07
E tfg 0:38
F baggins 0:26
G yasugongshang 0:56

UPD2: We investigated the issue to get the following results. 10 people were noticeably affected (that took them more than 3 minutes of the working time). Round will surely be rated for other participants. As for the affected participants, we will look into the rating changes and revert them in case they are negative (set the participant into the unofficial participation mode).

UPD3: Editorial is out

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

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

Wish you all +100 rating!!!

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

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

thanks codeforces for three contest in a row.also waiting for a div-3 contest.

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

    Hope next div.3 will be soon :) Now I'm too busy with the studying and other activities but I'm trying to prepare it as soon as possible

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

      happy to hear this and waiting for it.

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

      I really need to say the amount and the quality of contests you prepare are interesting, although not each contest you prepare is perfect, but the overall desirable quality is stable, I don't know how difficult it is to prepare a contest, but I bet it is not easy at all, sometimes I notice that you give attention to negative feedback, when you should only consider the constructive one, try to avoid that, every active contestant in codeforces realizes the amount of effort and creativity you offer to the community

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

I haven't been able to do a contest in a while... all contests are either morning/noon on weekday or early morning on weekends (I live in US).

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

    Me too. Unfortunately it seems early morning weekends is the only option.

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

Short statement and strong pretest plz.

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

    no way

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

    Instead of that I would ask for balanced problem-set. You know what happened in last few Educational rounds.

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

    Pretests will indeed be strong. They will be as strong as System Test...

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

    Every one knows how to solve D except me.

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

      I struggled a lot with brute force and DSU, trying to find smoe formula. I even put the results in OEIS to see if it matched some known sequence. Then, when all failed and Ernesta was looking at me like "what are you doing, gaucho?", I realized it was solvable with DP.

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

        Same as you! However when I realize it could be solved with DP, I have no enough time.

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

Is it rated for Div. 3??

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

    No :)

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

    This round will be rated for the participants with rating lower than 2100.

    What this means ?

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

      Me too. I don't understand it!

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

        It means that if your rating is <2100, then after participation it will change.

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

      If Div.3 participants have rating which is less than zero and their rating is unsigned short int, then it is indeed unrated for the.

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

        How about (unsigned short int)-65532?

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

          Imagine having a rating this low. You literally had to put effort into it.

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

            Well, check this guy out: .o.

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

              this appears to be done deliberately

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

                Yeah, that's my point. Effort made (yet perhaps he lost his patience too soon :D )

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

I have not competed in a contest in a long time. I think last time was before my sweet cow "Ernesta" gave birth to tiny and soft brown and white "Vaquita linda".

Now I'll leave the barn for a while and try to have a little fun with this contest. Or maybe I'll take my laptop to the field, and use the sheeps and cows as inspiration while I write code under the sun, gazing at the sunflowers and listening to the little singing birds.

Viva Argentina! Poder gaucho FTW!

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

    Don't know how much truth is there in whatever you wrote but if it is true then it is friggin' awesome.

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

4 consecutive contests what a great week

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

Delay :(

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

    How much is your RPS? (reload per second) ;D

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

      You don't need a reload. The pop-up that informs you that the round has started won't show up if the contest was delayed.

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

10-minute delay. -_-

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

after this week my rating will be lower than ever.

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

D — Delay P — Problem

DP

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

delay in Education rounds is no more a surprise for me, It has become a trend.

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

Delay is for registering for next contest.

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

I am staying at office late to take part in the contest and it just got delayed -_- . Now I may have to miss it :(

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

is it rated?

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

Problem A was unexpectedly too much implementation based :(

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

    I wasted time, thinking that there must be a simple and elegant solution. But I was wrong :(

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

      i started with A but then noticed B was getting more submissions.but i got late for D

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

      It seems to me that you can always find the answer by only looking at the first 3 characters, once you know the count of characters of each type in the string. Maybe that is a little more elegant than the solution you found?

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

    This is my solution of A 43153166, I don't know if this is too much implementation for A.

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

when you finish doable problems 25 minutes before and keep on refreshing the page to see your rank falling :(

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

    my mind just goes back to "candidate master in next contest"

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

Is this rated!

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

How to solve F?

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

    Delete a tree from the graph. You are left with a graph of at most 42 nodes. You can use distance pre-processing on the tree (lca) and on the remaining graph (floyd-warshall) to answer the queries.

    For more details: http://codeforces.com/contest/1051/submission/43144878

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

    Cut the given graph down to any spanning tree. There will be at most ~20 spare edges, you can calculate distance between any two nodes in O(log n) if you drop these spare edges out and consider only spanning tree.

    Now we will have to consider edges that we dropped out. Let G be complete graph where edge (U,V) is minimum of the path between U and V in the spanning tree and the length of spare edge between (U,V) if it exists. G contains only nodes from the initial graph which have at least one spare edge attached to it, so G is not larger than ~40 nodes. Let's calculate the shortest path between any two nodes in G (e.g. using Floyd algo).

    Ok, now for each query we just take the spanning tree path length between U and V as the initial answer and try to make it better by choosing every two vertices U', V' from G and taking spanning tree paths U-U' and V'-V plus G path U'-V'.

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

      Wtf is wrong with you guys? The above explanation is detailed and perfectly fine, why downvotes?

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

        People downvoted the post because they assumed the downvotes meant the explanation was wrong, without bothering to actually read it. Or perhaps they read it and the downvotes subconsciously made them think it's wrong. A vicious cycle.

        Perhaps a bit of asch conformity

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

    I think it's easier to think about it this way:

    Let T be any spanning tree of the graph, S be the set of edges in the original graph but not in T, and V be the set of vertices in S. Note |V| ≤ 42. Then any path that is not entirely in the tree must pass through at least one vertex in V. So the answer for a query (u, v) is min((dist(u, v) in the tree), (dist(w, u) + dist(w, v))) over all w in V. So you can run a Dijkstra from all such w and compute the answers this way.

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

      this is more clear explanation ,but isn't it dijkstra instead of bfs.

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

Damn man, what was the pretest 6 in C ;_;

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

A huge skill gap between D and E/F :(

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

    Don't see that much of a gap between D and E, however E is really tricky in implementation

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

I think A was harder than B/C/D.

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

    not harder than D

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

      I disagree. Spent 45mins on A, 40 mins on D.

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

        So work hard on your implementation bro. ;D

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

        I wasted 30 minutes trying to utilize my A's answer and thinking about what de hell I had done wrong.

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

swap(A, B);

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

What's test 4 in E?

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

    try this: 101 0 101

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

    Fuck! I wrote

    if (a[i] == '0' and l[1] == '0') {
      f[i] = f[i + 1];
    } else {
      // ...
    }
    

    instead of

    if (a[i] == '0') {
      if (l[1] == '0') f[i] = f[i + 1];
    } else {
      // ...
    }
    

    The difference is not immediately obvious. :'(

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

Can someone point out the mistake in this dp implementation for problem D ? http://codeforces.com/contest/1051/submission/43148059

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

    Please check this when previous column layer is BW or WB then adding BB or WW in current column doesn't change number of components

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

      i did check that and that is incorporated in the solution . l=0 implies WW l=1 implies BW l=2 implies WB and l=3 implies BB if you go through the code.

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

        You are not doing transition f(i,0,k) from f(i-1,1,k) and f(i-1, 2,k). Similarly you are missing many transitions for each case

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

Got my mistake

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

Expected solution for C ? I used some DP .

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

    It's pure implementation , there's no need for a dp!

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

Isn't C's problem statement confusing? I initially interpreted that nice numbers are only on the basis of the multiset s, not a and b.

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

    Yes. The English problem statement is incorrect.

    To quote: "Vasya has a multiset s consisting of n integer numbers. Vasya calls some number x nice if it appears in the multiset exactly once."

    When you type "the multiset", it refers to some specific multiset (the one mentioned). If you were to write "a multiset", it could refer to some other multiset as well. The problem statement was unambiguous regarding which multiset is used to define which numbers are nice: "the multiset" s given in the problem statement.

    Pretty annoying to spend 20 minutes of competition time just trying to figure out what kind of error was left in the problem statement.

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

What is wrong with 43149226 for C?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    if count of x is odd,then it can be a nice number, not only count of x is 1
    such as
    8
    1 2 2 2 3 4 5 6
    it can be split : 1 2 3, 2 2 4 5 6
    
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But you can ignore that number and add it all to one of the two sets if if exists more than once which won't be nice.

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

      Got the problem. Thanks man.

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

    The problem statement is misleading, what they mean is that can you partition the multiset into A and B so that No. of nice elements w.r.t A in A= no. of nice elements w.r.t B in B Not

    no. of nice elements w.r.t S in A= no. of nice elements w.r.t S in B

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

      Yes I understood it right. Though WA.

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

Everyone must be so afraid of halyavin right now XD

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

In problem F,the statement says m<=100000. However,in test 11, m > 100005.

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

    yes, i was thinking something like this must have happened. was getting WA in the contest.

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

    i had kept my array size as 1e5 + 5.

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

For problem B the solution always exists ?

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

I think that there is an invalid test case in Problem F. It appears that the test case 11 has M > 100000.

TLE Code: 43149555

AC Code: 43144968

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

F,the data is wrong, since I get RE if I set MX=1e5+5, and get AC when I set MX=2e5+5

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

Lol, F's constraint is 1 ≤ n, m ≤ 105, but in test case 11, m = 105 + 20.

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

How does hacking a solution affect the scoreboard of the hacker in educational rounds?

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

how to solve D and why :P? because I didn't know what to think

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

    You can use dynamic programming.

    dp[i][j][k] equals to the number of ways to color i columns, the last column has the state j and the total component count is exactly k.

    The state is 0 if both cells are white, 1 for white upper cell and black lower cell, 2 for black upper cell and white lower cell, 3 for both black cells.

    Base case: dp[1][0][1] = dp[1][1][2] = dp[1][2][2] = dp[1][3][1] = 1.

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

      You don't need to consider 4 cases, dp[i][0][j] = dp[i][3][j], and dp[i][1][j] = dp[i][2][j],

      you can just consider if last elements are of same color, or different

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

      I think I did same, but can you please tell what's wrong this submssion 43147897?

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

        Integer overflow.

        Each operation can caused your dp value to reach , which exceeds the upper bound of 32-bit signed integers (i.e. 231 - 1).

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

      thx really good explanation and in few words

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

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

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

    Is validator fixed now?
    How people will be affected if test cases are corrected? (In case it is fixed.)
    Considering that 116 people got AC during the contest, RE(?) and WA(?).
    If no of people <50 then we can probably ask those people do you want an unrated contest for you?
    And it can be kept rated for others?

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

      Validator is fixed and all the tests are also fine. The other questions are still in discussion.

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

        If the effect of the invalid test in F is not significantly high on new rankings, please try not to make the round unrated!

»
3 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

I think there is something wrong with CF-Predictor. halyavin got rank 839 and it predicted that he get +65.

UPD: Actually, he got rank 835.

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

    halyavin rank 839...are we in the real world or tron has taken over

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

    It is rated for div 2 only, so halyavin doesn't effected

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

    I had a meeting at work and had to start half an hour later.

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

    Also think so, CF-prediction for being #329 in Div2 was +123 while I got +15 which is about right.

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

http://codeforces.com/contest/1051/submission/43144963

What's wrong with my C?

It fails on Test 7

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

If the issue with F can be solved, please do not make this round unrated. It'll be very disappointing.

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

    it cannot be. how can you "solve" something like this. constraints say m <= 1e5. test case has m = 1e5 + 20

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

      remove/modify the test and reevaluate

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

        but time wasted is time wasted right. in my case, i got AC after changing the size of array.

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

          So did I.

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

            Lol. all my submissions for F ACed after the test case change. It will be highly unfair keeping this contest rated (for me). My first submission for F was at 00:46. I wasted time till 01:40 on it.

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

              That does make sense.

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

How to solve problem E?

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

    Let dp[i] be the total number of ways to partition the suffix of a starting at i. And let dp[n]=1 (n is the last character index+1). To calculate dp[i], you need to know the smallest index i' (i'>=i) such that the sub-string a[i, i+1, ..., i'] forms a number >= l, and you need to know the largest index i'' (i''>=i) such that the sub-string a[i, i+1, ..., i''] forms a number <= r. dp[i] will be dp[i'+1]+dp[i'+2]+...+dp[i''+1]. To find i' and i'', you need an algorithm which finds for every i the longest prefix starting at i which is also a prefix of l, and the longest prefix starting at i which is also a prefix of r (Z algorithm does this in linear time). And to sum the dp values, you can use cumulative sum on dp as you are calculating it. There is a bunch of corner cases that need to be handled of course.

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

the number of people who solved F isn't high enough to make the round unrated

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

    But some participants wasted time on F...They may got higher ratings if there was no problem

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

      i think it's kind of trade off, anyway my solution on E probably will fail so i am not talking because of me

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

      I think if they got RE verdict on test with high order likes 11th, then they could realize that they should change their constraint.

      And i think it was better to waste time on F instead of E or G.

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

Can you make the round unrated for only people affected?

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

Problem F had the same idea as this problem, but with a slightly tricky implementation.

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

I know it's not fair to make it rated for the participants who wasted time on f but it's also not fair to make it unrated for all the other participants ...

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

If this gets unrated, it will be the first unrated educational round [rated for div2]

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

If this round will be unrated.It will be better for those people who have at least one submission of problem F but not for all please, since the issue created with only problem F. Thanks.

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

In problem F, if the condition m-n<=20 doesnt exist, how to solve it ?

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

    Run floyd warshal or dijkstra for each pair or dijkstra on every query. There is no fast solution without that condition.

    Maybe some A* or some probabilistic stuff — no idea how that works in practice.

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

Sorry for the F, but hope this contest will be rated...

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

How to solve G?

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

    if doesn't exist any i,j(i!=j) such that a_i=a_j or a_i=a_j+1

    then obviously we can't do any operations and they are pairwise different

    so the answer is 0

    and now consider we got a new (x,y)

    lets look at the 2 conditions below:

    (1) lets say that there exists a_i+1=x and b_i<y, we should apply operation(2) to x and apply operation(1) to a_i so that we can add b_i-y(which is a negative value) to our answer

    (2) if there exists a_i=x, then we must apply operation(1) to one of them to make it pairwise different, and obviously, we should apply the operation to the one with smaller b

    after we have done our operations, we should get something like (a_i,b_i1),(a_i+1,b_i2),(a_i+2,b_i3)....

    be aware that these b are sorted so that b_i1>b_i2>b_i3 ...

    To conclusion, let consider we get (a_i,b_i1),(a_i+1,b_i2),(a_i+2,b_i3)...(a_i+m-1,b_im) ,(a_j,b_j1),(a_j+1,b_j2)...(a_j+k-1,b_jk) (a_j>a_i+m-1+1)

    if we get a new (x,y) that a_i<=x<=a_i+m, we should rearrange the them so that we get a new sequence (a_i,b_i1),(a_i+1,b_i2)...(a_i+m,b_i(m+1))

    and if a_i+m+1=a_j

    we should merge the two((a_i,b_i)... and (a_j,b-j)...) into one((a_i,b_i)...)

    we could do this by using a BST and Heuristic merge in O(Nlog(N)log(N))

    sorry for the bad explanation, you can check my code if you need

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

      I had found the same solution during the contest but didn't have enough time to write the bst from scratch, I wish we had a way to use std::set for the same job.

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

http://codeforces.com/profile/answhldkd this account is pretty obviously a team account. look at his submissions. ( http://codeforces.com/submissions/answhldkd ) You can recognize easly that coding style of B, D, F is simillar, but for F, A, C they are very different.

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

Problem F is similar with http://codeforces.com/gym/101808/problem/K which I have done 2 weeks ago. But my biggest mistake is tried to solve D before F. After contest, read F and say: OMFG!

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

    It is not similar, in task you mentioned, there is a solution just using lca, so you need there just to code simple lca (nlog(n), log(n)), here you should code something harder, but of course they have some similar part

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

For us, the game started very late, we stayed up late to the early hours, so I hope this game should rated.

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

Hope the contest will be rated. Few people were affected by issue in F, it could be unrated only for these people

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

    I don't remember the time, when the contest was rated for everybody except some people, because of mistakes in some problems, so in my opinion, contest would be rated for everybody, or unrated

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

Is it rated??

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

Rated!

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

Is the contest made unrated?

»
3 months ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

hope final testing will starting soon.its truly boring waiting a long time for testing.

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

is this contest rated or unrated ? for one test case in problem F round shouldn't be unrated problem F must be deleted or round became unrated for people who have solved problem F

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

    Or maybe codeforces should first make you expert and then think about what would be the best in everyone's interests?

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

Longest discussions ever...

1.politics

2.arms deals

3.educational round 51 rated or not

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

The System Test has started!

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

I open Codeforces about 20 times for the result of the discussing

and check the announcement said "are discussing" or "will discuss"

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

this is truly awkward ,if only for problem (F) this round will become unrated.

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

    It's not about the problem but about the number of people affected and the consequences of that issue.

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

why do these issues occur only when I do well in a contest ?!!!

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

I think there aren't lots of people affected by issue in problem F, because number of people that solved it didn't change much after rejudge, so I think it's better to make unrated only for them(If they want that ofc).

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

Maybe we can make the round unrated for those people affected.

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

Seriously, just only for few people its going to be unrated for all users? Its very unexpected from CF . Very sad. I cant believe it.

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

Upsolved problem A with adding "type" symbols after every char, which let me use backreference in regex. Solution with Perl: 43170240

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

Is it rated or unrated? Not determined yet?

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

    I don't know how it is going. I just hope this round would be rated. :)

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

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

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

If it's unrated, it would be very sad :( I will lost the chance to become CM.

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

So it is rated now? Nice.

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

Thanks a lot CF. Finally its going to be rated. Feeling really happy now. Again Thanks a lot.

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

Rated For Not Affected! That's Really a Nice Decision

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

List of top hackers?

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

In problem A, any particular reason for not allowing T > 1 during hacking phase? Actually these 43147222 , 43149770 solutions will fail on test cases such as : http://codeforces.com/contest/1051/hacks/489717/test

By the way, they are exactly same submissions by different users but in different languages.

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

    Our reasoning was that the other way around the whole list of 100 tricky cases might have been collected in a single file in order to abuse to hacking process.

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

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

Why does Bottom Up take much less time than top down with memoization??
In regards to 1051D - Bicolorings and following submissions:
Top Down: 43169291
Bottom Up: 43175270

Is it due to Hashing?

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

I have a question:

In problem F 1051F - The Shortest Statement ,it says m-n<=20,so it will be at most 21 Edges are not used after building a tree, so if every edge's u and v are different it will have at most 42 points.

I take these points out and run dijkstra to get these points to every points' shortest-path. but I only define a array dis[41][maxn], and I saved id start from 0.

I think it should get RE during system test. Why it got AC? If I use assert in my code, it got RE on test 6. I don't understand why really. (sorry for my poor English. :P)

Here's my code.43141017

use assert.43177498

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

    Program may use some static memory that goes after your array dis. It may be free memory of memory of some other array. There are good chances that such UB will not lead to Runtime Error. You was lucky.

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

      Thanks for your explanation.

      But After array dis it only follows an array len which is used in the query and means points' distance on tree, if it will be changed by dis[41], then why the answer is correct? Maybe I'm too lucky. :P

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

        In your code you have an array len after dis, but in the memory they may be in any order.

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

Where is editorial?

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

why no editorial even after 12 hours?

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