Привет, Codeforces!
В 17.08.2023 17:35 (Московское время) состоится Educational Codeforces Round 153 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Harbour.Space University в партнерстве с Giga (Unicef) предлагают стипендию для получения степени магистра в сфере Computer Science and Front-end Development, а так же опыт работы.
Мы ищем различных кандидатов от junior до mid уровня:
Front-end разработчик:
Студенту на этой позиции придется тесно сотрудничать с разработчиком блокчейна и главным менеджером по продукту чтобы способствовать разработке и реализации пользовательских интерфейсов для прототипов компании на основе блокчейна. Они будут отвечать за перевод каркасных фреймов UI/UX в функциональные и визуально привлекательные веб-приложения, обеспечивая беспрепятственный пользовательский опыт. Студент будет сотрудничать с блокчейн и бэкенд разработчиками и дизайнерами для оптимизации производительности приложения. Они также будут участвовать в тестировании, отладке и поддержании базы исходных кодов. У стажера будет возможность получить практический опыт разработки интерфейса в контексте технологии блокчейна и внести свой вклад в миссию Giga по подключению школ к Интернету.
- Уверенное понимание HTML, CSS и JavaScript
- Знакомство с фронтэнд фреймворками и инструментами, такими как React или Vue.js.
- Навык решения задач, внимание к деталям и страсть к созданию интуитивно понятных пользовательских интерфейсов имеют важное значение
Full Stack разработчик:
- Интерес и опыт в разработке веб-приложений, информационных продуктов и OpenAPI
- Умение работать с облачными службами развертывания (предпочтительно Azure), конвейером Git и CI/CD, а также процессами развертывания.
- Приветствуется опыт работы с проектами с открытым исходным кодом
- Уверенное знание ML
- Опыт работы с инструментами визуализации данных, такими как matplotlib, ggplot, d3.js, Tableau
- Отличные коммуникативные навыки — невероятно важно описывать результаты для технической и нетехнической аудитории
- Большой опыт разработки программного обеспечения
- Практический опыт работы с инструментами обработки данных
- Способность решать задачи
- Аналитический склад ума и отличное деловое чутье
- Степень в области компьютерных наук, инженерии или смежной области приветствуется
Все успешные кандидаты будут иметь право на получение стипендии со стопроцентной оплатой обучения (29 900 евро в год), предоставляемой нашими партнерами.
ОБЯЗАТЕЛЬСТВА КАНДИДАТА
Обучение: 3 часа в день
За год обучения вы завершите 15 модулей (длительность каждого 3 недели). Ежедневная учебная нагрузка составляет 3 часа, плюс домашнее задание, которое нужно выполнить в свободное время.
Работа: 4 часа в день
Погрузитесь в профессиональный мир во время обучения. Вы будете учиться у лучших и с первого дня сможете применять свои новые знания на практике.
ТРЕБОВАНИЯ
- Опыт работы в отрасли
- Международная экспозиция
- Стремление к обучению
- Устойчивое развитие ключевой момент для вас
- Желание работать на общественную организацию
UPD: Разбор опубликован
Hope the round will be interesting
actually it was boring
..
why were your solutions skipped in codeTon round 5?
..
haha
Go and say it infront of the mirror and see the magic
It will be very good, if educational rounds also have scoring distribution of problems!
Every problem has equal points. Rankings are determined by penalties. You can read this comment.
I don't think the community want contests like the last one, we wouldn't want the B to be harder than C 💀
True
6 ke 6 marunga
Wow, hope a good round!
awoo uwu ><
Hope to reach pupil this round! Just 7 more points to go :O
Nevermind :(
dw, next time you'll
Thanks :)
Just keep trying, and never lose hope. You should not stop believing that pupil is actually possible (which was my case when I had frequent rating drops). All the best!
How did it go? I am also targeting for pupil but wasn't able to solve B. LOL
I also couldn't, it's just terrible imo
It’s so strange that the explanation for problem B is not very referential, and even you can’t solve it
I mean, I couldn't solve it because of one case, I did write everything else, but still now I understand that Div 2B is harder than C sometimes
CF-Predictor says you will get positive delta (+14), maybe you will reach Pupil.
Maybe. Crossing my fingers right now, waiting for ratings to update
Noooo! 1199. SO CLOSE yet so far!
You will definitely reach your goal next time
Thank you so much!
Update: you were right! I reached pupil. Thanks for your support everyone!
Good luck, everyone! I hope there'll be good and pleasant problems at this contest
I LOVE EDU ROUNDS :3
PS: Earned +87 delta woooo!
It is easy to increase rating in Educational Round so all the best guys.
is it really so? but why
Hope to get 3 points to complete 1000 rating
I will drunk drive if I don't get positive rating in this round
You can't drink and drive even if you get a negative rating, it's extremely dangerous.
Everyone cares about ur life, please don't joke with ur own precious things. Drunk drive is very dangerous, right?
The quality of EDU competitions has always been good.
Good luck,everyone!
Imagine the C problem is another permutation problem:)
Guess What?! it is
lol
I love educational round :3
Hope to reach Pupil.
Wow you got it (same as me T_T)
:)))
You got it by dropping down not going up lol
holp to reach specailist
6 ke 6 karunga
Hope it will be an interesting round!
Problems were nice, thank you!
This round is so weird. Also A>>B and A>>C.
It just not. Just switch from $$$()()$$$... and $$$(($$$...$$$))$$$ solutions. Has "NO" answer only with $$$()$$$ input.
I will try to give constructive criticism this time.
Please, find testers or at least proof readers for your problem statements.
B is very hard to understand. What does an infinite number of stones mean? What is a1/ak
C is very weird. Alice makes the first move, but the first move isn't part of the game? How does that make sense?
Too hard A also, i think a lot of people just resigned after trying A
i almost gave up CP in general after not being able to solve A then i somehow figure it out, but i felt like A,B were harder than C.
Nah, honestly A was the hardest of them all (ABC). Unless you knew the trick.
B felt more like a forced question.
Most CP problems these days are forced. If you think about them, they are very unrealistic.
Concubine approval
Cool C,D,E but terrible A,B imo.
+1, but A was kinda funny
Agree about B. I couldn't solve it and just left being sad, tried D but didn't like it after 5 minuter
The Pain is real T_T
how to solve C?
It is easy to notice that the chip will be moving along the LIS ending at the i-th element. If the length of the LIS ending at the i-th element is 2, the i-th element is lucky, otherwise Bob can always make himself win. 219331114
My solution is pretty much the same as dIsPoSEdOfFAcCC514's, but i managed to simplify the implementation a bit more IMO, turns out we just need to keep track of the minimums, that is the minimum of the whole array, and the minimum of the winning positions values. The next winning position's value will need to be between the minimum of the whole array and the minimum of the winning positions values. Also, CMIIW 219313622
surely there has to be an easier way to solve it? i could notice that if all the numbers lesser than arr[i] preceding it in the arraay were in descending order, it means that the number is lucky. sadly could not code.
Let’s define cnt(pi) as count of elements lesser than pi that comes before it when going from left to right.
Alice can choose an index i if all pj<pi for j<i cnt (pj)=0.
Let $$$d_i = -1$$$ for all $$$i$$$. Now denote $$$d_i = 1$$$, if $$$i-th$$$ element is good, otherwise $$$d_i = 0$$$.
We go from $$$0$$$ to $$$n - 1$$$. It's obvious, that if we now have $$$d_i = -1$$$, then it's gonna be $$$1$$$ if we have no $$$a_j$$$, such that $$$j < i$$$ and $$$a_j < a_i$$$ and $$$d_j = 1$$$, otherwise $$$0$$$. So we just keep $$$2$$$ minimum elements. One with $$$d_i = 0$$$ and one with $$$d_i = 1$$$ and compare $$$a_i$$$ with each of them. After this update minimums.
Answer is $$$sum(d)$$$.
I solved that in O(n) Time complexity (One scan to be exact) and O(1) Space Complexity (No need to make an array).
So we declare two int variables as minLucky (the minimum lucky element until the ith element) and Min (the minimum element till ith element) and initialize them both as INT_MAX. Also, initialize a variable lucky = 0 (this stores the number of lucky elements).
We run n iterations and in each one, input a number (say x) of the permutation and do the following: (1) if x is greater than minLucky, ignore and continue; (2) if x is smaller than Min, update Min = x; continue; (3) if x is greater than Min and smaller than minLucky, then x surely is a lucky element, so increment lucky and minLucky = x (of course x was less than minLucky to reach condition (3))
Finally output lucky and there we go. You can find my code here.
Note: I came up with this solution on my own, although after the contest ended. Also have NOT been able to mathematically prove the working yet. I just took many different test cases and made observations to reach this approach.
PS: This is my first comment/post on this site. English is not my first language
Can somebody come up with a proof for this???
T_T
I think making problems hard to understand is becoming a trend or something like that
Imagine English being your official language but you find it difficult to even understand the problems T_T...
it depend on the author's first language.
After being specialist for so many contests, I solved 0 and dropped to pupil, go next contest I guess
Was hoping to reach expert for first time in my life.
2 hours' time may be too tight to view all of the problems.
A was really hard. I feel that among A,B,C, C was the easiest of the three.
Me trying to solve A, After 2 hours I felt like it is Div-1 Contest.
For D, I wonder what the upperbound for the minimum number of swaps needed is. It seems to be very low. I thought it was 2 or 3, but it seems I am wrong.
Consider the case 111111111.....000000000.....
Same here. I thought it would be 2 at most.
Ah, I see now. Guess the constraints fooled me into thinking it was some kind of brute force.
It does seem to be fairly low for this problem, but I think you can prove it's at least N/8 in the general case.
Rationale: you can start with a string of (N/2) 0s followed by (N/2) 1s which creates an imbalance of (N/2)^2 and any swap can reduce the imbalance by at most 2N, and (N/2)^2/(2N) = N^2/8N = N/8.
You can change any string s to any string t with at most n/2 swaps, so n/2
how to solve E
Problem C Can someone please explain how answer should be 1. n = 4 , a = 1 2 3 4
Suppose you decide to take 2, then the opponent will take 1 and you won't be able to make a move so, you win. Suppose you decide to take 3, then the opponent will take 2, then you will take 1, because of which your opponent wins. Suppose you decide to take 4, then the opponent will take 2, then you will take 1, because of which your opponent wins.
Thanks buddy :D, Misread the problem :(
Just to make sure my A doesn't fail, can someone verify this logic:
If string is "()" it is impossible.
If string is alternating for example: ")()()()" then you can use "(((...)))"
Otherwise you can use "()()()()()..."
Here is the code.
you can just take the smallest case where length = 2 and you find all the combinations to form, that's {"()", "((", "))", ")("} if it's the first one then it's impossible then if it's the second and third one if it's in any substring in the string you can just print ()()...() if the last one in any substring print (((......)))
Yep, basically if $$$s$$$ doesn't occur in $$$(((...)))$$$ then it's an answer, otherwise if $$$s$$$ doesn't occur in $$$()()...()()$$$ then it's an answer, otherwise there is no answer.
I was thinking along the same line but could not prove to myself why it works. Can you tell why this works in some mathematical proof ?
Basically, we can prove by induction:
Let see if $$$|s| = 3$$$:
$$$((($$$ — $$$()()()$$$ is suffice.
$$$(()$$$ — $$$()()()$$$ is suffice.
$$$()($$$ — $$$((()))$$$ is suffice.
$$$())$$$ — $$$()()()$$$ is suffice.
$$$)(($$$ — $$$()()()$$$ is suffice.
$$$)()$$$ — $$$((()))$$$ is suffice.
$$$))($$$ — $$$()()()$$$ is suffice.
$$$)))$$$ — $$$()()()$$$ is suffice.
If $$$|s| > 3$$$ then it will have $$$1$$$ of those cases as substring, so it will be solvable with the same answer. Can't think of better way...
if n=1 ---->impossible if n=2, ()--->impossible, )(---->(()) n >= 3: if in the string str, we found "((" or "))", then just construct ()()().., such string "((" is not substring of ()()()... otherwise, the string must be alternative, ()(.....or )()...., in this case, we construct ((((...))))
You just have to cover all the cases. There are three partially-overlapping cases:
()exactly.)(.((or))or both.We can easily prove that this covers all cases: if |S| = 2 then
(),)(,((and))are exactly the four possible strings. If |S| ≥ 3 either S contains)((case 2) or it is a sequence of(followed by)and since |S| ≥ 3 there must be at least two of one character in a row (case 3).In case 1 there is no solution, because any balanced bracket string must contain
(). For case 2(((...)))is a solution because it doesn't contain)(. For case 3()()()..()is a solution because it contains neither((nor)).i think you ignore the case when n=1 and string="("
it's not a valid case
minimum n is 2, so such case isn't possible. And even if this case was valid, the problem is impossible to solve because RBS has to contain both '(' and ')'
In my solution I just make 2 strings "((...))", "()()..." and checked if input string is a substring of first, then the second is the solution. Also the "NO" answer comes only with "()".
Is it just me took a WHILE to clearly understand C...
Agree
Can you tell me how to solve problem C? I don’t quite understand why other people’s code
Same
B felt like as one of the most unfun kind of math problems
It felt really forced, like they had to place a problem B somewhere and came up with a contrived problem
During the contest I've got the general idea pretty quickly, something like:
But translating that into actual expressions felt terrible, at least for me
Why all the problems is about to find all possible combinations of the answer and build the solution upon that, it felt like disguised combinatorics round.
Video editorial for problems A&B:
https://youtu.be/p-nKn3Hg9JE
Thought would be useful!
IN ENGLISH
That's really nice! I appreciate people making video editorials in English (looking at you Mustafa), always much easier to understand. Hopefully it'll be useful to people who couldn't solve it!
How to solve D? I have only one observation: Lets call number of 01 — number of 10 "Balance" When I swap i, j such that a[i] = 1 and a[j] = 0 I add i — j to balance and j — i otherwise Please explain full solution to me
UPD: My greedy solution was wrong
WTF
I did this and got Wa on test 5
Dw his guess is wrong :)
Can you prove that this greedy approach works? I mean, apart from the fact that it passes tests. I had similar idea but I couldn't think of a nice proof
every swap you can decrease the diff between 01 and 10 by 2, and you can always increase that by adding an additional character to the left or right that changes the diff.
So just pick pair i,j that max out that diff every time.
In fact it doesn't work and it's hacked
:c
I solved it using 3D-DP. Sketch: Assume w.l.o.g there are more 10 than 01. Then there is a diff > 0 you need to fix. Swapping a 1 with a 0 on the right fixes 2*(difference of indices). Now you can do similar to subset sum dp (you need a third dimension to store the position of the first 0 you used). The value of an entry denotes how many swaps you need to achieve this sum. Total runtime O(n^4).
How much memory do you use?
A little bit less than limit (237MB), but I could get it down by factor 8 quite easily (dp entry only needs 1 Byte + the diff can be upper bounded by (n/2)*(n/2)). You can also get rid of the first dimension completely just like in subset sum.
And how do you deal with situation in which you need to swap some 1 with some 0 and then you swap it again with some other 0?
I think this can't happen because then you could have just swapped it with the other 0 in the first place.
OH XD
Now i see
Thanks
Can you elaborate more on your DP-States?
One invariant could be: $$$dp[i][j][k]$$$ is how many swaps you need for sum $$$j$$$ using only '$$$1$$$'s with indices between $$$i$$$ and $$$n$$$, assuming the smallest position of a '$$$0$$$' you have used for a swap is $$$k$$$.
Go through from $$$i=n$$$ to $$$i=1$$$ and compute transitions.
Thankyou
Why would you want to store the smallest position of 0?
You somehow need to ensure you don't swap two 1's to the same 0 position and this is a way to achieve it.
for D we can see that whenever a swap happens, the sum of 01 and 10 doesn't change. Also looking at 10000, we can see that we can just move the 01 and 10 2 unit closer to each other by swapping an additional 1 more character to the right.
tldr is the diff between 01 and 10 count must be even. Swaps 1 and 0 always move the diff between them by an even number. So just swapping the best 1 and 0 pairs until they are equal
Is this a greedy problem? Wondering why s <= 100.
this was WA2forces for me but the problems were good
why dp solution doesn't work in c, this is my sub [submission:https://codeforces.com/contest/1860/submission/219347506] thanks.
thanks
Problem E is almost the same as this one. Check out 211055789 and 219307318.
A appeared to be tough & was a strange problem. The statement of B was so confusing with notations like a1 & ak. The problem statements were hard to comprehend. More of a read-carefully-be-patient test than a problem solving test.
Nice contest! Gain a lot.
Can we do E like this:
There can be 26*26 different substrings of length 2.
And for every query instead of finding a minimum number of moves to reach an index we find minimum moves to reach a substring. This can be done in (26*26*m).
suka...
In Problem D what can be the maximum size of 0 or 1 individually as the string can always be made balanced
Maximum size of 0 or 1 doesn't matter for solution.... But maximum value of balance matters which can be at most n/3*n/3
How to solve B?
ternary search or some simple math
c was pretty nice
Problem statements required hell lot of patience reading.
why dp solution dosent work for c , 219347506 thanks.
I wish your code was readable.
come on its not that complicated :(
It is
really? Can you point to the confusing parts?
Well I was scared by very big template and by lambda function solve. I don't know, is it really convenient to use lambdas?
yes for me, I don't need to make global variables or send them to a function or to reinitialize the containers .
bro your code looks like its from a nuclear reactor in Iran
:)
You are using memset on a 3e6 size dp for every test case. The total possible test cases are 1e4. So time complexity of your code will be more than 1e10.
oh shit, I forgot about memset, thanks.
maybe because it's a segment tree problem ?
bruh what do you need all those defines for, bet you don't use even a quarter of them often enough to justify adding them to the template
yeah, but I am too lazy to clean it.
Couldn't solve C because I swapped a1 and ak while taking the input OR
cin >> m >> k >> ak >> a1;
Help me cry
I SUBMITTED 3 WA BECAUSE OF THIS.
THAT SUCKS
so many case handling :((
˙◠˙˙◠˙˙◠˙
Screencast with commentary
without music :"(
how can you understand what he is talking about if there is the music
Problem B is one of the worst problem description
nah it's good
you are true , it was very clear.
The worst tasks I've ever seen
does anyone has proof for greedy approach on D ? also I would appreaciate it if you could explain the dp approach , I couldnt find it in contest time :/
How to solve D?
I can't prove my solution. But actually greedy approach works. Let's denote $$$cnt1$$$ equal to number $$$01$$$ occurs in $$$s$$$ as subsequence and $$$cnt2$$$ equal to number $$$10$$$ occurs in $$$s$$$. Now let's find such $$$i$$$ and $$$j$$$, that after swapping $$$s_i$$$ and $$$s_j$$$ we will make $$$|cnt1 - cnt2|$$$ smallest. Swap $$$s_i$$$ and $$$s_j$$$ and continue doing this until you get $$$|cnt1 - cnt2| = 0$$$.
Nvm got hacked, lol, hahaha
Does, Problem B is based on Binary Search?
ITS MATH CALCULATION
I did it ternary Search
you can't even do simple math?
You don't need to be rude to make a point! What's wrong if someone solve it with ternary search instead of SIMPLE MATH!!!
dw bro he's my friend we're just joking
No I don't think so , there is no monotonocity of some property , It was just greedy one.
Took so much time on A. I think A is much harder than B and C.
Trivial cases were the key idea to solve A.
I think people who came up with the idea with trivial cases felt it is so easy, but those who are not, they(that includes me) must have struggled.
IMHO, in problem D, It would've been better if
" In one operation, you can: choose two characters in s and swap them. Your task is to calculate the minimum number of operations to make the string s balanced. "
than
" You can perform the following operation any number of times : choose two characters in s and swap them. Your task is to calculate the minimum number of operations to make the string s balanced."
It sounded like this problem is about feasibility. (printing out YES or NO).
Actually a simple way of solving problem A is to check whether there exists a pair of adjacent brackets that are both left or right (like “((“ or “))”). If true, the answer should appear like “()()…()” If false, the answer should appear like “(((…()…)))” The only exception is string “()”, u just need to especially judge if the given string is exactly that thing. I personally consider C harder than A, because it took quite a long time for me to figure out how to solve LIS in O(nlogn) time…
i don't think lis is needed though:
My submission that passes tests 219294134.
When i find a new m2, that element is winning because it can't reach any former m2 (all of those are bigger) and there's an m1 that the m2 can reach (meaning that a move exists and it leads to a losing state). It's easy to see that all the other moves are losing : if an element doesn't enter any of the ifs, it's trivially a losing one as that can reach another losing element (basically it can reach any m2, as it's bigger).
This proof feels harder than the code, i 100% didn't think it this way when i wrote it but it feels right.
Wow that's a good solution!
I simply tried to calculate the LIS ending at each point, and if its length is exactly 2, it is a possible position that Alice places the chip.
However my calculation didn't stop even if the LIS' length had already exceeded 2. So your solution is a better one!
This is my code, for reference: 219329123
From the rules of some earlier rounds:
" 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated "
Will this thing (rejudge on successful hacks) be used here?
n^4 passing for D:
Hope codeforces catch all of them https://youtube.com/@codingSchool2.O
Hi, i am a beginner , tried the first question didn't got it then went to the second one , thought that i might be able to do it but then time passed and i wasn't able to do it. can someone give solution or tell where i can find proper solutions suitable for beginners.
Hope that my solution is right and easy to understand 219268377
That code is extremely clean. Amazing job man
I would recommend you to firstly participate virtually in some Div3 or even Div4 rounds. Difficulty of problems there should suit you way better than Div2. But to be fair, usually problems A and B are a bit easier than in this contest. Good luck!
DW, this contest was way harder and weirder than other div2 contests. Try again in another contest.
A is the kind of stupid problem that you take a bold guess by intuition. I looked at it for 5 mins and guess I only have to test ()()() and ((())) kind of bracket sequence and luckily it passed. I did a little proof after this. And B is just simple strategy based on modulo. You can find editorial shortly after the contest where you read solutions.
where can i see the editorial , on youtube or it is available on codeforces only?
First check cf editorial, and then if you don't understand (cf editorials are not necessarily well-written), there is a comment section below the editorial. Still don't understand, go find other non-official explanation on the Internet (I use Chinese). Or you may find competitive programming communities somewhere to ask.
Nice massive hacks on D
Can someone show simple test which fails on greedy solution?
For example like this: 010000100000100010001011010010000110010011000101010001100100110111000101110111011110100110101
I HAVE OBSERVED THIS TREND IN RECENT CONTEST THAT LANG OF QUESTIONS ARE TOUGH TO UNDERSTAND. ITS MY HUMBLE REQUEST TO MAKE SINPLER STATEMENTS IF POSSSIBLE
I do agree that it's frustrating to read long statements. Moreover, I also agree that long statements does not fit for contests where time is short. Especially, for platform like CF. However, your all caps comment made it hard to read. Hence, my conclusion is your comment is not much different from unnecessary long statements! LOL :v
Can someone write a blog about this because more than 800 watched the videos https://youtube.com/@codingSchool2.O
MikeMirzayanov plz ,, do something
I don't think it's feasible for Mike or any other admin to track all the cheaters. Especially, folks who share codes outside the platform anonymously. At the end of the day, it's just an online contest. If you focus on learning and growing your problem solving skills it does not matter how many cheaters out there. Certainly, they will have some impact on the rating. But rating is just a number. If you can solve 2 problems in div 2 on average now, your concern should be how can you solve 3/4 regularly in the future. Cheaters will most likely stay at the same level because their main focus is not learning and growing skills IMO. That means at some point you will surpass them if you continue working on improving. And from that day onwards, they will not have much impact on your rating.
How to solve E? I already knew how to get the shortest path from a pair of character to another. But my solution seems to run in m*26^4 so it didnt pass :(
Let MX denote 26*26. We can create (n-1+MX) nodes weighted directed graph. n-1 represents cursor position while 26*26 extra nodes represents all possible two length strings. For the ith position of cursor we have to add edges of weight 1 between each pair consecutive positions ,an outgoing edge from current position to string cursor is representing as weight 0 and incoming as weight 1. Now we can calculate distances to all other nodes from those MX nodes in O((n+MX)*MX) using 0-1 bfs. Now we can reach from p to q without going to any of those extra nodes in abs(p-q) steps or if we visit any extra node the answer from such a node can be computed as d[p]+d[q]-1.So each query is computed in O(MX). So final complexity stands O(MX*(n+q)) for my approach.
Ah okay that makes sense, my solution was a bit different than yours. Thanks for the reply!
Around 1/3 of Problem D AC's hacked
Were the hacked solns greedy?
my greedy got hacked
I have no idea but looking at the constraints I'd be surprised if a greedy solution was intended. Didn't even think about it because of this, so dunno.
most likely yea, intended solution I think uses O(n^3) dp. I ended up doing some omega scuffed greedy that somehow passed pretests, but from looking at hacked solutions I already knew that something was off
Can someone explain the C problem solution, or just name the type of problem? Got the A and B, C was out of time for me.
UPD: Damn it was easy....
problem statement of B was difficult for me to understand
A simple solution for C
Key solution: A number is unlucky iff 0 or 2 jumps to left are possible from it.
https://codeforces.com/contest/1860/submission/219359755
Video Editorial For problem A,B,C
https://youtu.be/wZF5qfvBhuM
Editorial for problems A&B:
https://youtu.be/p-nKn3Hg9JE
Thought would be useful!
do we get anything for hacks? Like less penalty?
Why so much down votes ?.At least they puts efforts to make contest for us.We don't pay anything.
Great contest, although I didn't address D. This idea of D transferring the contributions generated by the two 01s to the characters themselves is great!
How i can solve B with binary search?
Hello everybody, I made a submission for C a few minutes ago (after the contest). Even though it says Accepted, i have the feeling that it will FST. It's just over 15 lines (apart from the template).
Try hacking it.
int n; cin >> n; vi tab(n); for(auto &i: tab) cin >> i; set<int>zeros; set<int>ones; zeros.insert(0); ones.insert(0); int ans = 0; for(int i = 0; i < n; i++){ if(*zeros.upper_bound(-tab[i]) == 0) zeros.insert(-tab[i]); else if(*ones.upper_bound(-tab[i]) == 0){ ones.insert(-tab[i]); ans++; } } cout << ans << endl;Submission: 219367730
It is correct, because it's a convoluted version of the solution vinren explained above. Compare with his solution: 219313622.
To see that it's the same, consider that whenever you do
set.upper_bound(-x) == 0you are effectively asking: is the minimum element in the set less than x? But to answer that question you do not need to maintain the complete set of values; it's sufficient to track just the minimum.Codeforces ---> Queueforces
Shall I get bonus points for a successful hacking on the 12 hour hacking phase?
No, but you can hack those in front of you and get higher rating
If CF give bonus point, people can create alt like mine and submit some thing like if(test==69) cout << "FREE POINT";
Did somebody use this approach to solve problem B? I just come up with it now. The code is commented so you can understand whats going on
Well it is hacked now.
Thank you guys for the contest . it was a very good contest, i hope next contest will be the same
Thank you guys for the contest . it was a very good contest, i hope next contest will be the same
I find myself stuck in A B C general math problems. Due to this I am not able to give time to harder problems during the contest.
This thing happened with me in last contest's B as well as this contest's B. I find it difficult to understand some general math based solutions.
Can anybody give me suggestions for how to quickly come up with mathematical solutions. This really slows me during the contest. Even while practicing problems I have noticed this weakness.
I am quite ok with number theory problems. Difficulty arises when some general math and greedy are there.
Try to come up with some obvious greedy ideas, then try to split this greedy in a small number of cases, and work with each one individually. Eventually you will become good at understanding formulas that you're writing
it's a really intersting round
You can't drink and drive even if you get a negative rating, it's extremely dangerous.
No editorial page this time? If any one find pls share
I didn't participate in the contest. But why so many downvotes eh? I think problems were good. I love A,C,D, and E. Although I find B is a bit too "mathy" but I don't think this contest deserves that much downvote tho
Maybe due to the weak tests for D. I like the problems themselves too.
I guess pretests for D were weak so that "hacking phase" served its intended use.
There are no so-called "pretests" in CF mode. I can understand weak pretests in CF mode (actually most users don't). However if the tests in exICPC mode are weak, the wrong solutions will pass as long as there are no users are hacking.(for example, when some significant events take place and high-leveled users are not online)
Anyway, optimistically, this gives a lesson to user who do not prove and check their solutions. This will influence a lot of people in future CF mode contest!
It hurts so much to get hacked for the first time, maybe many wrote to the greedy in D and will be able to understand me.
It hurts so much to get hacked for the first time, maybe many wrote to the greedy in D and will be able to understand me.
i am so much disappointed.long time later i could not solve a single problem.
Why not system test (i’m new here pls no downvote)
Educational contests are different from the normal contests.
In Educational rounds and Div-3,4 contests, system testing takes place few hours after the hacking phase finishes. Also, system testing will include the successful test cases generated by hackers.
Problem C is so interesting that I spent almost one hour on it.
Почему никто не делает видеоразборы на русском языке? Было бы прекрасно, если нашлись бы такие люди.
Can anyone tell where can we find the editorial to this contest?
The author hasn't release the editorial yet.
Hi, awoo, do you play genshin or starrail, which leads you to provide these weak pretests?
Tests is good, you got fst because you got skill issue.
P/s: We don't have pretest here. You get WA on hacks (because of your skill issue.)
Problem E is actually similar to this.
Good round, but problem B...
Hackforces round.
I am currently a newbie and the details above says that the contest is rated for those with rating below 2100 so why is the contest listed as unrated on my profile? Someone mind explaining?
Educational Rounds, Div.4 and Div.3 rounds rating updates takes time.
Why though? Just curious.
Because they have an extra 12 hour hacking phase.
Yeah, but even after that it takes time.
So, like the ratings for this contest will update right? It's not unrated isn't it?
Rating was updated
the problems were good. thanks for the contest adedalic BledDest awoo ! ignore the downvotes
agree I liked it.
Learn to be honest.
learn that you dislike problems because you are unable to solve them (due to skill issue)
Learn that you only liked the round because you solved the 3 easiest problems and got +ve.
"learn that you dislike problems because you are unable to solve them (due to skill issue)"
Didnt comment on this? does that mean it is true LOL
Besides, the complains in this contest were mostly regarding B and C, and if you say that they are "easiest", then you shouldn't be crying about the contest being bad, you should focus on quality of D-which you cant cuz skill issue again
why this round is showing unrated even if i am in Div 2 ??
Wait for some time, the rating will update in 2-3 hours. It always shows up as unrated shortly after the system tests.
Is the contest rated or not?
When is Tutorial going to get release next year?
Can anyone please explain this elegant solution (219271388) of D by jiangly?
wow, that's a fantastic solution.
I guess the idea is: let c00 be the count of 00 pair, so does c01, c10, c11. Given c01 = c10, we have
let c0 be the number of 0s, c1 be the number of 1s. we know the sum of the total number of pairs begin with 1 and end with 1 is c01 + c10 + c11 + c11, so for each it is ( c01 + c10 + c11 + c11) / 2,which is param "need"
then uses a dp[i][j][k] to find the min ops to achieve need, where i means consider first i items, j means the total 1 been used, the k means the (c01+c11) till now. And the value is how many position we put 1 but it is 0 original.
The answer is dp[n][c1][need], because each swap we can put a 1 in its final position
very nice explanation, thank you!
Nicely Explained !!
Thanks xioxio :)
I want to report @erfge56gyt4w5h356 for obfuscating his solution of E.
https://codeforces.com/contest/1860/submission/219309571
I though this wasn't allowed by the contest rules.
I didn't solve a single task — I was unsuccessfully struggling with task B the whole round, — but still got +125 points ¯\_(ツ)_/¯. Is there any article on how rating on Codeforces is calculated?
Maybe this will help link
I'll try to explain it without going into the math behind it. In the first 6 rounds combined you get a bonus rating of 1400, split as 500-350-250-150-100-50 and your assumed rating for your first round starts at 1400.
Your rating change according to your performance will be calculated as bonus + (whatever you get because of your assumed rank vs gotten rank)
So basically you had a 250 bonus already as it was your third round and whatever you got was a score that stacked onto that
where is the editorial?
Authors of Edu. rounds like to post editorial in a few days after the contest, they do this so that the participants can discuss their solutions without authors ideas.
At least that's what I remember from some comment from awoo or bleddest
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
.
I had misread problem C, B was like too many if else statements.
I misread problem C, it was interesting though. Also, B was like too many if else statements!
Amazing contest! Thanks adedalic BledDest Neon awoo
Good Contest
Hello, I'm a boy from an Indian village. I wish to become proficient in the Java Programming language. Could anyone please suggest the best freely available resources to master it? Unfortunately, I don't have the money to purchase a paid course. I hope that God will provide you with the strength to help me.
gEEKS FOR gEEKS
It was the best codeforces round (in my opinion), thanks to BledDest, Neon, adedalic and awoo!
About my solution to Problem C 219315276 was judged to be duplicate, I used the source code that had been published in 2017, its content is linked at: https://blog.csdn.net/George__Yu/article/details/75896330 Your text to link here... I don't think that constitutes cheating
Где сложности???
How this guy who had secured a rank of 268 but 28 rank is shown on his profile and rating changes are also based on that rank?
User : https://codeforces.com/profile/erfge56gyt4w5h356