Привет, Codeforces!
В 08.10.2019 17:35 (Московское время) состоится Educational Codeforces Round 74 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Так же от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Привет Codeforces,
Прежде всего благодарим вас за отклик на опрос из анонса прошлого раунда. Более 300 человек поучаствовали, и мы надеемся начать внедрять ваши предложения уже очень скоро.
Так же мы рады сообщить, что время приема заявок на наши полностью финансируемые стипендии для магистерских программ в Бангкоке продлено.
Напоминаем, что они покрывают всю плату за обучение, а также расходы на проживание. Итак, если вы или кто-то из ваших знакомых интересуетесь технологиями, предпринимательством или дизайном и уверены в своих силах, не медлите!
Последнее, но не по значению, мы хотели бы порекомендовать статью, вышедшую на прошлой неделе в нашем блоге: “Топ 5 дополнительных навыков, которые каждый разработчик должен иметь”. Как вам список? Согласны ли вы с ним?
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | HIR180 | 7 | 296 |
| 2 | Hoxilo | 7 | 317 |
| 3 | stasio6 | 7 | 350 |
| 4 | sigma425 | 7 | 400 |
| 5 | jiangly | 7 | 405 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | kimbj0709 | 120:-19 |
| 2 | Retired_NarutoElMatria | 107:-111 |
| 3 | baluteshih | 48:-9 |
| 4 | galen_colin | 40:-3 |
| 5 | Rian_5900 | 34:-13 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| 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: Разбор опубликован
hope that problems be as good as the problems of the last contest was .
Is it rated?
Yes , Educational rounds are always rated.
Hope it won't be rated.
It will definitely be !
No
Why ?
Are you part of that DDOS team? -.-
Yes I think
awoo and vovuh together to prepare a contest that will be awesome ^_^.
It seems they are part of the head-quarters now. XD
Wish no ddos, no long queue, no aliens attack, no world crash.
No hacks
:))
It will be an interesting contest.
How to calculate penalty?
1 penalty = +10 minutes
Hope NO DDOS.
Can you, please, click on the like?
sure I'll downvote
educational rounds are the best thing that can happen to a learner
Site broke for 10 minutes or was it just me?
+1, was 100% it was my local network at first but reddit showed no issues AT ALL loading in the same time.
I am experiencing issues while submission. Is it for everyone or just me?
CF rarely responding. 502 Bad gateway VK. Same with m1 and m2 :(
Queueforces.
Long queue causes distraction this is not ok
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
CF giving issues. Bad gateway.
Even m2.codeforces.com is not working :(
contest should be unrated!
Contest should be unrated .. server is lagging too much
gg go next
:'(
Round should be unrated.
long queue of the judging?
semi rated?
100 pages of queue, nice
Is it rated?
Please make this unrated ..... 100 pages of queues.
This site began to have serious issues... 25 minutes waiting for my submission to be judged? FFS!
DDOS again?
DDOS again?
Who make DDOS again?!
Round should be unrated
More than 100 pages of queue.This round should be unrated.
Again DDOS, again unrated
AnouncementForces lol....Leave DDOS , too much clarification for problems in my opinion.
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?
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.
Please explain D more properly how is ans 6 for 1 st test case
problem writers were extra bad today
BREAKING NEWS
The round is rated
DDOS attack + ambiguous questions + long queue submission = Unrated contest
The contest should be unrated.Increase in contest length does no good
Can the conditions of the tasks be even longer and even more unclear?
The contest should be unrated.Increase in contest length does no good.
It is will be rated? Dudes, are you seriously?!
Bad Day :(
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.
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.
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?
Told them this 8 minutes into the round. They announced it 15 minutes later...
please unrated ，just after chines national day and i need VPN？
I will get a positive rating change but I say round should be unrated. I submitted problem B in minute 21. I received the verdict at 42. I had to change a single
>to>=, so I got accepted at minute 43. I lost 20 minutes in between because of queue and DDOS. Problem B's statement was unclear although it could be figured out from the verb "push" that what the author really meant, the statement was wrong. Long queue and unclear statement for problem B and lots of clarifications influenced lots of contestants I believe.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
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.
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?
10 Announcement. What is this?
something must go wrong in CF contest. it's just must.
Does it test programing or English Reading Comprehension????
Why is this contest Rated? Please UNRATED!!
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
Me logging into codeforces and getting 10 notifications: Is this what it feels to be popular?
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.
I feel you brother :D
Oh. Didn't see it even till the very end. Welp.
I also have idea in O(N^2).
I have an $$$O(n\log{n})$$$ solution independent of the number of letters: 62179184
Red for a reason, impressed.
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).
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.
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!
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'.
Yes, but maybe some people just left after seeing that there were some problems with the site.
You just named at least 3 reasons for it to 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.
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.
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.
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?
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.
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)
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!
Poor English Statement :'(
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
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.
You can always do something like: https://codeforces.net/contest/1238/problems
Better use complete problemset button.
Yeah, that's another option :)
I feel the same!
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 :/
when will we be able to submit?
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.
I read Problem C statement for 1hour 30min xD.
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.
Error on statement B was obvious imo. And sample test answer on F corrected fast. So its all good man.
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.
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.
1
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.
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...”
Can someone explain problem C, I think didn't understand the question ?
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.
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.
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.
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?As same as you, I can't open Codeforces without VPN
I also got it I'm Egyptian
I got the same message, but just refreshing the page made it go away.
I don't understand problem c :(
same :)
How to solve E?
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.
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.
Amazing solution. Had to read your comment for 10 times to finally understand how this was working.
Can someone explain how this logic works?
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.
can you explain it more briefly with some small example, that would be very helpful
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.
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
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)
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
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.
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.
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!
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 :)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.
How to solve C?
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.
Exactly.
Normal people expect to do easy works. Look, there are over 2000 people solved C, so stop moaning about statement please!
Problem C: Why 1 correct answer for this test ?
He can jump like 5->3->1->0 without crystal . There is not written in statement that he can't skip any platform.
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.
But there is written that he can jump from x to x-2.
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
Why can't he jump directly to 3? He won't die, right?
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
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.
Thanks, I guess it is another statement problem.
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.
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!
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 ?
Yeah, we count AB..B, A..AB, AB, BA..A, B..BA, BA
Also, do not double count the strings like AB and BA.
DDOS + BAD problem statement ruined the contest
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.
I like this kind of statement.
"Hooray! Today we've survived another DDOS attack. The round was not perfect, but it was not ruined!"
Is it technocup second elimination round?
No, 'cause in Technocup's site have no information about it.
Just rofl man -_-
Ну что тут можно сказать...
What is the meaning of "good strings" in question D?
I just can't understand what question is trying to say.
string s is good if $$$\forall s_k \in s \exists i, j : i < k < j$$$ and $$$s_i ... s_j$$$ is a palindrome
Прошу прощение,но неужели не очевидно как сильно атака повлияла на раунд? Простейшая математика:Человек(признаюсь,я говорю про себя) сдает задачу на 13 минуте,происходит атака,огромная очередь,в итоге,человек(опять же я)узнает вердикт(WA2) уже примерно на 40 минуте,исправляет решение за 3 минуты и сдает его на плюсик,в итоге данный участник получил решение на 42минуте+10минут штрафа = +52 к штрафу.Теперь предположим что участник узнал вердикт сразу,тогда правильное решение он бы сдал на 16 минуте + 10 = +26 к штрафу,очевидно обогнал бы многих, кто придумал решение на,например, 30 минуте. Однозначно не забываю про тех кто придумал свои решения в период атаки но не мог их отправить по понятным причинам и тоже получил штраф. Возможно я не могу обьективно оценивать ситуацию из-за того что уйду в конкретный минус,но мое мнение-раунд должен быть нерейтинговым.Извините за негатив
меня постигла точно такая же ситуация
Misread D and wasted 1 hour coding QQ
It is not mention in the problem that good strings will also have length greater than 1
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)
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).
I also did it by counting all good ones directly :D
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.
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
What is the hack for B?
A lot of people submitted B with $$$O(n ^ 2)$$$ solution then case is:
$$$1$$$
$$$100000$$$
$$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$ ... $$$100000$$$
What about r?
r is 1
ofcourse 1.
How To Solve B...?
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.
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.
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.
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.
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.
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.
I am wrong, sorry
Upvoted your comment, only because you play Dota!
How to solve problem D? what is logic for the problem?
Count useless subsrings: AB,ABB...BB,AA..AAB,BA,BB..BBA,BAA..AA
we need only count this 6 substring?
If if their numbers is x.answer is (n×(n+1))/2-x
Кому понравился кф тот "Пешка Мирзаянова"
Why DDOS again? Who are these people who attack on educational sites like codeforces??
is it rated?
is it Hooray?
This is the first time I am seeing a "is it rated" getting upvoted.
I think we should discuss about problems, thats more important...
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?
5?
Choosing 5 twice is a solution, fine. But why choosing 7 and 3 isn't possible?
You are allowed to use just one prime integer
I can't understand what is good string in D! Can someone please elaborate
string is good if all it's characters are in palindrome substring of this string
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 :)
Why does greedy work in C?
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 )
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.
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
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
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.
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!!
MikeMirzayanov ban plz
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.
:(
net upvotes of rnd 74
The previous Educational Round had a net upvote of +298.
Rip Pikmike's contribution :(
This round has a net upvote of +10.
awoo can't be stopped!!!!!!!!!! Long live edu rounds!!!!!!!!!!!!!!!!
Codeforces has repelled the attack, uraaaaaaaaaaaaaaaaa!
can someone explain solution of problem A
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.
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.
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$$$.
Second solution is $$$O(m^2 * 2^m)$$$, isn't it? How can we optimize it to $$$O(m * 2^m)$$$.
Okey, $$$O(m^2 * 2^m)$$$ got accepted. But anyway, is there a $$$O(m * 2^m)$$$ solution?
Yes https://codeforces.net/contest/1238/submission/62192103
Yes, you can squash one m factor. See https://codeforces.net/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.
It just should be unrated, I think. Last night was so bad for people like me.
Please make this contest unrated. Many people suffered due to this.
how many?
All those who failed to solve more than 2 :):)
lmao
So finally what's decided? Is the contest rated or not?
Minyoo's comment above best describes the situation
When system testing start ??
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.
Editoral ? wanted to know how F can be solved in single dfs traversal.
So will the contest be rated in final?
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.
Yes, it's rated, and I -62 became expert.
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.
Why system testing is so slow nowadays ?
When is the rating usually recalculated after edu rounds?
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
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?
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 usePrintWriterinstead (but don't forget call itsclose()function, since it can just forget to flush output).Also, I used PrintWriter instead of System.out...!
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.
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.
What about random shuffling before sorting?
That should work if you use a good random number generator.
Thats good to hear!
Nobody forces you to code in Java. You select language on your own and should be aware of such language details.
will it be rated?
Yes
Sastin
Why all python submissions on B got hacked? 62157133 Is this because of slow input? How can I avoid 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.
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.
Well,,, I 've found the way to accelerate the input, just add
import sys;input = sys.stdin.readlinein front of the code...Надеюсь раунд будет нерейтинговым, писать его было практически невозможно, каждые 5-10 минут кф куда-то улетал.
SlowForces
When will they update the ratings?
I wish,I knew that.
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 ?
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.
ohhhh
thanks
Does this happen for all types of rounds?
No, only ICPC style contests, so educational and Div.3 I think too
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.
Could somebody explain how to solve Problem F?Thanks :)
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:
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.
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.:)
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(?).
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 :)
Why is there no tutorial?
How to solve F?
Thanks for fast editorial
Since the tutorial is not released yet, can anyone briefly describe their approach to problem G?
make educational codeforces a weekly event , a request
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
how is it possible in educational round become failed with out any successful hacking attempts ??!!! does it have any extra system test ??
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!