Привет, Codeforces!
В 31.08.2023 17:35 (Московское время) состоится Educational Codeforces Round 154 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Отдельное спасибо тестеру раунда stAngel за ценные советы и предложения!
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Harbour.Space University в партнерстве с Giga (Unicef) предлагают стипендию для получения степени магистра в сфере даталогии, а так же опыт работы.
Мы ищем различных кандидатов от junior до mid уровня:
Специалист по работе с данными:
- Хорошие знания в области машинного обучения
- Опыт работы с инструментами визуализации данных, такими как matplotlib, ggplot, d3.js., Tableau, которые помогают визуально кодировать данные
- Отличные коммуникативные навыки – невероятно важно описывать результаты технической и нетехнической аудитории
- Сильный опыт разработки программного обеспечения
- Практический опыт работы с инструментами обработки данных
- Способность решать проблемы
- Аналитический ум и отличное деловое чутье
- Высшее образование в области компьютерных наук, инженерии или смежной области приветствуется
Аналитик данных:
- Подготовка данных
- Анализ и изучение данных
- Знание статистики
- Анализ и визуализация данных
- Отчеты и панели индикаторов
- Общение и переписка
- Знание предметной области
- Ориентированность на решение
Все успешные кандидаты будут иметь право на получение стипендии со стопроцентной оплатой обучения (29 900 евро в год), предоставляемой нашими партнерами.
ОБЯЗАТЕЛЬСТВА КАНДИДАТА
Обучение: 3 часа в день
За год обучения вы завершите 15 модулей (длительность каждого 3 недели). Ежедневная учебная нагрузка составляет 3 часа, плюс домашнее задание, которое нужно выполнить в свободное время.
Работа: 4 часа в день
Погрузитесь в профессиональный мир во время обучения. Вы будете учиться у лучших и с первого дня сможете применять свои новые знания на практике.
ТРЕБОВАНИЯ
- Опыт работы в отрасли
- Международный опыт
- Стремление к обучению
- Устойчивое развитие ключевой момент для вас
- Желание работать на общественную организацию
UPD: Разбор опубликован
In blog : The problems were invented and prepared by ..., Roman Roms Glazov, ...
But in contests page Roms doesn't exist.
Hope to stay blue after this round. GL & HF
Fixed.
Good luck! :)
I'm always scared of educational rounds because I tend to do worse in them — but it's never too late to turn the trend around. Good luck everyone!
its not just you buddy, these are just speed forces rounds lately. People solve till ABC and There is huge difficulty gap in C and D. Good luck :D
Last One？
but this time there is huge difficulty gap between B and C.
Some people I saw that they solved D, but not C.
That was me.. I had a stupid bug in my C sol lol. -100 delta for me, the trend continues xD
same here, solved D in just 5 minutes but wasn't able to debug C
Earlier educational rounds used to be educational. Now it's more like easily come up with the logic and implementation in 10-15 mins and debug the code for the corner case for next 20 mins. dsa problems have vanished entirely
Nah now it's just sth like F being unsolvable for the very vast majority of people and E being some classical problem lmao
Edu rounds can educate me that I can't become Master without a clear brain.
Edu rounds can educate me that I'm not at all educated...
ya dalala
Thanks HARBOUR.SPACE UNIVERSITY
Hi all, it would help if you can post some insights/hints for the problems of this contest (AFTER it ends) on https://starlightps.org. Here is the collection for the problems of this contest: https://starlightps.org/problems/collection/cf-edu-154/.
This will help us get more data so users can have a platform to:
Check it out if you're interested. Thanks!
Get ready for the worst implementation problems like always
poor how are you going to solve the problems of 1300 implementation((( i hope you wont die while you write 20 lines of code
lol
remember me kempachi fan!!!.
i am best
today, another step back incoming?
lets compete who will bring better rank today! No holding back now...
ok, how do you feel knowing that you would lose today?^^
Talk about that after the contest... I have new dp now
yare yare daze!
oops
2 steps back:)
Oops
oops
lets see in next contest
I'm unrated. Can I participate? I've never participated in any contest before. This is my first time in codeforces. :')
Of course, you will be rated after you participate in the competition
This is the last contest before the National Day holiday in my country.
I will do my best!
Wish no weak pretests again.
wish not granted
Hopes to get educated from this educational round
Hoping to get more educated in this educational round
Good luck!
It seems that the standings is
brokenunusual currently (it shows all participants in official standings, even div.1). Could you pleasefixredesign thisbugunusual design ASAP?That's not a bug. It's feature.
oh shoot. yeah that sounds about right
Will be delta calculated considering contestants from div. 1 or not?
Can anyone help and tell for which test case my solution is failing? Problem : C Submission link
+++1+++0---0
C>>D.
rly? I solved C in 15mins but 45 on D :) but maybe its just my skill in cp being poor ...
Or maybe mine
adhoc forces
I solved B, D and E using DP :)
What was your states and transitions to solve E ?
dp[i][j]: number of arrays of size i such that the last j elements are distinct
if j = k then the last j elements form a permutation and if j>k it means the last j%k elements are distinct and there are j/k permutations not including the last j elements
dp[0][0] = 1
for transitions:
dp[i][j] = (summation dp[i-1][l] where l>=j and floor(l/k)=floor(j/k), and l is not a multiple of k) + dp[i-1][j-1]*(k-j%k)
k-j%k is the number of possible elements distinct from the last j%k, it's the number of possible ways to make the last j%k+1 elements distinct
the number of possible ways to make only the last j%k — x numbers distinct is 1, just append the xth element from the end
How to solve E?
I didn't solve E, but I think it maybe smth like $$$dp[i][len][count]$$$, where $$$i$$$ is a length of prefix, $$$len$$$ is the maximum suffix, where all numbers are distinct and $$$count$$$ is the number of obtained correct sequences of length $$$k$$$. The number of states is not more than $$$N * K * N / K = N^2$$$, so it maybe correct if all transition is made no longer than $$$O(1)$$$. But unfortunately I got confused in the transitions :(.
Got the same idea, but had no time due to B and C...
What does your suffix mean?
It means the longest suffix of current prefix of length i, where all numbers are distinct
My solution uses this idea, perhaps you can check it out and see if it makes sense to you. 221347739
Thanks
I just figured this out (very close to solving it during contest). You can check out my submission with comments 221395884
How to solve D? do we need to consider some increasing and decreasing slopes?
You can make some prefix negative and rest all positive.
Can you tell me how you came up with this intuition? A lot of people found this fairly easy but I couldn't come up with any solution.
First, assume we are only dealing with positive numbers. For any adjacent a,b, if a>=b, we will have to multiply b and all numbers after it Proof assume there is a c after b. If b is already less than c, multiplying both is the surest way to preserve that. If b>=c, then (again, with positive numbers) no matter what we do we can't change that, so it's still fine to multiply both.
Now we can extend this to negative numbers using similar logic (replace a<=b with a>=b). Since we need a strictly increasing sequence, we can do a single transition from negative to positive numbers, but it may not be necessary (all negative/all positive could be better).
3 contests in a row solving E but can't finish in time, fuck
smb please tell their solution to E?
Same to me for problem C. Long way to go on the revenge journey.
I solved by finding, "in how many arrays does some subarray contribute?"
For this, I use a dp state where dp[i] gives number of arrays of length i, such that the subarray ending at the last index is used.
Now for calculating dp[i], we can first see that elements from i-k+1 to i should form a permutation of k, and for the rest, we can give any element from 1 to k. So we initially set dp[i] to be k! * exp(k,i-k).
Now we need to subtract those arrays from dp[i] which have their last used subarray ending at some index in the range [i-k+1, i), because it will intersect with our subarray ending at i. Suppose we have an array ending at j, which lies in [i-k+1, i). So number of arrays such that last used index is j, and [i-k+1,i] still forms a permutation is dp[j] * (i-j)!. We subtract this value from dp[i] for all j in [i-k+1, i).
Now our answer is the sum of contributions of all subarrays, so we can simply sum up dp[i] * exp(k,n-i), because for all elements after i, we can place anything we want.
Took so much time for C, couldn't even think about D much. How to solve D?
Divide the array into two halves, make first half negative ascending and second half positive ascending. Pick the best answer among all possible half partitions (you can also make all positive and all negative).
If you only multiply by positive number then the answer would be number of elements
isuch thata[i]>=a[i+1]. Instead what we can do is for someiturn the prefix before it to a negative increasing array. If the prefix containskstrictly decreasing segments then the number of operations needed to convert the whole prefix to an strictly increasing prefix such that all it's elements are negative isk. So we can just check it for each indexiand calculate the minimumHow to solve Problem D? I couldn't solve it, got a headache from Problem C :(
I feel D<C and the implementation of C was complex. What's the easiest solution for C?
my submission: 221301419
You just need to maintain 3 variables: current_number_of_element, sorted_till(default = 0) and unsorted_from(default = inf) and do casework.
I created a tree and checked for validity using dfs.
I used a lazy segment tree for C
I don't think I've seen this level of overkill since this
It's not overkill at all. I just copied the tree and then implemented it within 5 minutes. I believe it's the easiest and quickest approach to solve problem C.
Hi, can you explain your solution how it works ?
Maintain a pointer and a lazy segment tree where each node in the tree is assigned one of three values: 0, 1, or 2, representing "not sorted," "sorted," and "unknown" respectively.
Consider each type of query as follows:
"+": Increment the pointer by 1 and set the corresponding value in the tree to 2.
"-": Decrement the pointer by 1.
"0": If the node's value at the pointer position in the tree is 1, the answer is "no". If it is 2, set it to 0.
"1": If the minimum value in the range [1, pointer] of the tree is 0, the answer is "no." Otherwise, set all values in the range [1, pointer] to 1.
💀
I kept track of L = current length of the array, A = the maximum possible number of sorted elements, B = minimum possible number of sorted elements. If B == L, then 0 is impossible. if A < L, 1 is impossible.
This makes sense to me. It's short to implement and lighter casework. 221383919
For a long time I could not understand the author's solution to this problem, but I understood your explanation right away, it is so simple and understandable. Thanks a lot!
Let's make a stack which maintain values where 0=unsorted from here, 1=sorted until here, 2=unknown.
When processing query=='+', if stk.top()==0 then stk.push(0) (to propagate info) because array is unsorted obviously, else stk.push(2).
When processing query=='-', if stk.top()==1 then do{stk.pop();stk.top()=1;} (to propagate info) because array is sorted obviously, else just stk.pop().
my submission: 221294647
I used a stack: 221370839
When a new element is added, store whether the array used to be sorted in the stack. When an element is removed, pop the value from the stack.
If we know this array is sorted, then all previous arrays are sorted as well, so mark them as such in the stack (maybe don't do it in O(N) like I did on the contest, lol).
If we know this array isn't sorted and a new element is added, the new array isn't sorted either.
The answer is NO if at some point we are told the array is sorted but we know it isn't, or if we are told it isn't sorted but we know it is.
This is easy to optimize to use O(1) memory, but that isn't needed with the task's constraints.
Maintain a stack of states : 1 if sorted, 0 if not, -1 if both possible. When you add an element it's either 0 if the array is already not sorted, or -1 (since the last element can be decreasing too). For the queries : if last state is -1 and array is sorted erase all the minus ones and replace them with ones.
My 3 variable solution: 221315344
(same as described by adityagamer)
How to solve C?
How to solve C?
If a prefix of an array is not sorted, the arrays to which the prefix belongs is also not sorted. If array is sorted, all its prefixes are also sorted. Just simulate operations from left to right and keep track of the state of the prefix (whether it's sorted, not sorted, or no idea), if you find a contradiction, answer is no otherwise yes.
C is so bad
C is so bad
Huge increase in difficulty from D to E. Why is it that only GM or LGM-s can solve last problem on div 2? It's rated under 2100 but not expected to be solved someone under 2100.
I fully agree, every edu looks like this for some reason.
C was a brilliant problem.Took me an hour to realise it could be solved by set and lower bound.
can you explain your solution?
it can be solved without using any data structures
A: One of "13" and "31" will be a subsequence of permutation of [1, 9], and both of them are prime.
B: Note that during the operation, the occurence of substring "01" can only be removed but can't be created. Since the first and last character can't be changed, there will be occurence of "01" in both a and b after operation, and they need to occur at the same position, so there must be some position that "01" occurs at this position both in a and b initially. On the other hand, if a[i]=b[i]='0' and a[i+1]=b[i+1]='1', we can do operation (1, i) and (i+1, n) both on a and b, then a and b will be the same.
C: We need to maintain 2 values: pos1 = the leftest possible position such that a[pos1-1]>a[pos1], pos2 = the maximum possible prefix such that a[1, pos2] is sorted. When we process query '0', we need to check if pos1<=length, then let pos2=length-1, and for '1' we need to check if pos2>=length, then let pos1=inf.
D: Suppose we need to make a[1, k] negative and a[k+1, n] positive. For making a[k+1, n] positive and sorted, we need a operation for each k+1<=i<n and a[i]>=a[i+1]. For making a[1, k] negative and sorted, we need a operation for each 1<=i<k and a[i]<=a[i+1], then we need an extra operation on [1, k] multiply by -1. Therefore we can solve the problem by keeping prefix and suffix sums.
E: When solving the problem for a single array, we can solve by greedy: Iterate i from 1 to n, when a[i-k+1, i] is a permutation and doesn't intersect with any subarray we've taken, we take it as a valid subarray. Let dp[i][j] = the answer when we consider arrays of length i and the length of the maximal suffix without duplicate elements is j, cnt[i][j] = number of arrays of length i and the length of the maximal suffix without duplicate elements is j. For 0<=j<k-1, the update is dp[i][t] += dp[i-1][j] for 1<=t<=j, dp[i][j+1] += (k-j)*dp[i-1][j] (similar for cnt[i][t]). When j==k-1, adding the missing number of the suffix with length k-1 will create a new permutation as a subarray, so the answer need to be increased: ans[i][0] += ans[i-1][k-1] + cnt[i-1][k-1], and for 1<=t<k, we have ans[i][t] += ans[i-1][k-1]. Thus we can solve the problem in O(n*k) by using prefix sum for range updates.
Your editorial for E is extremely hard to understand, please consider adding some explanations. Thanks.
This is how I did E
can you share ur soln sir
Best contest of my life, Thanks. UwU
Spoiler: ^this man solved one problem
+1
This guy v6ishal is streaming contest live on youtube. Is there something that can be done? Link to the video : https://www.youtube.com/live/JLoIIk9S_F0?si=MASh06PY_pKUhj22 Channel Link : https://youtube.com/@v6ishal?si=uUk4r0I3VbBfbeI_
Am I the only one who thinks the sample testcases are too weak? T_T
+1
btw, I upsolved problem D using DP. I noticed that most contestants solve it with some observations. If anyone's approach is similar to mine(not a good "observer" haha) and is stuck in WA, I hope my submission will help!
hard dp to understand, maybe you can explain what is f[i][j]?
$$$f_i$$$ is the answer considering $$$[1,i]$$$.
$$$f_{i,0}$$$ is the answer when we modify $$$a_i$$$ with a negative number, and $$$f_{i,1}$$$ is the positive case.
Then the following process is kinda natural. If $$$a_i$$$ and $$$a_{i-1}$$$ can satisfy the restriction in one operation, the answer is equal(just "extend" the operation from $$$i-1$$$ to $$$i$$$), otherwise it has to $$$+1$$$.
thus $$$\min(f_{n,0}, f_{n,1})$$$ is the final answer.
ah, it looks the nested markdown list is broken...
Did anyone else solve B using dp because it seemed simpler than trying to find a greedy solution or is it just me?
SleepingThread
me
It was the worst Educational round (in my opinion), thanks to BledDest, Neon, Roms, adedalic and awoo!
Did you participate in this EDU? I couldn't find you in the standings.
A was very tricky
this isn't an educational type round imo. just tricky constructive implementations
Since when does CF give penalty for failing on samples?
Since the beginning. It only doesn't give penalty if you fail test case 1 in order to avoid cases of "I accidentally submitted the wrong code". But if you fail test 3 and it's in the samples it's still going to give penalty.
Must've confused it with some other judge... Thanks
Does anyone have an example where doing a prefix sum instead of suffix sum for D doesn't work?
What exactly do you mean by that?
When I made my dp array to count the number of operations needed to convert the array to strictly increasing, I just made a prefix sum array and assumed I could've just taken some suffix from it, instead of making a suffix sum.
I did the same way. I guess your implementation is wrong in some corner case, don't know where exactly. Maybe my solution might help
Hmm that's weird. I just set the first index as 0 and just iterated thru and added 1 if current element is <= prev element
Is Someone tell me how to i solve A & B fast in div2 contest. To give me any advice. Thanks.
Practice Cs, a and b will seem easier and you could get them faster.
Help me explain problem C. test case: ++++0++---1. why the result is TRUE
List of numbers inserted in order:
1,2,4,3,5,6.The first 4 elements are not sorted so the
0and after inserting remaining 2 elements you remove the last 3 elements which leaves us with1,2,4which is sorted so the1.until the array size reach 4 you don't know weather it's sorted or not when the array size becomes 4 0 appears which means array is not sorted and it can be due to 4th element or any of the first 3 elements after that 2 elements added last 3 elements removed we are left with first elements and we don't know weather it's sorted or not so it can be sorted sorted and the sequence is correct for eg:- add 1, add 2, add 4, add 3 -> unsorted add 5, add 6, remove 6, remove 5, remove 3 array becomes 1, 2, 4 -> sorted
for each + sign append the following number
2,3,4,3
after this it is 0 so the array formed is unsorted again for each + append following number
2,3,4,3, 5,6
now remove three number from last as we have — then we get 2,3,4 after this it is 1 and also the array is sorted so it is true.
Can anyone explain the observation of problem B as A[i] == 0 and A[i+] = 1 for some index for both A and B?
Video Editorial for Problem A,B,C,D.
Can anyone please tell error in my soln for problem C. I am getting WA on 2638th test case 3. 221366386
same for me bro, I have -12 at C and I'm gonna lose my specialist :(
First two solution by recursion
1) Problem A
2) Problem B
Upvote If u like my solution
.
E is very cute
Can anyone provide a counter example for this submission for problem C — 221365170
you may try this testcase: 1 ++0++0++0--1 expected: NO your solution output : YES
Damn this was the case that caused the whole problem for me yesterday!! Let's smile and move on :') .
I always find educational rounds tricky.
ABCDE are all doable but I wasted too much time on C just to figure out how to implement "properly".
Disappointed that i could't solve problem D during contest.It was doable and bit easier than usual problme D of educational rounds.
Hi all, it would really help if you can post some insights/hints for the problems of this contest on https://starlightps.org ! Here's a link to the problems: https://starlightps.org/problems/collection/cf-edu-154/. This will help us get more data so users can have a platform to:
Check it out if you're interested. Thanks!
Had been solving 3rd problem from the last 6 contests, Couldn't solve this time
Why should there be no pretesets in problem C with |s| = 2 * 10^5?
I set my N ( MAXN ) equal to 10^5 and got time limit on system testing. :(
In problem c can anyone tell me where my code fails this on
++0++-1It should output NO
Waiting for rating change.
Continuously pressing F5 in front of the computer because I am confident that I am finally going to become a master after the rating change.
congrats bro for becoming master
thank you.
congrats!
hackational codeforces round
Can someone explain me why my code fails on problem C 221400131
++++1-0
When will editorial drop?
I am waiting for the moment to reclaim my blue.
i am waiting to become specialist for the first time :( why are the rating changes taking so long
Nothing can make us happy without patience
I think the rating changes will be executed soon!
Enjoy your day ^^
Is there a math solution for problem E?
My solution for C got accepted during the contest, but it now shows TLE. Day ruined :(
why ML in B so tight, what is the point of cutting off dp solution ?
UPD: my bad, I know dp solution (221428793) can be implemented in O(n) space complexity, and I will more care about space complexity next time
I couldn't be any more unlucky. Missed 2100 by 1 rating point :(
What is case 58 of test 3 in problem D? I've been trying to figure out what's wrong with my solution since yesterday but I can't figure it out. Can someone tell me what that test is, or help me find a counter example for my solution? Link to my solution: Your text to link here...
Where is the editorial?
Problem E...
say DP(n) = total sum of costs of arrays of size n.
DP(n) = C(k) * (DP(n-k)+1) + C(k + 1) * (DP(n-k-1)+1) + ... + C(n) * (DP(0) + 1)
But I can't get formula for C(i), number of arrays of size i, such that only the last subsegment of length k has pairwise distinct elements.
Can someone help, please? ;((
EDIT: (mistake in DP(n), I think it should be: DP(n) = C(k) * (DP(n-k)+k^(n-k)) + C(k + 1) * (DP(n-k-1)+k^(n-k-1)) + ... + C(n) * (DP(0) + 1)
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Does anyone know the 682th token for tc3 for C? My soln is here: soln although it maybe be abit unreadable
Overall good contest C was little tougher.
Why Was My Submission Skipped Despite Submitting First
https://codeforces.me/blog/entry/120756
NO