Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By pikmike, history, 5 months ago, translation, ,

Hello Codeforces!

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 Ne0n25 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 9623 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 Astaa 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 L4U 0:04
C OmegaLUL229 0:17
D MarcosK 0:08
E GyojunYoun 0:09
F ksun48 0:29
G NotNight 0:51

UPD: Editorial is out

• +60

 » 5 months ago, # |   0 hope that problems be as good as the problems of the last contest was .
 » 5 months ago, # |   -67 Is it rated?
•  » » 5 months ago, # ^ |   +19 Yes , Educational rounds are always rated.
•  » » » 5 months ago, # ^ |   -93 Hope it won't be rated.
•  » » » » 5 months ago, # ^ |   -8 It will definitely be !
•  » » » » » 5 months ago, # ^ |   -80 No
•  » » » » 5 months ago, # ^ |   +4 Why ?
•  » » » » 5 months ago, # ^ |   +59 Are you part of that DDOS team? -.-
•  » » » » » 5 months ago, # ^ |   -22 I have the same question too.
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   -67 Yes I think
 » 5 months ago, # |   0 PikMike and Vovuh together to prepare a contest that will be awesome ^_^.
•  » » 5 months ago, # ^ |   0 It seems they are part of the head-quarters now. XD
 » 5 months ago, # |   +106 Wish no ddos, no long queue, no aliens attack, no world crash.
•  » » 5 months ago, # ^ |   +9 No hacks
•  » » 5 months ago, # ^ | ← Rev. 2 →   -13 :))
 » 5 months ago, # |   0 Codeforces are inherently good, and every contest is carefully prepared by the host. But there're always someone to attack this website over and over again, destroying fair competition and causing trouble for the contestants. Hope them don't do it again!
•  » » 5 months ago, # ^ |   -6 If they do this, they will waste the chance of the competitor’s (possible) increase rating.
 » 5 months ago, # |   +4 It will be an interesting contest.
 » 5 months ago, # | ← Rev. 2 →   0 How to calculate penalty?
•  » » 5 months ago, # ^ |   +12 1 penalty = +10 minutes
 » 5 months ago, # |   +5 Hope NO DDOS.
 » 5 months ago, # |   -48 Can you, please, click on the like?
•  » » 5 months ago, # ^ | ← Rev. 3 →   -37 sure I'll downvote
 » 5 months ago, # |   +23 Site broke for 10 minutes or was it just me?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 +1, was 100% it was my local network at first but reddit showed no issues AT ALL loading in the same time.
•  » » 5 months ago, # ^ |   0 Gave my Bad gateway in the first minute of the contest and still does
 » 5 months ago, # |   +2 I am experiencing issues while submission. Is it for everyone or just me?
 » 5 months ago, # |   +8 CF rarely responding. 502 Bad gateway VK. Same with m1 and m2 :(
 » 5 months ago, # |   +28 Queueforces.
 » 5 months ago, # |   +11 Long queue causes distraction this is not ok
 » 5 months ago, # |   +3 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
 » 5 months ago, # |   +10 CF giving issues. Bad gateway.
 » 5 months ago, # |   -6 Unexpected error forces
 » 5 months ago, # |   +10 Even m2.codeforces.com is not working :(
 » 5 months ago, # |   +42 contest should be unrated!
 » 5 months ago, # |   +18 gg go next
 » 5 months ago, # |   0 :'(
 » 5 months ago, # |   +10 Round should be unrated.
 » 5 months ago, # |   0 long queue of the judging?semi rated?
 » 5 months ago, # |   +18 100 pages of queue, nice
 » 5 months ago, # |   +7 Is it rated?
