Educational Codeforces Round 74 [Rated for Div. 2]
By awoo, history, 5 years ago, translation, In English

Hello Codeforces!

On Oct/08/2019 17:35 (Moscow time) Educational Codeforces Round 74 (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 extended 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 Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

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

Hello Codeforces,

First of all, thank you for the great feedback on our survey from the last Educational Round. Over 300 people participated, and we hope to start implementing some of your suggestions really soon.

We also wanted to let you know that we have extended the deadline for our fully-funded scholarships for Masters programs in Bangkok.

Remember, they cover the entire tuition fee as well as the cost of living expenses, so If you or someone you know are interested in technology, entrepreneurship, or design, and believe you have what it takes, we want to hear from you!

APPLY HERE→

Last, but not least, we would like to recommend an article published in our blog last week about the “Top 5 Soft Skills Every Developer Has to Have”. What do you think, do you agree with this list?

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 HIR180 7 296
2 Hoxilo 7 317
3 stasio6 7 350
4 sigma425 7 400
5 jiangly 7 405

Congratulations to the best hackers:

Rank Competitor Hack Count
1 kimbj0709 120:-19
2 Retired_NarutoElMatria 107:-111
3 baluteshih 48:-9
4 galen_colin 40:-3
5 Rian_5900 34:-13
571 successful hacks and 641 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A algo.code 0:00
B Surge 0:04
C otbitiy_serb 0:17
D MarcosK 0:08
E GyojunYoun 0:09
F ksun48 0:29
G NotNight 0:51

UPD: Editorial is out

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

Comments Comments (270)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope that problems be as good as the problems of the last contest was .

→ Reply
»
5 years ago, # |
  Vote: I like it -67 Vote: I do not like it

Is it rated?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

awoo and vovuh together to prepare a contest that will be awesome ^_^.

→ Reply
»
5 years ago, # |
  Vote: I like it +106 Vote: I do not like it

Wish no ddos, no long queue, no aliens attack, no world crash.

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

It will be an interesting contest.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to calculate penalty?

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

Hope NO DDOS.

→ Reply
»
5 years ago, # |
  Vote: I like it -48 Vote: I do not like it

Can you, please, click on the like?

→ Reply
»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Site broke for 10 minutes or was it just me?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    +1, was 100% it was my local network at first but reddit showed no issues AT ALL loading in the same time.

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I am experiencing issues while submission. Is it for everyone or just me?

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

CF rarely responding. 502 Bad gateway VK. Same with m1 and m2 :(

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Queueforces.

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Long queue causes distraction this is not ok

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Please make this unrated now otherwise there is gonna be a huge rating drop. I have currently submitted just the A problem and can't submit B problem

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

CF giving issues. Bad gateway.

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Even m2.codeforces.com is not working :(

→ Reply
»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

contest should be unrated!

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

gg go next

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

:'(

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Round should be unrated.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

long queue of the judging?

semi rated?

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

100 pages of queue, nice

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Is it rated?

→ Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Please make this unrated ..... 100 pages of queues.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

This site began to have serious issues... 25 minutes waiting for my submission to be judged? FFS!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DDOS again?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Who make DDOS again?!

→ Reply
»
5 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Round should be unrated

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

More than 100 pages of queue.This round should be unrated.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Again DDOS, again unrated

→ Reply
»
5 years ago, # |
  Vote: I like it +45 Vote: I do not like it

AnouncementForces lol....Leave DDOS , too much clarification for problems in my opinion.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +148 Vote: I do not like it

I support problemsetters in nearly all situations, but today it's a shame really. The amount of messages with clarifications is astounding. Were the problems developed 1 day before the contest?

→ Reply
»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Seems like an overall disaster.Many problem statements are faulty and contest is taken without addressing the DDOS issue of the last contest.Disappointed in codeforces.

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Please explain D more properly how is ans 6 for 1 st test case

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

problem writers were extra bad today

→ Reply
»
5 years ago, # |
  Vote: I like it +57 Vote: I do not like it

BREAKING NEWS

The round is rated

→ Reply
»
5 years ago, # |
  Vote: I like it +61 Vote: I do not like it

DDOS attack + ambiguous questions + long queue submission = Unrated contest

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The contest should be unrated.Increase in contest length does no good

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Can the conditions of the tasks be even longer and even more unclear?

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The contest should be unrated.Increase in contest length does no good.

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

It is will be rated? Dudes, are you seriously?!

→ Reply
»
5 years ago, # |
  Vote: I like it +111 Vote: I do not like it

Bad Day :(

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

    I think the problem statement for C was clear. There was a typo in B but it was an obvious one, especially when you check the test cases.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      If you only can understand by test case, it means that there is wrong in statement. Statment should be clear which means that we have to understand without testcase.

      → Reply
»
5 years ago, # |
  Vote: I like it +135 Vote: I do not like it

Fucking problem B wastes me more than half hours. Statement was WRONG but you told us after contest has begun 23min. Making such a fucking mistake and then you say rated.Are you kidding me?

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

    Told them this 8 minutes into the round. They announced it 15 minutes later...

    → Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

please unrated ，just after chines national day and i need VPN？

→ Reply
»
5 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Should be unrated because of: 1- Problem had a wrong statement (I think until 20 minutes after the beginning) 2- Long queue affected me and lots of other contestants 3- Too much clarification 4- DDOS attack

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I think this contest must be unrated i have a little mistake in b I wait ~20 minutes for queue and then i see that my solution get wa then i saw my mistake but 20 minutes = so many people goes to in front of me.

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

The site was woking perfectly before the start of contest.But from around 10 minutes before the contest, I couldn't enter codeforces entire time using my wifi. But when i switched back to my mobile network everything is working. Is anyone else facing this problem?

→ Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

10 Announcement. What is this?

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

something must go wrong in CF contest. it's just must.

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

Does it test programing or English Reading Comprehension????

→ Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Why is this contest Rated? Please UNRATED!!

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

1238B - Kill `Em All — the name literally describes my feelings when I wasn't able to send solutions for 20 mins...

And before DDOS CF said "we have new IP-adresses, won't work in your country without VPN". What a lovely day

→ Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Me logging into codeforces and getting 10 notifications: Is this what it feels to be popular?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

Anyone else thought that the whole English alphabet is possible in D then when they realized that it's called AB-string solved it in 10 min?

Edit: BTW, is it even possible to solve it if there are 26 letters? I think I have O(n^2) solution only.

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I just don't understand the reason as to why people are asking for the contest to be unrated. Yeah, ok, maybe the site was broken for some time, and they did extend the time limit to compensate for that.

The problems could have been made clearer, but none of them were so wrong that they were unsolvable, unless you couldn't apply common sense (except F, where the sample case was wrong).

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

    Totally agree. I kept refreshing when site went down and after 10 minutes it came back up. Also my submission judged in like 10 minutes too. After that it was all good. About the statements, yeah they were not the cleanest but I understood problems correctly. Even though I didn't perform my best, it should be rated.

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

      When the site went down, I had B ready to submit but I didn't open the statement of C, So I had nothing to do while the site was down, whereas some other contestants had something to work on, so this is a problem!

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -28 Vote: I do not like it

        The same happens to me, but still i think this round should be rated, when site wake up, there is enough time for me to solve 'C' or 'D'.

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

    Yes, but maybe some people just left after seeing that there were some problems with the site.

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

    You just named at least 3 reasons for it to be unrated...

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

    Because when the system broken down.Some people think the situation will as same as the day before yesterday,so they give up the contest.

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

    There are close to 1000 peoples who manage to solve 4 or more problem in this round, it doesn't looks that DDOS attack, queue and ambiguous statement too much affect the performance of large no. of participants.
    Also making '2' back to back round unrated, look's too bad for codeforces.

    → Reply
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

This is the most fucking unlucky contest ever for me. I submitted with wrong compiler and it gave me some random number as answer and then I realized I was clearing my whole dp array in every query in Problem F(How stupid I am). When I got TLE, I tried to fix it last second but couldn't ffs.

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

How to solve D? I know there is some optimization because given characters are a and b only, but can't figure our how to use this hint?

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

    Try to count non good strings. Note that a string is not good only when either its length is one else both characters are present in it and one character just appears once either at the beginning or at the end of the string.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    we can see that string is not good only if there is only one symbol A or only one symbol B in the front or in the end (like ABBBB, BBBBA, AAAB, BAAA). so we can count not good substrings and answer is n * (n + 1) // 2 minus (num of not good substr)

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

    the idea is to count bad substrings instead of good ones. and answer is (n+1)*n/2 — bad; good observation about bad strings a string is bad "not good" if it's first or last character unique . things like A...AB or BA...A. this help you count bad strings as follows for each position find all bad strings ending there as difference between current position and previous position of same character. same way you count all bad strings starting at each position. now all bad strings are counted but some counted twice ! which ones all strings "AB" or "BA" as will be counted twice remove them once. other group is strings of size 1 be sure to remove them only once!

    → Reply
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Poor English Statement :'(

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Problem statements were a bit vague ,followed by the 1 hr. DDOS attack recovery .Still they didn't give up on the contest and made the contest attemptable .......I appreciate that part

→ Reply
»
5 years ago, # |
  Vote: I like it +58 Vote: I do not like it

What I learned today? Opening tabs with all problem statements while CF is still alive should become my new contest routine. Otherwise my F5 key will wear out pretty soon.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Didn't had problems understanding the problem statements, and uploading worked fine after some tries. Not to bad.

But was not able to find proper implementation for problems C, D and E :/

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will we be able to submit?

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

The contest should be unrated because probably some people left immediately after they saw that there was a problem with the site. In fact, I also thought about leaving, but in the end I decided to stay idk why and then after the site started working properly I just read the statements of the problems and again thought about leaving but then the announcement about the contest being rated appeared, so I decided to stay though. Anyway, I think that rating is not that much important, but again it should show skills of people, so imo it will be a bit unfair if the contest is rated.

→ Reply
»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

I read Problem C statement for 1hour 30min xD.

→ Reply
»
5 years ago, # |
  Vote: I like it +142 Vote: I do not like it

About the statements.

First of all, I want to apologize for my bug in the statement of B. We noticed it really fast and would have fixed it if the system was working properly, but it is not an excuse for me.

I don't get why people are so angry about the statement of C. Most participants who understood it incorrectly thought that it was possible to jump from one platform to another, and there were a lot of questions about that -- but I don't understand why the participants thought so. There is not a single word "jump" in the whole statement, but people still thought it was possible to jump down; furthermore, the phrase that pulling a lever is the only way to move between platforms was in the statement all along since the beginning of the contest.

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

    Error on statement B was obvious imo. And sample test answer on F corrected fast. So its all good man.

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

    I just felt like statements of B and C were closer to normal rounds, not educational. But also, when I look at the statements I can't really think of any simpler version.

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

    I believe that none of the people who understood incorrectly statement C though of the word jump. I think that most of us were confused by the part "(...) then he can pull a special lever (...)", which gives the idea that pulling the lever is not mandatory. Let's remember that most of people try to read fast the statement and usually ignore everything after they "understood" it. Thus, most of us ignored the part that came after it "(...) Note that this is the only way to move from one platform to another. (...)".

    However, the fast response to the questions was nice.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -7 Vote: I do not like it

    1

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

    the confusion was may be for this line "then he can pull a special lever" , which should have been "then he has to pull a special lever" . Though it was eventually clear to me, but there's should be no surprise if someone gets confused for this.

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

    For me this part is confusing: “ In other words, the platform you are currently standing on will hide in the cliff and the platform one unit below will change it state: it will hide if it was moved out or move out if it was hidden. In the second case, you will safely land on it. Note that this is the only way to move from one platform to another.” I understand from this that I can only move from Platform X to Platform X-1!? You should use “pulling a lever” instead of confusing word “this” in phrase “this is the only way...”

    → Reply
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Can someone explain problem C, I think didn't understand the question ?

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

    As per my understanding you need to reach height 0 from h and you are allowed to perform following operations : a) pull the lever : that changes state of current height's platform and the one below. As the current height's platform's state changes, i.e., it goes hidden you fall, you fall till the height whose platform is out but if the height differnce you fell is more than 2 you die. b) use crystal : this helps change state of a paricular platform at a height you choose.

    Find the minimum no. of 2nd type operations to reach height 0 from height h without dying.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

Unrated round please, because due to long queue and DDOS attack many people got late submission penalty and were unable to think about the problems in their natural style.

→ Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

I don't understand why so many people want this round to be unrated, when everybody could see the statments and during not working judge (for 15 minutes) everybody could't submit, so it's not something special.

→ Reply
»
5 years ago, # |
  Vote: I like it +26 Vote: I do not like it

I got Codeforces moved to new IP addresses. Probably, it can be blocked in some countries (Ukraine?). You can use VPN or other similar methods to deal with it. message when contest started. (Im in Japan) CF Team grasped this situation?

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

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I don't understand problem c :(

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

    Seems like DP+bitmask. But I couldn't come up with dp states. If I let mask be the set of elements we have put in our permutation to far, to put another element would require knowing the position of each element in mask which cannot be known from mask alone. I couldn't go futher.

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

      Yes dp with submasks, and when you consider new element calculate its contribution to the answer. Just add position of this element multiplied by the amount of used symbols to which the new one is adjacent and substract position multiplied by the number of unused adjacent elements.

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

        Amazing solution. Had to read your comment for 10 times to finally understand how this was working.

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

          Can someone explain how this logic works?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it +13 Vote: I do not like it

            You assign positions to characters in the order $$$ 1 \ldots m $$$. So for a character $$$i$$$, the characters adjacent to it which are used will have positions smaller than $$$pos_i$$$, and those unused will have positions greater than $$$pos_i$$$, so when you simplify the absolute values, contribution of $$$pos_i$$$ is positive in first case and negative in the second.

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

              can you explain it more briefly with some small example, that would be very helpful

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                ← Rev. 2   Vote: I like it +34 Vote: I do not like it

                Suppose $$$m = 110001$$$, this means that we have put the first, second and sixth characters on the keyboard.

                $$$f(m = 110001)$$$ is the minimum cost that it will take to put the first, second and sixth character on the keyboard.

                Now, suppose we want to add the fifth character. The mask becomes $$$m = 110011$$$.

                When we are calculating $$$f(m = 110011)$$$ having placed the fifth character last, the fifth character will be at the position 4.

                • Whenever $$$5$$$ is paired with $$$1, 2, 6$$$, we will add +4 to the answer (Because $$$5$$$ is at position $$$4$$$ and comes after $$$1, 2, 6$$$ in the keyboard)
                • Whenever $$$5$$$ is paired with $$$3, 4$$$, we will add $$$-4$$$ to the answer. (Because $$$5$$$ is placed at $$$4$$$ which is before $$$3, 4$$$ in the keyboard).

                The beautiful idea of this solution is that we do not need to know the relative order of the keyboard ! All we need to know is which characters are already processed. If we are adding a new character, we know it's position in the keyboard. And regardless of the position of the other characters, we can calculate it's contribution to the sum easily !

                Thanks a lot straw_boy,ABalobanov and ankusht

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                  ← Rev. 2   Vote: I like it +3 Vote: I do not like it

                  Why does this idea work:

                  I mean why do we add $$$+4$$$ to all the previously placed numbers ($$$1,2,6$$$) and not have to add different numbers $$$+3$$$, $$$+2$$$, $$$+1$$$ respectively?

                  The reason being when $$$1$$$ was placed at some earlier point in time, it had to add $$$-1$$$ and $$$2$$$ had to add $$$-2$$$ and $$$6$$$ had to add $$$-3$$$ and when you adjust for those earlier additions you now instead have to $$$+4$$$ to all (instead of $$$+3$$$, $$$+2$$$, $$$+1$$$ resprectively)

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                  ← Rev. 2   Vote: I like it +3 Vote: I do not like it

                  In the example I provided $$$m = 110001$$$ was already placed.

                  When I am placing the new character $$$5$$$ at position $$$4$$$, then the cost will be increased by $$$(4 - 3) f(5, k(3)) + (4 - 2)f(5, k(2)) + (4 - 1) f(5, k(1))$$$

                  Where $$$f(4, k(i))$$$ denotes the frequency of the pair $$$(5, k(i))$$$ in the password where $$$k(i)$$$ is the $$$i$$$ th key in the keyboard

                  After this, there will be two more characters, who's cost will be $$$(5 - 4)f(5, f(k(5))) + (6 - 4)f(5, f(k(6)))$$$

                  So, when we are inserting one character, we just add it's contribution to the sum independently of the positions of the other characters.

                  So, when we added $$$1, 2$$$ at earlier points in time, we already accounted for their $$$-$$$ contributions and when we will add $$$3$$$ at some later point in time, we have already accounted for $$$4$$$'s positive contribution

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

        Thanks for the solution! ^^

        I had to really squeeze it in order to get it to pass, and I believe 800 ms is not the intended time.

        Can you propose any optimizations? or some other way to code it?

        I know coding an iterative dp will be faster, but I still think this is too much.

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

          We can achieve $$$O(2^N * N)$$$ by precalculating function $$$g(mask, i)$$$ — the number of symbols in mask adjacent with symbol i. To calculate each state of it in $$$O(1)$$$ just consider any bit $$$j$$$ in mask suppose the lowest and then do the following $$$g(mask, i) = g(mask$$$ $$$xor$$$ $$$2^j, i) + c(i, j)$$$ where $$$c(i,j)$$$ is the number of times symbols $$$i$$$ and $$$j$$$ are adjacent.

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Thankss!

            I spent a lot of time trying to preprocess something that can get me $$$O(2^N * N)$$$ but I always loop for that $$$j$$$ you mentionned.

            Very nice and simple trick to just choose one single bit and use the previous states!

            → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I didn't squeeze my solution and it passed though without any optimisations!

          Maybe the check on line 25 if (!((msk >> i) & 1)) is all what is needed, not sure :)

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the contest should be rated i know many were troubled by long queue even me but it was just for 20-30 minutes and the contest was extended by that much and the problem setters works really hard to make these questions.

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve C?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest should be unrated!!!!!! Because when the system broken down.Some people think the situation will as same as the day before yesterday,so they give up the contest.

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Normal people expect to do easy works. Look, there are over 2000 people solved C, so stop moaning about statement please!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

Problem C: Why 1 correct answer for this test ?

1
5 3
5 3 1

He can jump like 5->3->1->0 without crystal . There is not written in statement that he can't skip any platform.

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

    The statement also doesn't say that he can't teleport directly to 0 without using any platforms, but we don't entertain that possibility because the statement would tell you if that was possible.

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

      But there is written that he can jump from x to x-2.

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    1

    5 3

    5 3 1

    at first you're at p5 (h = 5)

    then you hide p5 but p4 move out so h = 4

    hide p4 but p3 is also being hidden because p3 is moved out currently in this case you will fall to 1 which is Death (4-1 > 2)

    so you have to use magic to moved out p2, h = 2 now (after falling from 4, still alive because 4-2 <= 2)

    when h <= 2 you can just jump to 0

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

      Why can't he jump directly to 3? He won't die, right?

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

        he can't jump to 3 because when he hides p5, p4 will show and block him to reach p3.

        it's said that when you try to switch pi, pi+1 will also be switched depend on whether it's hidden or showed.

        the only way he can jump from p5 to p3 if p4 is moved out. so when he hide p5, p4 will also be hidden

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

        There's no concept of jump. Its just fall , once you pull the lever you fall from current height to the just lower height which has a platform , but if you fall more than a height of 2 you die.

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

    first he at 5 when move 4 opens so he doesn't go to 3 now he at 4 when move 3 closes and he couldn't go from 4 -> 1 must open 3 or 2 with crystal. the trick is that if he fall 2 is ok means he can't fall more but if next one is open he couldn't fall more! 5 can't go to 3 as 4 is open in between.

    → Reply
»
5 years ago, # |
  Vote: I like it +73 Vote: I do not like it

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it

Terrible statements in C and wrong statements in B, D and F. 10 Announcements to explain and correct the questions. 30 Mins of DDOS attack and 100 pages of Queue.

If this does not call for an unrated round, i dont know what is!

→ Reply
»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it
Spoiler
→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem D, you have to count the number of ABBBB..., BA.... strings (bad string) right and then subtract from the answer right, am i missing something ?

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

    Yeah, we count AB..B, A..AB, AB, BA..A, B..BA, BA

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

    Also, do not double count the strings like AB and BA.

    → Reply
»
5 years ago, # |
  Vote: I like it +34 Vote: I do not like it

DDOS + BAD problem statement ruined the contest

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Since the cf-predictor says that I will get -1 as the result of this contest, I think that I'm objective enough to talk about this accident.

And in my opinion, this round should be UNRATED, because you can't evaluate how such accident impact participants' emotions and attitude toward this contest. For instance, this contest start at 22:35 in China, so some people may go to bed when they see "DDOS" at nearly 22:45. And it's clearly that most of them just pass problem A eventually.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I like this kind of statement.

"Hooray! Today we've survived another DDOS attack. The round was not perfect, but it was not ruined!"

→ Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Is it technocup second elimination round?

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Misread D and wasted 1 hour coding QQ

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    It is not mention in the problem that good strings will also have length greater than 1

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

      It has to be a length of more than 2,other wise you can not find a suitable palindrome for each letters. Because the minimum length of a palindrome is 2(according to statement)

      → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

My 2 cents considering problem D:

Most people solved this by counting bad substrings and subtracting their amount from all total substrings. But, you can also just count all good substrings. Notice that all characters in a string, except for the first and the last, have to be part of a palindromic substring. Why? Well, consider a letter which is not the last or first with two neighbors (we will consider A because B can be proven in a similar way) ?A?. For it to not be in a palindromic substring of length two, it's neighbors both must be B — ABA, but this results in there being a palindromic substring of length 3, which proves our thesis. So we only need to consider the first and last character. In the case that the first and last character are the same, the substring is OK (you can prove this in a similar way as we proved that all letters in the middle are part of some palindromic substring). But what if the first and last characters are different? Well, that means that we need to have at least two A's and at least 2 B's in the string for it to be correct, because since they are not the center of any palindrome of length >=2, we will need a character which is the same at some other point in the string.

We can count the number of substrings with the same letters on both ends by just pairing all A's and all B's, and we can count the number of substrings which have different letters on the ends with a simple sliding window and suffix sums of A's and B's, so the total time complexity will be O(n).

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I was stucked with BAD GATEWAY problem in the middle of the contest. The authorities really managed it well to keep the round rated inspite of the DDOS attack.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I like codeforces contests, but last 2 week we used to handle a lot of technical problems during contests, but not solving tasks. Please dont test your defence againts DdOS during contests. If you are not sure that contest will be held in normal conditions — dont start it. People are getting a lot of rating changes for nothing

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

What is the hack for B?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +80 Vote: I do not like it

I think it is a battle of ego now, if they make it unrated, the attackers win again, despite if cf's efforts to handle it.

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I think that a lot of people are requesting to make the round unrated because they left the contest. However, a participant must take responsibility of its own actions: I just can't leave a contest expecting it to become unrated because of people leaving it, that's not how the things work. The correct situation would be "The contest is declared unrated, then I can leave", not the opposite.

Anyways we are all hoping that these kind of technical issues with DDoS end soon to have well developed contests.

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

    No, in fact I didn't leave the contest and my expected delta is +70. The point is that I still think that it is better to make the round unrated because a lot of people probably left because immediately after you see that there are some technical problems you start thinking about leaving I mean you just lose motivation for doing a contest because there is a high chance of a contest ending up in a big queue and I mean just being a complete shit. So, the whole point is that probably a lot of people have left and I completely agree with you that it has been their responsibility, but again imo somebody's rating should show their real skill, so it does not make sense to make this contest rated.

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

      I agree with what you say, but by my experience (which made me not to leave the contest), there have been previous rounds with similar situations and the fact of people leaving the contest didn't matter in the end and they still were rated.

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

    I didn't leave the round. I got a PDF and solved all the problems that I could solve offline (after the acceptance of A).

    It's the round that left me. I can't consider it fair for me if the round is rated.

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

      In your case you might request to make the round unrated just for you (I guess you'll need to give a lot of evidence of your situation), since it would be way unfair for the others to make it unrated just because your network broke down.

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

      Upvoted your comment, only because you play Dota!

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

How to solve problem D? what is logic for the problem?

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

Why DDOS again? Who are these people who attack on educational sites like codeforces??

→ Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

is it rated?

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think we should discuss about problems, thats more important...

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A: test case 2: 42 32

In the note it said that: you cannot choose p=7, subtract it, then choose p=3 and subtract it again.

Can anyone explain why it's not possible?

→ Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I can't understand what is good string in D! Can someone please elaborate

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

    string is good if all it's characters are in palindrome substring of this string

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone tell me what actually asked of problem C. I am trying to understand the problem statement for a long time but still didnt understood. Thanks :)

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why does greedy work in C?

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

    Because you have only one way to move by using lever, "which switches the state of two platforms" so you don't have any options for minimizing or maximizing. ( when you can't move you have to increase your answer by one with no other options )

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think the problem statement for C was too confusing. It was easily comprehendable with the common sense and the sample cases. This, in any way, should not be the reason to make it unrated imo. The DDos attack also didn't affect much as the site wasn't down for long. Still the extra 20 minutes make up for that.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    I have a little mistake in problem B i wait 20 minute queue so if the verdict of my solution come quickly i will repair the mistake in 2 minute but thx for queue so i see my codes get wa after 20 minutes.

    I always say that codeforces is the best site for coding but last 2 contest is really bad please check your problems before contest(like statements) and upgrade the system.

    Or change the site's name. pls do it www.queueforces.com

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I came up with a idea to solve Div 2C by using a map, but it gave me a MLE on TC 6, can someone please help me code

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I submitted B at 41 mins. My friend submitted at 16 mins. But unfortunately he kept C as his language whereas he coded in c++. He noticed that and corrected it but thanks to the ddos, it was 47 mins gone already. So I was actually ahead of him the whole time. That's the POWER of queueforces.

→ Reply
»
5 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Most of the time I can solve at least A. Today I couldn't. And then there were some clarifications too.. This round should be highly rated so that i can be newbie again!!! And please down vote my comment.. It will be a complete package!!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

After realizing that I couldn't connect any site of Codeforces (m1 or m2 inclusive), I received the problemset in PDF from a kind friend. Then there was a short break that I was enabled to submit code through m2. However, after A had been accepted, my network broke down again and I couldn't load any page until the contest was over. I solved ABCE on my own computer and had no idea about my rating. Could this round be unrated? I'll appreciate it if so.

:(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

net upvotes of rnd 74

The previous Educational Round had a net upvote of +298.

Rip Pikmike's contribution :(

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Codeforces has repelled the attack, uraaaaaaaaaaaaaaaaa!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain solution of problem A

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

    If x minus y is greater than 1, the use of prime factorization can ensure that the result of x minus y must be able to separate a prime number p (x-y = np, n >= 1), which is equivalent to x minus n*p to get y. But 1 is not a prime number that x — 1*1 = y isn't accepted.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The question is if (x-y) is dividable by a prime number. If (x-y) is a prime number, then it is, obviously. If (x-y) is not a prime number, then it is, too. Because the defintion of a "not prime number" is to be dividable.

    So, the only number not dividable by a prime number is 1, since the smallest prime number (the problem states that) is 2.

    → Reply
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

In $$$E$$$, many (including me) thought about building the permutation letter by letter and using $$$DP$$$ to optimize the complexity from $$$m!$$$ to $$$2^m$$$, but got stuck in determining the contribution of each newly added letter in the total cost, as this would apparently require knowing the positions of the previously added letters. If anyone still doesn't know how this problem is overcome, this may help:

These are $$$2$$$ ways to calculate the cost (summarized from some people's solutions and ideas):

Let $$$cnt[i][j]$$$ be the number of times letters $$$i$$$ and $$$j$$$ appeared next to each other.

1) Whenever you add a new letter, loop on every not added letter $$$uc$$$, and add $$$cnt[uc][ac]$$$ for all added letters $$$ac$$$. This is due to the fact that cost can be decomposed into units, which are added dynamically at each position.

2) For any $$$2$$$ letters $$$i$$$ and $$$j$$$, where $$$pos_j>pos_i$$$ in the permutation, the contribution of $$$(i,j)$$$ in the total cost is $$$cnt[i][j]*(pos_j-pos_i)$$$. Therefore every newly added letter $$$nc$$$ contributes in the total cost by $$$cnt[nc][ac]*pos_{nc}$$$ for all already added letters $$$ac$$$, and $$$-cnt[nc][nyc]*pos_{nc}$$$ for all not yet added letters $$$nyc$$$.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It just should be unrated, I think. Last night was so bad for people like me.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Please make this contest unrated. Many people suffered due to this.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So finally what's decided? Is the contest rated or not?

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

When system testing start ??

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was good for me that I didn't see the announcements before submitting C.

I started the contest may be after 20 minutes. Codeforces wasn't loading then for me. I tried m2.codeforces.com and it worked. I straightly went to probelm C. After 1 hour 17 mintues I submitted C. Before being accepted I tried opening original codeforces.com and it also worked. Till then I hadn't seen the announcements. I became afraid but my submission got accepted. A and B also got accepted. No wrong answer. If I would have seen the announcements earlier it could be a disaster for me.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editoral ? wanted to know how F can be solved in single dfs traversal.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So will the contest be rated in final?

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

    I got really affected by the attack. It is cool that codeforces managed to control it but anyway i submitted B and only after 30 minutes got the WA veridict. Also it got submitted 2 times in a row. I left the contest and then returned after some minutes randomly and it was already repaired. Maybe you can make it unrated for those who will decrease in rating, anyway i think that next rounds everything will go a lot more smoothly.

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

    Yes, it's rated, and I -62 became expert.

    → Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Question: How to get upvotes for a blog that is being downvoted by almost everyone?
Answer: Ask Mike Mirzayanov to write a blog post requesting everyone not to downvote the blog.

P.S.: It's just for fun. Nothing serious. I (and many) appreciate the efforts put into by the Codeforces team to tackle the DDOS attack.

→ Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why system testing is so slow nowadays ?

→ Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

When is the rating usually recalculated after edu rounds?

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

Used "Arrays.parallelSort" instead of "Arrays.Sort" in problem B to get rid of "UWI"-hack, but it gave TLE on case-19. Too much pain for JAVA users!! @ awoo

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

    I used Collections.sort(). It sorts in O(n log n) time in worst case. But I still got TLE on case 9. What were you supposed to do? Counting sort?

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

      The problem in your solution is not a slow sort, but slow output. System.out.println() always flushes the data, that's why it has problems with printing $$$10^5$$$ integers one per line. In that cases you can use PrintWriter instead (but don't forget call its close() function, since it can just forget to flush output).

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Taking Integer[] array instead of int[] array also works for Arrays.sort(). Most of the time Arrays.sort(int[]) gets time limit exceeded. Arrays.sort(Integer[]) works normally.

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

    I don't use Java but here you go what I understood from the last 1203912039 times that it happened:

    Arrays.Sort can be O(N^2) for primitive types but it is O(NlogN) always for non-primitive types. So you can just wrap what you want in a class or something and it can't be hacked.

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

    Nobody forces you to code in Java. You select language on your own and should be aware of such language details.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will it be rated?

→ Reply
»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Why all python submissions on B got hacked? 62157133 Is this because of slow input? How can I avoid it?

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

    I'm afraid so. Actually I remove the set() method and implement a unique function by myself (linear complexity, I thought it may faster than using set() method). And I submitted in PyPy3, it should faster than py3. And I got a TLE in test 7. 62193391 . Perhaps you should use C++ instead.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      If you look at the test case you can see its input is like this: 100000 1 1 1 1 1 1 ...

      so i think reading 100k lines makes some big overhead.

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

        Well,,, I 've found the way to accelerate the input, just add import sys;input = sys.stdin.readline in front of the code...

        → Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

SlowForces

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

When will they update the ratings?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have a question.
I submitted two codes to A and B.
I hacked the second one is each task and I still have AC.

So the first AC is the final one? Or the best one?

MikeMirzayanov awoo ?

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

    I once asked a clarification about this, the first solution that gets AC is counted. And if you resubmit and your first solution later fails, but second gets AC, you get AC.

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

      ohhhh
      thanks

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

      Does this happen for all types of rounds?

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

        No, only ICPC style contests, so educational and Div.3 I think too

        → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it -10 Vote: I do not like it

Hi — My code has been plagiarized by user my_name_is_khan. This user is malicious and has a history of ripping off other people's code as you can see from their submission history here. I request MikeMirzayanov, awoo, and vovuh to please restore my solutions and rate me for this contest. Also, I request you to take steps to ban such hostile users. Thank you.

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Could somebody explain how to solve Problem F?Thanks :)

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    It is easy to notice that your graph will always look like a single chain, and any vertex of this chain can have some "leaves". So your answer will be always a graph like this:

    Image

    Where vertexes from 0 to 7 I call body vertexes and others are leaves.

    In order to find this tree you have to launch a dfs from one of body vertexes and $$$ans(x) = max1(ans(son_1), ans(son_2), ...) + max2(ans(son_1), ans(son_2), ...) + sons.count$$$, where max1 — first maximal among sons, max2 — second.

    But we cannot launch dfs from each vertex and select the best answer, so you can think a bit how can you calculate it using two only (or 1) dfs.

    I hope the main idea is clear.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for your clear solution!

      But I want to figure out a fact that for a valid tree.Except the root can have two sons which are not leaves, other nodes in the tree can only have at most one son which is not a leave. So you should calculate another value for every node that if the node is not a root then what's the maxsize tree of it to get the correct answer. The formula in your post is almost correct except that the meaning of the "ans" on the left is different from the meaning on the right. You can use just $$$1$$$ dfs to solve it.:)

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Let's fix the root of the optimal sub-graph. Let's define two types of segment for each node — a point segment(where only this node is used in optimal sub-graph) and a batch segment(where this node along with its its subtree childs are used). Assume fixed root has batch segment, then we can use atmost two types of batch segments which intersects with segment of root and infinite point segments. For all non-root nodes we can use atmost one batch segment and infinitely many points one. This may be not clear to understand because of my explaination but maybe this picture can give you an idea — (https://imgur.com/HPwMhoi) This is simple DP. Details in my code. But root can be any node not just the one we selected initially. Assume child of above fixed node is new root then either previous node will add as point segment — we can add 1 to dp[new_root][0] otherwise it act as a batch segment then we can just swap two batch segments of new_root and prev_root and hence this value will be equal or maybe there exist a rerooting parameters(?).

    → Reply
»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

After ac problem A I can't submit my solution for B. Then I closed codeforces when I saw "ddos attack". finally,my rating got -157. rediculous :)

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Why is there no tutorial?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

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

Thanks for fast editorial

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the tutorial is not released yet, can anyone briefly describe their approach to problem G?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

make educational codeforces a weekly event , a request

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

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how is it possible in educational round become failed with out any successful hacking attempts ??!!! does it have any extra system test ??

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone please shoot me in the head? I don't deserve to code because I'm an idiot. I just VCed in this contest. Solved ABD. Look at my submissions for problem D.

79009148: Okay, naive $$$O(N^2)$$$, was bound to TLE.

79009410: Okay, better than previous one but still TLE.

79009661 and 79009765 and 79009935:

You can read in the commented part how I thought of optimising. (I've started to adapt to the habit of writing down my ideas as short comments so as to have them gathered to look at while solving problems). Well, there was nothing wrong with my solution algorithmically. Yet, I got WA. I tried finding all possible errors with my algorithm, maybe I'm doing something wrong with indices, maybe something else. It turns out I was taking $$$N$$$ as an integer and overflowing it. It took me an hour to figure this out. I feel terrible and am really mad at myself.

Great problems though!

→ Reply