Привет, Codeforces!
В 25.05.2023 17:35 (Московское время) состоится Educational Codeforces Round 149 (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 Бангкок
Отличные новости, Codeforces! Harbour.Space Bangkok Campus предлагает 10 полных стипендий для изучения Computer Science или Data Science!
Присоединяйтесь к нам в Harbour.Space в самом сердце Бангкока, Таиланд, и откройте для себя целый мир возможностей. Мы с гордостью сообщаем, что недавно одержали победу на SWERC, одном из самых престижных соревнований по программированию.
В Harbour.Space у вас будет возможность учиться у таких известных экспертов, как MikeMirzayanov и Errichto. Эти исключительные люди привносят свои знания и понимание отрасли, создавая динамичный опыт обучения.
Став частью нашего динамичного и инклюзивного сообщества, вы будете сотрудничать с блестящими умами, способствуя развитию культуры роста и инноваций. Наши квалифицированные и талантливые студенты имеют возможность соревноваться в ICPC, демонстрируя свои навыки на мировой арене.
Присоединяйтесь к нашим выпускникам, которые работали в ведущих компаниях, таких как IBM, Google, Deloitte, Amazon и других, прокладывая путь к успеху.
Требования:
Обучение: 3 часа в день
За год обучения вы завершите 15 модулей (длительность каждого 3 недели). Ежедневная учебная нагрузка составляет 3 часа, плюс домашнее задание, которое нужно выполнить в свободное время.
Требования университета
- CV
- Аттестат об окончании старшей школы/диплом бакалавра
- Знание английского языка
- Занятие призового места любого соревнования по программированию — это плюс!
Не забудьте подать заявку до 30го июня, 2023, чтобы иметь шанс получить стипендию и снизить плату за подачу заявления.
Готовы начать свой путь к успеху? Подать заявку сейчас.
Мы с нетерпением ждем вас в нашем университете.
Всего наилучшего,
Команда Harbour.Space
UPD: Разбор опубликован
I seriously want that Mike's T-shirt...
Me too!
me too, how to buy this, please anyone
Please don't be another SpeedForces Edu Round, otherwise excited about this.
Please don't be another HackForces Edu Round
Now it became guessforces.
they literally just made speedforces
not really, actuallly problem F seems pretty easy ( I didn't solve it, my solution fails at 23 test case ) .
My implementation is little hard, SSRS_ has implemented is very easily with two priority queues.
basically, we need to apply binary search on the final time, and maintain how many editorials we can write in the given time, if we split at index 'i' ( splitting that first person writes as many as editorials from index '1' to index 'i', and second person writes as many editorials from 'i+1' to 'n' within given time ) .
its taking too much time to be in queue is it problem on my end or happening with yall
WHY ARE THERE NO TESTERS FOR ANY EDUCATIONAL ROUNDS?
this is pure stupidity from the organizers
https://mirror.codeforces.com/contest/1837/problems never gets updated! I waited 10 minutes and then finally got to know it's WA on test 1 after 10 minutes when solutions were rejudged. queue is also long, taking so much time for the verdict
Still in queue for B. Should i resubmit?
https://codeforces.me/contest/1837/submission/207170399 была на 10 минуте, перетестирование позже. Уберите её, пожалуйста!
stringforce
"problems and examples will be in announcements"forces
by the way speedforces too HUUUUUUUUUUUUUUUUUUUGE gap between D and E
F seems easier than E to me.
(()deforces
I dont think i will participate in edu rounds anymore. I asked if my submission is going to be judged after it was in queue for 10 minutes. While I got the answer it was judged and the answer was "No comments". There is no need to be arrogant and in my opinion that was. Also, this would not happen if they tested the round.
"No comments" is very classic answer if they don't want to tell you anything, it wasn't arrogant (in my opinion).
Don't wanna be this man, but since when experts struggled to solve C?
it's a bit of an exaggeration, but there was Educational Codeforces Round 133 (Rated for Div. 2) last year where C had under 1k solves.
I'm aware about that, just wanted to point out that it is a bit odd comparison.
one time Div2C was NP-hard
This contest is really bad. What is this problem D? The solution is pretty dumb for a D. I think ABCD were really silly and this round is really bad. I liked problem E though.
so u will be getting +delta then!?
I won't but I'm not mad about that. It's just that the contest is unbalanced and problem D shouldn't be like that
Why time constraint was so small on F? my nlog^2n solution with segment tree could not pass, had to remake it into a priority_queue solution with same nlog^2n. (smaller constant with priority_queue)
did you use only segment tree ? or was it persistent seg tree ?
can you please enlighten how to do it with normal seg tree ? ( i used persistent seg tree ) which was huge implementation. :( .
I used normal segment tree. First I created a vector of pairs where I put { a[ i ] , i } the I sorted that vector and assigned an index to each pair. I use that index to store them in segment tree. Then I binary search on the answer. I use two segment trees, for each answer I rebuild both segment trees in the following way: first segment tree is empty, and second segment tree is full with activated nodes. In each node of segment tree I store pairs, where first element is the sum of times of activated verticies and second one is the amount of them. While checking the answer I go from right to left, activiating each vertex of the current pair { a[ i ] , i } in second first segtree and deactivating in the second one. Now what I need to check is if I can get some prefix of both seg trees such their activated times are less then the answer I am checking and the amount of activated verticies is maximum possible. For that I create a recursive function for each segment tree, where I first check the root of tree and its value, if the time of activated verticies stored in the root is less or equal to answer(which I am checking) time then I simply return its activated verticies count, otherwise I check for its left and right children.
207253723
I used
ordarray to compress the indices.You can maintain prefix sums on a Segment tree.
Iterate on every prefix-suffix pair $$$i$$$ and binary search on the minimum time required to finish the editorials if Monocarp only covers from the prefix and polycarp only from the suffix. Then if you keep a prefix-sum segment tree on the sorted list of editorial times you can quickly search for the last position where $$$sum \leq x$$$ which gives you the maximum number of editorials either of them can cover.
Updates are basically $$$0 \rightarrow a[i]$$$ when $$$a_i$$$ is added to the available for set for either of them and vice-versa.
I used KACTL's Fenwick implementation for it but the idea is the same. 207239500
the worst contest
another really bad educational round
B completely ruined my round,TEST YOUR PROBLEMS.
For the problem D is there any chance that we need to use more than 2 color because i tried many sequence ans only i found only 2 color is enought to paint.
No. 2 is sufficient
Submission can you give me some sample cases where my code fails. Couldn't find any test case as of now.
1
10
)))((())((
2 : 1 1 1 1 2 2 2 2 1 1
You can just reverse the whole string which is 1 color
2 is enough.
Worst contest I have ever seen!..
The sample test case was wrong and it delayed me a lot. Also, because of rejudges, there was a queue so I could not see my verdict for a while.
Also, I could not submit my code in the last 30 seconds maybe it was about my internet but giving the sample wrong was a big mistake :(
I was also unable to submit my code in the last minute. I think we should try using m1.codeforces.com for the next contest
may anyone help me ,plz? i dont know why does it give me WA (problem B:) https://codeforces.me/contest/1837/submission/207236832
1
10
<<<<<<><<<
your answer : 9
correct answer : 7
1<2<3<4<5<6<7>1<2<3<4
Answer should be 3, but your code gives 4. In line 42, why are you doing cnt1--?
Last tasks DEF look like CDE to be honest.
It was 1st Div. 2 round that i almost have solved full. (but wa2 in F on last minutes)
Unrated would be better than this situation
Nice E, solved it 2 minutes after contest:)
The last 2 rounds made me realise that expert is not for me ;(.
i'm gonna cry because of the problem E....
Really bad Contest . Solutions can be easily guessed .
This is really the most unexperienced game, abcd is violent, e is too big, there is no room to learn, total useless。
Again, a shit educational round. Problem A,B,C,D can be done in 25-30 minutes and rating depends on whether or not you incorrectly submit B. Last educational round for me,you learn nothing and only have headache.
Worst Contest !!! Didn't liked the problems at all
Very Cool F except the TL
Very bad experience, all the time was wasted on understanding the meaning of the question, and I once doubted whether I was from Earth
That's a very serious concern if you did indeed doubt your origins as you mention...
I don't know why I wasted time waiting in the queue. Could have solved other Problems earlier. LMAO
Solved A-E and passed pretest of F in 3899ms (which will be TLE in system test).
A: If x%k!=0, we just need to move by x, otherwise since k>=2 we need to move by x-1, and then move by 1.
B: Consider the longest maximal block of same symbol, let it's length be k. Then If we put 1 at every local minimum and k+1 at every local maximum, we always have enough numbers from 2 to k to fill other positions.
C: We can see that a consecutive block of same numbers (0 or 1) plays the same role as a single number, and more blocks takes more operations to sort the string. Therefore, we can fill '0' into a block of '?' between '0' and '0', fill '1' between '1' and '1', and fill '0' or '1' between '0' and '1'. For these blocks at the front or the back of the string, we can assume that there's an additional '0' at front and '1' at back of the string, which won't affect the answer.
D: For any beautiful sequence the number of occurences of '(' and ')' will be the same, so if they are not the same we can simply output -1. Otherwise, there must be a solution with k<=2. In fact, we can record the prefix-sum of the string (assume '('=1, ')'=-1) and change color whenever the sign of the prefix-sum changes, then brackets with non-negative prefix-sum will form a regular sequence, and other brackets will form a reversed regular sequence.
E: We can see that teams of number [2^(k-1)+1 , 2^k] will lose in the first round, teams of number [2^(k-2)+1 , 2^(k-1)] will lose in the second round, and so on. So in the first round, we check 2^(k-1) pairs of adjacent positions, and each pair must contain a team with number larger than 2^(k-1). If any of such a pair contains 2 numbers > 2^(k-1) or 2 numbers <= 2^(k-1), there's no solution. Otherwise we have 2^a*(b!) ways to arrange teams of number [2^(k-1)+1 , 2^k], where a=(how many pairs of positions are both undefined), b=(how many pairs of positions contains no teams with number > 2^(k-1) ). Then we can eliminate teams with larger number in every pairs, and solve the problem recursively.
F: I tried to solve it by segment tree and ternary search in O(n*(log(n))^2), but it takes too long times to pass the system test. Maybe there will be solution with smaller constant.
Not sure if it is compatible with your solution, but in F replacing segment tree with a priority queue or a set gives AC in approx 3 seconds.
Nope, my solution with std::set gives TL on 23 pretest though I changed cin/cout to scanf/printf and had no stupid memory allocation.
207257375
I wish in C++24 std::set is automatically substituted by priority_queue if my code does not contain iterators, BS and etc :)
Probably requires minor constant optimizations. 207226137 passed in 3 seconds.
Quote: "...but in F replacing segment tree with a priority queue or a set..." I mean std::set can't pass TL but std::priority_queue can.
Might be possible, my bad.
Can you explain bit more about "2^a where a=(how many pairs of positions are both undefined)" in your E's solution?
If a pair of position is -1 -1, then we can put the team with larger number on the left or right of this pair, so each pair gives us 2 options. Otherwise, which number will be larger is determined in this pair.
Dont the numbers in range [1,2^(k-1)].Doesn't they impose constraint on other number ? How can they be placed freely ?
For suppose, if 1 is place in Xth pair then 2 cant be placed in (X+1)th pair, if they get placed they 2 will get eliminated in second round but they need to continue until finals ?
If a team cannot be decided in kth turn, you bring it to the next turn with -1, You can only count those teams can be determined in kth turn within (2^k-1, 2^k] and leave those undetermined to the (k-1)th turn. The key observation here is when a team gonna lose is fixed at the beginning. So the whole process is like you assign a seed to a team only if that team will lose in that turn.
use binary search on answer in F instead of ternary search, and then priority queue to find maximum numbers <= sum in prefix and suffix
mine runs in 2.7s
Sorry YocyCraft:( (Hacked)
10k ACs on C and 4k ACs on D, wow! Never seen anything this extreme before.
Nice contest. Incase you are stuck on Problem A, Problem B, Problem C, Problem D. You can use check the following video tutorial- video link
Amazing and very clear video tutorial <3
Very helpful sir ❤️❤️
The Worst Education Round I ever seen.
Reasons:
1.Big changes on problem B:Wrong sample,too long queue(after change),etc.This is terrible.
2.Speedy Edu.Problem A,B,C,D is too easy and E is hard.4,600 people passed D,but only 367 pass E.This mean the rank between ~400 and ~4000 is FULLY depend on the Penalty.
More I know:the B is similar as atcoder contests
were they really too easy and im just dumb? because i only managed to solve A :D
S/he's speaking from the perspective of an Expert. Don't feel too down about your performance. :)
My solution to B got WA on test 1 at first, but once the samples were changed (and before the announcement that the previously solutions would be rejudged) I resubmitted the same code with a no-op to see if it would pass. Then both solutions gave a WA time penalty :(.
I didn't know that a priority queue is faster than a multiset, and if the intended solution has a complexity of O(n * log^2n), then, in my opinion, should have also considered the multiset solution.
Priority queue is a binary heap which is faster than any balanced binary search tree by the constant factors and the access time of O(1)
So many errors in the statements... Contests of such scale should be thoroughly tested!
worst contest I have ever seen!
this round should be unrated due to long queue time(~1 min for every submission) and wrong examples in B.
yes
You are wrong. Here's why.The authors and coordinator put weeks of work into it!
No, all of the educational rounds are being prepared in the contest day.
dude python was not working for question c.It was giving tle at testcase 6
https://codeforces.me/contest/1837/submission/207200150
Because s = s + "1" is O(n^2), but s+="1" is O(n). Yours solution is O(n^2). It cant pass
Try submitting it on another version of pypy, this might help.
Problem B has a quite similar approach with this problem.
I find it a bit funny tho because problem B is about
<>, problem C is about01and problem D is about()lolProblem D statement was not clear
Using discrete to convert time complexity from nlog(1e18)log(1e9) to nlog(1e18)log(3e5) then pass pretest on Problem F. Time limit is toooooooooo tight.
One tip if you got WA on test 8 of E: Please notice the input format.
you are perfectly right! In the contest I have great confidence in my algorithm. But always WA in test8.Damn!When I saw test 8 after contest, I just realized that I mixed up the team ID and seed ID，Oh Damn Damn Damn!!!
Same here, 1h wasted trying to find the WA test 8...
Can someone please assist me with submission :207266027 ? I am unable to determine why my submission is incorrect. Thank you very much.
no need ,the input format is really annoy
I don't understand how this type of input format couldn't have been identified in any of the 6 examples.
Me too, sadly
800-Forces
Can anyone please explain why the answer to this test case is 4 for question 'E':
3 -1 7 -1 8 2 -1 -1 5
What I understood from the question is illustrated below: _ & 5th | _ & _ | 8th & _ | 2nd & 4th So according to this arrangement, 4th would have rank '5' which is not desired. So shouldn't the answer be 0?
plz someone explain this UPD- They are seed-wise arranged
It is given that team 'ai' has seed 'i' ;-;
Therefore for given example: 3 -1 7 -1 8 2 -1 -1 5
Team 3rd has seed 1.
Got my answer. Should have read the input properly ;-;
what is your answer?? having same problem
It is given that team 'ai' has seed 'i' ;-;
Therefore for given example: 3 -1 7 -1 8 2 -1 -1 5
So, Team 3rd has seed 1 Team 7th has seed 3 .. and so on
oh
Is not it 3rd can 5th for the last bracket? I think you have off-by-one error.
Problem B ruined my contest. Please at least take a glance and make sure that the examples are correct (it was so obvious that the examples were wrong ...).
Hello, I enjoyed this contest. thanks to the problem setters.
During the contest, I solved problems $$$A - E$$$. Just after the contest, I solved problem $$$F$$$.
Problem $$$A$$$: if $$$N \mod K == 0$$$ it's $$$N-1$$$, $$$1$$$ otherwise it's $$$N$$$.
Problem $$$B$$$: the answer is the longest increasing(or decreasing) subarray.
Problem $$$C$$$: how many disjoint $$$1$$$ s are there ($$$-1$$$ if the last number is $$$1$$$).
Problem $$$D$$$: if the number of opening brackets isn't the same as the number of closing brackets it's $$$-1$$$. otherwise, if it's a beautiful bracket sequence the answer is $$$1$$$ otherwise $$$2$$$. We can color the biggest beautiful bracket sequence with the color $$$1$$$ and the remaining brackets make a beautiful bracket sequence.
Problem $$$E$$$: We know which players will be eliminated in the first round. Let's say there is a $$$P$$$ number of $$$(-1, -1)$$$ matchup, and $$$Q$$$ number of players we need to eliminate on that round. On round $$$k$$$ the number of ways we can place the players that should be eliminated is $$$(2^{P_k}\cdot Q_k!)$$$. Then, we can assume those players are eliminated on that round and solve the problem for $$$k+1$$$-th round. Thus, we can recursively find the answer.
Problem $$$F$$$: I didn't solve this problem during the contest. I used
multi_set, which I later changed intopriority_queueto get accepted. My time complexity is $$$O(N \log^2 N)$$$. I don't know if the problem setters intended to cut submissions that usedset. The idea of this problem is to find the answer with a binary search. For a chosen value, we check for each element to be the last problem of the Monocarp, and find the maximum number of editorials we can make in that situation. If it's over or equal to $$$k$$$ we can make it in for the chosen value. I still think the time limit for this problem is a little too tight.Overall it was a good contest :)
The problems were very easy till D , it must be somewhat tough at least for C and D.
please start writing div3 contests
I passed F in last two minutes! Hope it won't FST.
Hello. I am from the future. It FSTs.
You are wrong. Here's why.
you are lucky enough!!!
D can u tell what's wrong with my soln first i eliminate all the regular seq from string and colored them with 1 then i reversed remaining and colored them with 2, if finally the stack is not empty i print -1; then did above process again but this time i reversed first then printed min of above 2 processes
nvm , got it, didn't print -1 ,i am an idiot
Seeing even experts getting WA for first time in B is such a relief..
Candidate Master also get WA in problem B
I second this
I got 2 WA for B but 0 WA for A, C, D... what a contest.
i got 3 WA on B...
unrate it please.
Problem B is bad :( Promblem D is easy but I made many stupid mistakes... bad experience.
"How many greedy questions have you prepared for this contest?" Problemsetters: Yes
This was not a good contest for div2. All problems were very easy compared to their expected hardness.
Can anyone please explain why my solution is incorrect?
207239600
https://codeforces.me/contest/1837/submission/207239600
>>><>>><>>><Your approach: [0 1 2 3 2 3 4 5 4 5 6 7 6] best answer: [0 1 2 3 0 1 2 3 0 1 2 3 0]
Was this the easiest div 2D ever in terms of problem rating and solve count?
queue is so long!
maybe change the problemsetters for some time
Can anyone give a counterexample where my code gives a wrong answer?
207246737
What is this: not accepted / accepted
Only difference that the first one may only print out 2s instead of ones, but there is nowhere specified that colors must start with 1...
It is given in the problem statement that we have to print from 1 to k
i wish i could read
Wow, I am little surprised to see the number of submissions of B. Was the solution leaked somewhere ?
There were also more participants than usual in this contest
Hi this is the first time I join in a competition. But I only resolve the first three problems (A, B, and C). Will I get a rating score? Because I saw that my score is still 0 in my profile.
Yes,Wait for some time
Я сегодня впервые участвовал в контесте и с интересом изучаю чужие взломы.
При этом мне показалось, что в некоторых случаях отдельные участники соревнования кое-где у нас порой специально публикуют решения с изъяном от имени клонов и потом их с гордостью взламывают.
Например, четыре успешных взлома задачи А: https://codeforces.me/contest/1837/hacks?verdictName=CHALLENGE_SUCCESSFUL&chosenProblemIndex=A — удивляют схожестью идеи и явным сходством в никах автора решения и взломщика. Или мне только кажется?
Возможно, есть какой-то принятый способ сообщать о подобных хитростях?
А смысл? в таких раундах не дают доп. очки за взломы. А в раундах в которых дают очки за взломы, все разбиты по комнатам.
very high time limit for F
gordan ramsay after giving todays contest.
"My gran could do better!"
F is the most messed up problem I've ever seen. I can't believe it's that easy yet I can't solve :(
In problem B, if I start with the number X initially, if I encounter '<' I increment X else decrement X . Here is the code for it
vi ans; ans.pb(5); ll val = 5; f(i, 0, n) { if (s[i] == '>') { val--; ans.pb(val); } else { val++; ans.pb(val); } } deb(ans); set<ll>st(all(ans)); cout << st.size() << endl;}
Why is this approach wrong?
If the sequence is ">><>>" then
Your answer: $$$[5, 4, 3, 4, 3, 2]$$$
Optimal answer: $$$[5, 4, 3, 5, 4, 3]$$$
I'm still getting the wrong answer when I apply your logic.
That's why I edited it. You have to do it for both '>' and '<'.
someone pls explain how to solve problem F
will i be able to becomes red one day :/
you will be if you cut the suffix. ✧(≖ ◡ ≖✿)
this contest should be unrated because of the problem B.
My approach for Problem F:
Let us say we already have the k elements which are picked out from the original array, we can create a prefix and a suffix sum array and then iterate over the two picking the minimum of max(prefix[i], suffix[i]).
So now all we have to do is to find the k elements, we can find the k smallest elements in the original array and then take the maximum of that array, then check if we can/have to pick more than one occurrences of the max element from the original element, if yes we somehow have to find which occurrences of the max element do we have to pick in order to reach the minimum later on when we calculate the answer, I understand that the position of the max element matters but I cannot figure out how to optimize it in such a way so that it leads to the minimum ans.
even then you will mp fail on testcase n=4,k=3 and a=[2,3,2,4]
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Trash round.
Poor English. It is 'trash' instead of 'trush'
My rating was updated to expert few days ago and today it is showing back to specialist, it has reduced by some points in this contest. Have anyone else faced this?