•  » » 5 months ago, # ^ | ← Rev. 3 →   -21 [deleted]
 » 5 months ago, # |   +24 Please make this unrated ..... 100 pages of queues.
 » 5 months ago, # | ← Rev. 2 →   +11 This site began to have serious issues... 25 minutes waiting for my submission to be judged? FFS!
 » 5 months ago, # |   0 DDOS again?
 » 5 months ago, # |   0 Who make DDOS again?!
 » 5 months ago, # |   +54 Round should be unrated
 » 5 months ago, # |   0 More than 100 pages of queue.This round should be unrated.
 » 5 months ago, # |   0 Seriously This is happening again!!! Codeforces do something fast or you are going to lose a lot of contestant.
 » 5 months ago, # |   +3 Again DDOS, again unrated
 » 5 months ago, # |   +45 AnouncementForces lol....Leave DDOS , too much clarification for problems in my opinion.
 » 5 months ago, # | ← Rev. 2 →   +148 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?
 » 5 months ago, # |   +41 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.
 » 5 months ago, # |   +11 Please explain D more properly how is ans 6 for 1 st test case
•  » » 5 months ago, # ^ |   0 Given string AABBB has these substrings: substringss[1, 1] = As[1, 2] = AAs[1, 3] = AABs[1, 4] = AABBs[1, 5] = AABBBs[2, 2] = As[2, 3] = ABs[2, 4] = ABBs[2, 5] = ABBBs[3, 3] = Bs[3, 4] = BBs[3, 5] = BBBs[4, 4] = Bs[4, 5] = BBs[5, 5] = BWell, substrings with length 1 are bad from the definition. Let's remove them. new list of substringss[1, 2] = AAs[1, 3] = AABs[1, 4] = AABBs[1, 5] = AABBBs[2, 3] = ABs[2, 4] = ABBs[2, 5] = ABBBs[3, 4] = BBs[3, 5] = BBBs[4, 5] = BBAA is palindromic, so it's good. AAB is bad, because you can't get palindrome with B. AABB, AABBB are good, because AA is palindrome and BB is palindrome.AB, ABB, ABBB are bad.BB, BBB, BB are good. Now we have only 6 substrings: good substringss[1, 2] = AAs[1, 4] = AABBs[1, 5] = AABBBs[3, 4] = BBs[3, 5] = BBBs[4, 5] = BBAnd answer is 6.
 » 5 months ago, # |   +19 problem writers were extra bad today
 » 5 months ago, # |   +57 BREAKING NEWSThe round is rated
 » 5 months ago, # |   +61 DDOS attack + ambiguous questions + long queue submission = Unrated contest
 » 5 months ago, # |   +13 The contest should be unrated.Increase in contest length does no good
 » 5 months ago, # |   +19 Can the conditions of the tasks be even longer and even more unclear?
 » 5 months ago, # |   +3 The contest should be unrated.Increase in contest length does no good.
 » 5 months ago, # |   +28 It is will be rated? Dudes, are you seriously?!
 » 5 months ago, # |   +111 Bad Day :(
•  » » 5 months ago, # ^ |   +6 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
 » 5 months ago, # |   +135 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?
•  » » 5 months ago, # ^ |   0 Told them this 8 minutes into the round. They announced it 15 minutes later...
 » 5 months ago, # |   +32 please unrated ，just after chines national day and i need VPN？
 » 5 months ago, # |   +38 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
 » 5 months ago, # |   +19 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.
 » 5 months ago, # |   +10 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?
 » 5 months ago, # |   +17 10 Announcement. What is this?
•  » » 5 months ago, # ^ |   0 if the problems statements were clear then there was no announcement(except DDOS attack announcement)
 » 5 months ago, # |   +5 something must go wrong in CF contest. it's just must.
 » 5 months ago, # |   +6 Does it test programing or English Reading Comprehension????
 » 5 months ago, # |   +29 Why is this contest Rated? Please UNRATED!!
 » 5 months ago, # |   +30 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
 » 5 months ago, # |   +29 Me logging into codeforces and getting 10 notifications: Is this what it feels to be popular?
 » 5 months ago, # | ← Rev. 2 →   +34 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.
•  » » 5 months ago, # ^ |   +5 I feel you brother :D
•  » » 5 months ago, # ^ |   +5 Oh. Didn't see it even till the very end. Welp.
•  » » 5 months ago, # ^ |   0 I also have idea in O(N^2).
•  » » 5 months ago, # ^ |   +34 I have an $O(n\log{n})$ solution independent of the number of letters: 62179184
•  » » » 4 months ago, # ^ |   0 Red for a reason, impressed.
 » 5 months ago, # |   +13 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).
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   +16 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!
•  » » » » 5 months ago, # ^ |   -28 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'.
•  » » » » 4 months ago, # ^ |   0 shut up noob !
•  » » 5 months ago, # ^ |   +6 Yes, but maybe some people just left after seeing that there were some problems with the site.
•  » » 5 months ago, # ^ |   +21 You just named at least 3 reasons for it to be unrated...
•  » » 5 months ago, # ^ |   +4 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.
•  » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   -19 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.
 » 5 months ago, # |   +5 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?
•  » » 5 months ago, # ^ |   +6 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.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 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)
 » 5 months ago, # |   -19 Poor English Statement :'(
 » 5 months ago, # |   +25 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
 » 5 months ago, # |   +58 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.
•  » » 5 months ago, # ^ |   +23 You can always do something like: https://codeforces.com/contest/1238/problems
•  » » » 5 months ago, # ^ |   0 Thanks for this, didn't know about it.
•  » » 5 months ago, # ^ |   +5 Better use complete problemset button.
•  » » » 5 months ago, # ^ |   0 Yeah, that's another option :)
•  » » 5 months ago, # ^ |   0 I feel the same!
 » 5 months ago, # |   0 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 :/
 » 5 months ago, # |   0 when will we be able to submit?
 » 5 months ago, # |   +30 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.
 » 5 months ago, # |   +29 I read Problem C statement for 1hour 30min xD.
 » 5 months ago, # |   +142 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.
•  » » 5 months ago, # ^ |   +21 Error on statement B was obvious imo. And sample test answer on F corrected fast. So its all good man.
•  » » 5 months ago, # ^ |   +17 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.
•  » » 5 months ago, # ^ |   +9 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   -7 1
•  » » 5 months ago, # ^ |   0 After reading the first two paragraphs they might have gotten the idea that one can simply pass through platforms, since this is a common feature in platformer games. Then they skimmed the leaver part figuring it was just a gimmick to explain the "going down" part. Maybe at that point it was hard to notice that something could be wrong, because including the "passing through" feature would make for a reasonable task.
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 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...”
 » 5 months ago, # |   -9 Can someone explain problem C, I think didn't understand the question ?
•  » » 5 months ago, # ^ |   0 you're not alone !
•  » » 5 months ago, # ^ |   +4 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.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 There are platforms numbered from $1$ to $h$, the number of a platform represents its height from the groundEach platform can have 2 states, it's either hidden (you can't land on it) or visible (you can land on it if the distance between the current platform you're on and the one you want to reach is at most $2$), at each platform there is a lever, if you move the lever at platform $X$, the platform at height $X$ and height $X-1$ change their state (if a platform is hidden it becomes visible and vise-versa).Assume you're currently at platform $X$, there are only 2 scenarios in which you can move from $X$:1- $X$ is visible, $X-1$ is hidden. You move the lever which causes $X$ to disappear and $X-1$ to appear, you move from $X$ to $X-1$.2- $X$, $X-1$, and $X-2$ are all visible, if you move the lever at $X$ then both $X$ and $X-1$ will disappear and you move to $X-2$.You also have the option to change the state of any platform using a crystal. You are initially at platform $h$ and you're given a sorted sequence of the platforms which are currently visible, you're asked to reach the ground at height $0$ (the ground is not a platform) using the minimum number of crystals.
 » 5 months ago, # | ← Rev. 2 →   -14 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.
 » 5 months ago, # |   +20 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.
 » 5 months ago, # |   +26 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?
•  » » 5 months ago, # ^ |   +6 As same as you, I can't open Codeforces without VPN
•  » » 5 months ago, # ^ |   +4 I also got it I'm Egyptian
•  » » 5 months ago, # ^ |   0 I got the same message, but just refreshing the page made it go away.
 » 5 months ago, # |   +5
 » 5 months ago, # |   +4 I don't understand problem c :(
•  » » 5 months ago, # ^ |   +5 same :)
 » 5 months ago, # |   0 How to solve E?
•  » » 5 months ago, # ^ |   +14 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.
•  » » » 5 months ago, # ^ |   +34 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.
•  » » » » 5 months ago, # ^ |   +2 Amazing solution. Had to read your comment for 10 times to finally understand how this was working.
•  » » » » » 5 months ago, # ^ |   0 Can someone explain how this logic works?
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » » » » » 5 months ago, # ^ |   0 can you explain it more briefly with some small example, that would be very helpful
•  » » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +34 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,AleksanderBalobanov and ankusht
•  » » » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 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)
•  » » » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 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 keyboardAfter 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
•  » » » » 5 months ago, # ^ |   0 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.
•  » » » » » 5 months ago, # ^ |   +3 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.
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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!
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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 :)
 » 5 months ago, # |   0 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.
 » 5 months ago, # |   +2 How to solve C?
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   -15 Exactly.
 » 5 months ago, # |   +28 Normal people expect to do easy works. Look, there are over 2000 people solved C, so stop moaning about statement please!
 » 5 months ago, # | ← Rev. 2 →   -12 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.
•  » » 5 months ago, # ^ |   +25 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.
•  » » » 5 months ago, # ^ |   +11 But there is written that he can jump from x to x-2.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 15 35 3 1at first you're at p5 (h = 5)then you hide p5 but p4 move out so h = 4hide 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
•  » » » 5 months ago, # ^ |   0 Why can't he jump directly to 3? He won't die, right?
•  » » » » 5 months ago, # ^ |   +3 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
•  » » » » 5 months ago, # ^ |   0 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.
•  » » » » » 5 months ago, # ^ |   +5 Thanks, I guess it is another statement problem.
•  » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   +73
 » 5 months ago, # | ← Rev. 2 →   +27 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!
 » 5 months ago, # |   +51 Spoiler
 » 5 months ago, # |   +3 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 ?
•  » » 5 months ago, # ^ |   +5 Yeah, we count AB..B, A..AB, AB, BA..A, B..BA, BA
•  » » 5 months ago, # ^ |   +14 Also, do not double count the strings like AB and BA.
 » 5 months ago, # |   +34 DDOS + BAD problem statement ruined the contest
 » 5 months ago, # | ← Rev. 2 →   +11 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.
 » 5 months ago, # | ← Rev. 5 →   -20 Congrats with living today!!!
 » 5 months ago, # |   +8 I like this kind of statement."Hooray! Today we've survived another DDOS attack. The round was not perfect, but it was not ruined!"
 » 5 months ago, # |   +17 Is it technocup second elimination round?
•  » » 5 months ago, # ^ |   0 No, 'cause in Technocup's site have no information about it.
•  » » » 5 months ago, # ^ |   0 Just rofl man -_-
 » 5 months ago, # |   0 I will request to move it unrated. I was disappointed by the reloading and left the contest to do other works.
 » 5 months ago, # |   +10 Misread D and wasted 1 hour coding QQ
•  » » 5 months ago, # ^ |   -21 It is not mention in the problem that good strings will also have length greater than 1
•  » » » 5 months ago, # ^ |   0 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)
 » 5 months ago, # |   +4 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).
•  » » 5 months ago, # ^ |   0 I also did it by counting all good ones directly :D
 » 5 months ago, # |   +3 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.
 » 5 months ago, # | ← Rev. 2 →   +1 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
 » 5 months ago, # |   +6 What is the hack for B?
•  » » 5 months ago, # ^ |   0 A lot of people submitted B with $O(n ^ 2)$ solution then case is:$1$$100000$$1$ $2$ $3$ $4$ ... $100000$
•  » » » 5 months ago, # ^ |   0 What about r?
•  » » » » 5 months ago, # ^ |   0 r is 1
•  » » » » 5 months ago, # ^ |   0 ofcourse 1.
•  » » » 5 months ago, # ^ |   0 How To Solve B...?
 » 5 months ago, # | ← Rev. 2 →   +80 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.
 » 5 months ago, # |   +30 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.
•  » » 5 months ago, # ^ |   +7 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.
•  » » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   +3 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.
•  » » » 5 months ago, # ^ |   +14 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.
•  » » » » 5 months ago, # ^ | ← Rev. 4 →   +3 I am wrong, sorry
•  » » » 5 months ago, # ^ |   +1 Upvoted your comment, only because you play Dota!
 » 5 months ago, # |   0 How can i get rid of A read-only mode ? Please help me.
 » 5 months ago, # |   +5 How to solve problem D? what is logic for the problem?
•  » » 5 months ago, # ^ |   +1 Count useless subsrings: AB,ABB...BB,AA..AAB,BA,BB..BBA,BAA..AA
•  » » » 5 months ago, # ^ |   +1 we need only count this 6 substring?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 If if their numbers is x.answer is (n×(n+1))/2-x
 » 5 months ago, # |   +6 Why DDOS again? Who are these people who attack on educational sites like codeforces??
 » 5 months ago, # |   +31 is it rated?
•  » » 5 months ago, # ^ |   +8 is it Hooray?
•  » » 5 months ago, # ^ |   +10 This is the first time I am seeing a "is it rated" getting upvoted.
 » 5 months ago, # |   +9 I think we should discuss about problems, thats more important...
 » 5 months ago, # |   0 Problem A: test case 2: 42 32In 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?
•  » » 5 months ago, # ^ |   0 5?
•  » » » 5 months ago, # ^ |   0 Choosing 5 twice is a solution, fine. But why choosing 7 and 3 isn't possible?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +1 You are allowed to use just one prime integer
•  » » » » » 5 months ago, # ^ |   0 Got it. Thank you.
 » 5 months ago, # |   +2 I can't understand what is good string in D! Can someone please elaborate
•  » » 5 months ago, # ^ |   0 string is good if all it's characters are in palindrome substring of this string
 » 5 months ago, # |   +2 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 :)
 » 5 months ago, # |   +1 Why does greedy work in C?
•  » » 5 months ago, # ^ |   +2 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 )
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   -13 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
 » 5 months ago, # |   +1 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
•  » » 5 months ago, # ^ |   0 Actually consider the case when there is no block beneath our current standing platform, then what will happen is when we will pull out our lever then a platform just below will open up and this will continue till there was actually a platform earlier. So I think you do not have to decrement h at each step by one rather than you do platform_height[i+1] + 1, where i was our previous location of the platform. Hope this might would help
 » 5 months ago, # |   0 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.
 » 5 months ago, # |   -21 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!!
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 MikeMirzayanov ban plz
 » 5 months ago, # |   0 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.:(
 » 5 months ago, # | ← Rev. 2 →   0 net upvotes of rnd 74The previous Educational Round had a net upvote of +298.Rip Pikmike's contribution :(
•  » » 5 months ago, # ^ |   0 This round has a net upvote of +10.
•  » » » 5 months ago, # ^ |   +27 PikMike can't be stopped!!!!!!!!!! Long live edu rounds!!!!!!!!!!!!!!!!
 » 5 months ago, # |   +9 Codeforces has repelled the attack, uraaaaaaaaaaaaaaaaa!
 » 5 months ago, # |   0 can someone explain solution of problem A
•  » » 5 months ago, # ^ |   +1 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
 » 5 months ago, # |   +33 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$.
•  » » 5 months ago, # ^ |   +8 Second solution is $O(m^2 * 2^m)$, isn't it? How can we optimize it to $O(m * 2^m)$.
•  » » » 5 months ago, # ^ |   +8 Okey, $O(m^2 * 2^m)$ got accepted. But anyway, is there a $O(m * 2^m)$ solution?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0
•  » » » » 5 months ago, # ^ |   +11 Yes, you can squash one m factor. See https://codeforces.com/contest/1238/submission/62162904 Basically osum[k][bm] is the sum of occurrences (k,i), where the i-th bit in bm is set. add[bm] is the sum of all occurrences of (i,j), if the i-th bit is set, and j-th bit is unset.
 » 5 months ago, # |   0 It just should be unrated, I think. Last night was so bad for people like me.
 » 5 months ago, # |   0 what is the slution for codeforces "A read-only mde"?
 » 5 months ago, # |   +3 Please make this contest unrated. Many people suffered due to this.
•  » » 5 months ago, # ^ |   0 how many?
•  » » » 5 months ago, # ^ |   +21 All those who failed to solve more than 2 :):)
•  » » » » 5 months ago, # ^ |   +1 lmao
 » 5 months ago, # |   0 this is how cyber expert challenges software engineer
 » 5 months ago, # |   0 So finally what's decided? Is the contest rated or not?
•  » » 5 months ago, # ^ |   +15
 » 5 months ago, # | ← Rev. 2 →   0 deleted
 » 5 months ago, # |   +19 When system testing start ??
 » 5 months ago, # |   0 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.
 » 5 months ago, # |   0 Editoral ? wanted to know how F can be solved in single dfs traversal.
 » 5 months ago, # |   0 So will the contest be rated in final?
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 Yes, it's rated, and I -62 became expert.
 » 5 months ago, # |   -7 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.
 » 5 months ago, # |   -8 Why system testing is so slow nowadays ?
 » 5 months ago, # |   -7 When is the rating usually recalculated after edu rounds?
 » 5 months ago, # | ← Rev. 4 →   +1 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!! @ pikMike
•  » » 5 months ago, # ^ |   0 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?
•  » » » 5 months ago, # ^ |   +35 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).
•  » » » » 5 months ago, # ^ |   -10 Thank you very much. I didn't suspect it to be the output since I usually run into that Problem at about 10^6 output lines. When will I learn!?
•  » » » » 5 months ago, # ^ |   +1 Also, I used PrintWriter instead of System.out...!
•  » » » 5 months ago, # ^ |   -10 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.
•  » » 5 months ago, # ^ |   +21 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.
•  » » » 5 months ago, # ^ |   0 What about random shuffling before sorting?
•  » » » » 5 months ago, # ^ |   +10 That should work if you use a good random number generator.
•  » » » 5 months ago, # ^ |   0 Thats good to hear!
•  » » 5 months ago, # ^ |   0 Nobody forces you to code in Java. You select language on your own and should be aware of such language details.
 » 5 months ago, # |   0 will it be rated?
•  » » 5 months ago, # ^ |   +10 Yes
•  » » » 5 months ago, # ^ |   +5 Sastin
 » 5 months ago, # |   -14 Why all python submissions on B got hacked? 62157133 Is this because of slow input? How can I avoid it?
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   -10 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.
•  » » » » 5 months ago, # ^ |   0 Well,,, I 've found the way to accelerate the input, just add import sys;input = sys.stdin.readline in front of the code...
 » 5 months ago, # |   +18 SlowForces
 » 5 months ago, # |   +16 When will they update the ratings?
•  » » 5 months ago, # ^ |   0 I wish,I knew that.
 » 5 months ago, # | ← Rev. 2 →   0 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?
•  » » 5 months ago, # ^ |   +6 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.
•  » » » 5 months ago, # ^ |   0 ohhhh thanks
•  » » » 5 months ago, # ^ |   0 Does this happen for all types of rounds?
•  » » » » 5 months ago, # ^ |   0 No, only ICPC style contests, so educational and Div.3 I think too
 » 5 months ago, # | ← Rev. 4 →   -10 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, PikMike, 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.
 » 5 months ago, # |   +8 Could somebody explain how to solve Problem F?Thanks :)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +5 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: ImageWhere 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.:)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 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(?).
 » 5 months ago, # |   -8 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 :)
 » 5 months ago, # |   +9 Why is there no tutorial?
 » 5 months ago, # |   0 Why is this contest rated??! it's unappropriate!
 » 5 months ago, # |   0 How to solve F?
 » 5 months ago, # |   0 Is there any editorial for the round please ?! I got stuck with many problems in the contest thanks in advance
 » 5 months ago, # |   +5 Thanks for fast editorial
 » 5 months ago, # |   0 Since the tutorial is not released yet, can anyone briefly describe their approach to problem G?
 » 5 months ago, # |   0 make educational codeforces a weekly event , a request
 » 5 months ago, # |   +6 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # |   0 how is it possible in educational round become failed with out any successful hacking attempts ??!!! does it have any extra system test ??