Привет, Codeforces!
Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со стипендиями JetBrains. Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Любопытно? Ознакомьтесь с учебной программой прямо сейчас. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно!
В 17.03.2025 17:35 (Московское время) состоится Educational Codeforces Round 176 (Rated for Div. 2).
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков и Александр fcspartakm Фролов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Данный раунд частично пересекается по задачам с Внутривузовской олимпиадой Саратовского ГУ. Если вы участвовали в этом соревновании, то воздержитесь от участия в раунде.
Удачи в раунде! Успешных решений!
Наши друзья из Neapolis University Pafos также хотят передать вам сообщение:
Прием на бакалавриат по программе "Компьютерные науки и искусственный интеллект" в Neapolis University Pafos открыт!
JetBrains Foundation поддерживает эту программу бакалавриата и предоставляет 15 полных стипендий для самых талантливых абитуриентов. Стипендия покрывает стоимость обучения, проживание, медицинскую страховку, визовые сборы и карманные деньги (300 евро в месяц).
Первая волна набора:
- Срок подачи заявок – до 23 апреля 2025 года
- Вступительный тест – 27 апреля 2025 года
Hope we'll find a variety of topics in this round rather than only maths or bitmasking type problems.
Hope that we'll find a variety of topics in this round rather than only maths or bitmasking type problems.
I wish we could have a
fair and enjoyable round! No cheating, just honest participation!
Edit : Why does it always happen when I wish for something not to?
lets see if -100+ is possible or not
score distribution?
There is no score distribution in an educational round.
meaning?
Educational rounds follow extended ICPC rules. You get 1 point for each problem solved, and there is a 10-minute penalty for each wrong submission before a correct one.
wont we get any elo?
We will.
I got 41 penalty points does that mean i loose elo?
Check out this blog : Open Codeforces Rating System [updated on October 2015]
1-1-1-1-1-1
Sacrificed my sleep for +9 in last div 2 hoping to get it in this round
Hope to enjoy this round without any technical issues. Because, the calendar has a less number of rated scheduled contests this month.
Why adamant about not keeping educational rounds on saturday sundays
watch me win in this contest...
Why this post has less up votes??
I really hope enjoy this round without the server acting unstable for no reason
best of luck coders!
bruh my alarm didn't ring
I literally registered for this contest seeing that one of my friend has already solved problem A in 2 minutes and started this contest like 5 minute late
your pfp was me 30 minutes ago
lol but my pfp is this guy for like 2 years now I love this virtual cat fr
Yesss, finally, I will be back to CYAN today, inshaAllah! Scored 'C' just 13 minutes before the ending! It took me 3 unsuccessful submissions and a long time to realize that 'B' was that much easy!
what was the approach for 3rd bro i tried but failed
Bro, we need to choose a pair every time ensuring their "SUM" is at least 'N'. When this "AT LEAST" thing come to your mind, this is something "BINARY SEARCH". At the same time, you need to make it optimize that how many such index exists for the current index that if you form a pair their "SUM" will be at least 'N'. Then, when this "HOW MANY THING" come to your mind you need to sort the given array and use "PREFIX/ POSTFIX" sum array to optimize the counting approach using "BINARY SEARCH".
One important point, if the value of an index is 'N', then make it 'N-1' before processing. Because, we need to make 'N' by taking at least 2 indices.
Now, you can see my submission to align this approach in a better way. (I named the array preSum. It's actually postSum.)
actually i tried but can't figure out what's wrong in this
Hopefully, next time bro. Don't give up.
wtf was B
Real
can't agree no more!
Solve for k=1 separately
How to solve E
P.S. C << B
any hint to solve b?
handle k is equal to 1 case explicitly otherwise it's just summation of maximum k+1 elements from the array
Oh wow
it was tough to figure really
intuition ? excuse me?
it is pretty simple like if k==1 you can take one element which can be any and you have to take at least one last end element you can take both as well otherwise for k is greater than one try to make segments you will always be able to cover all the k+1 greater elements
If $$$k > 1$$$, consider the array's largest $$$k + 1$$$ elements : $$$G = g_1, g_2, ..., g_{k + 1}$$$.
Let the $$$g_i$$$ that appears first in the array (smallest index in $$$a$$$) be $$$g'$$$ and the one that appears the last be $$$g"$$$. Now we can choose the last value as any $$$g_i$$$ between $$$g'$$$ and $$$g"$$$ and initial $$$k$$$ values as the remaining values in $$$G$$$. Then we can color the chosen ones as red initially and start moving inwards from $$$g'$$$ and $$$g"$$$ and reach all $$$k + 1$$$ elements $$$g_i$$$ and can finish at any one of them, so that the last value that is added is also one of the $$$g_i$$$. Thus sum of values of $$$\sum_{i = 1}^{i = k + 1} g_i$$$
If $$$k == 1$$$ you have only two elements, if you choose them to be the largest two, you cannot always color such that the last element is one of them, eg. [1, 5, 6, 2]. In those cases answer is $$$max(a_{max} + a[0], a_{max} + a[n - 1])$$$
If $$$k == 1$$$ and max element is at one of the ends, answer is $$$a[0] + a[1]$$$ if a is sorted in descending order
omg, I'm gonna kill myself. I thought about that, but I didn't consider k = 1, and get wa
did you try c?
yeah. Actually C was easier than B
can you tell me what is wrong in this code? i am confused
I think you missed one thing. Consider this test case: a = [6,6] n = 5
You considered cases where all fences are colored with the same color (which you shouldn't)
Ok I think I missed exactly 2 colors thing:(
v[i] = min(v[i], n-1); do this and it will work
Although this might be the solution, my approach was slightly different. To make the i-th element (i > 0 && i < n — 1) the final cell to be painted blue, there must be at least one blue cell to its left and one blue cell to its right. For i = 0 and i = n — 1, the answer is just a[i] + sum of k maximum numbers in the remaining array.
how ? if n=7 and k=4 array=7 1 3 1 10 12 14 ans is 44 or 46 ?
It's 46 choose 4 elements as 7 10 12 14 and consider last element as 3
but 3 is not neighbour of any blue element
Like consider making 1 blur first which is adjacent to 7 then make the right side elements of 3 blue then make 3 blue and that way 3 is last element
WHAT? i thought there some kind of 2d dp...
why cant I submit solution now that contest is over
is there any smarter way of doing 2F without some cosmic-tier binary search/sweep line jank
I think divide and conquer works.
For each $$$i$$$, we find optimal $$$j$$$. Let $$$solve(l,r,a,b)$$$ mean that we are solving $$$l...r$$$ and their optimal $$$j$$$ are in $$$[a,b]$$$. Then, find the optimal $$$x$$$ for the index $$$mid$$$ and call $$$solve(l,mid-1,a,x)$$$ and $$$solve(mid+1,r,x,b)$$$.
Actually the sweep line is not that complicated, you just have to notice that the best endpoints are $$$l,r$$$ such that $$$a[l]$$$ is the unique minimum of its prefix and $$$a[r]$$$ is the unique maximum of its suffix (in this problem it really helps visualizing the array as points in 2D).
And now the candidates for $$$l$$$ and $$$r$$$ are decreasing sequences, because of that, for each element, the endpoints that it appears in are a range of each sequence (i.e. the 2D conditions are now easier 1D conditions).
And then you do the sweep line of the biggest range intersection of the second sequence given that only pairs of ranges that contain me in the first sequence are alive.
Panicforces.
WA multiple times, I'm cooked.
Could you please give me an explaination why problem B can be solved in $$$\mathcal O(n\log n)$$$ easily but $$$n\le 5000$$$?
two pointers on 2D prefsums
imo this is much harder than what solution I wanted to express...
ofc, but this implementation is not for div2b i think
Misdirection
is this really allowed in pB? I have just known that pA could (and should) be have smaller constraints.
there are two cases
when
k=1
: you will take any element, and take max of first and last if available.Logic: As you have can only paint in one direction, you can only take max of first or last element
when
k>1
: you will just have to take sum of k+1 max elements in array!Logic: Fix range to minimum and maximum index of k+1 max elements
I solved it in O(N * K) because it was the only solution I could think of. I think they keep this time limit because it's Div2 B.
Is "D" Bruteforce?
same question, I thought of bf but have no time to implement.
Yes, try every possible subset for $$$x$$$ and $$$y$$$ which are disjoint and reduces $$$x$$$ and $$$y$$$ to the same value.
why does my D solution is wrong recursive dp + bits 311139765
Good C and D :)
The only unpleasant part is B, the too many "Announcement" are misleading and interferin :(
And hope the samples can be stronger.
why is time limit exceeding in my solution ????
vector ct(200000 + 1, 0), pfx(200000 + 1, 0);
You create two vectors, ct and pfx every time. If operations iterate over these vectors t times, the total number of operations can reach around 4e9 ((2e5 + 2e5) * 1e4), which can easily exceed the time limit.
Is there a reason why all of these submissions are the same for problem E? Either someone has several alts, or serious cheating is happening...
22R01A05B8 kushwahaarpit360123 vinay_m18
with several more (usually unrated or newbies).
Livestream on YT and link to telegram group with solutions A-E :/
sadly there exist multiple telegram groups sharing solutions to rounds, most of these cheaters just copy the code from these groups
ALL leaked solution :> (src -yt)
... ~~~~~
~~~~~
...
...
Rajkumar_24M11MC100 this cheater has same codes, nigga is so dumb didnt even think for a second before copy pasting the code lol. also look at his prev contests he has 0/1 submissions.
Problem B be like:
"Your first solution must be the sum of first $$$k+1$$$ maximum elements and you shall figure out the correct solution afterwards when you've already got a wrong submission"
Good contest, quite interesting problems.
Overall, not so bad of an Edu round. B was very educational lol.
How to solve B problem? IDEA please
Try to upper bound an answer, then prove that the bound is exact (except one corner case).
311145412
why am I getting WA What's wrong in my code?
can u pls help me...
try to solve for k = 1 and for k >= 2 separately
311145412
my submission. But got WA
you are missing a case for k = 1, when corner values are maximum. example: {5, 1, 2, 3, 4} n = 5, k = 1.
Also you are sorting before storing first and last element.
Thank you, sir.. a lot of corner case. but finally learned and solved it with your help..
D doesn't need any DP. I solved D with DFS, I try to guess the answer never greater than 100000. And it worked! :) :) :)
DFS is dp actually
No, I just used DFS to run out a answer map in home and submit. $$$O(T\times\log^2_2\max(x,y))$$$.
Check my code to see my strange solution :)
Is this based on the fact that the first 15 bits are enough since sum of first 15 nat nums is 120 = 60 * 2 ?
Edit :- Ok, that would tle
can you tell how you solved C
C 2 pointer trap can be avoided with binary search. I was lucky to choose BS instead of 2 pointer (for real)
there is nothing wrong with 3d dp . if you look other submissions , from msbs , why to only have equal reductions . That is underfit , u may even not be able to make things equal ofc excluding( u can make both as zeros which is not optimal alwys)
Wrongly interpreted my bad
BTW , you were very close .
I've just fixed my dp. Now it TLs lol, so I should probably think of another approach
Ohh overflow tle?
Daamn, I didn't think about precalculating. In this problem, it is a must. Also, I couldn't figure the error about properly computing cost of making both numbers 0 during the contest.
Indeed, an educational content here.
if we have to make x and y equal and they are not zero when made equal , msb1 , msb2 as to go to some common msb (reductions are msb1 — msb , msb2 — msb). but when they are zero that they do not have to be some common msb like 2^(-1) or 2^(-2) . one can have msb of 2^(-1) x is 0 , other can have 2^(-2) y is 0 .
e.g. 2 3
such a bullshit B
Top 7 all from Japan :D
dumbest contest ive ever participated in. gl CM :(
Such a bullshit B
I really liked B tho
maybe I'm picking a side here because this contest is my best one yet
I tried solving problem D by finding the longest common prefix in the binary representation of x and y. This helped me determine the highest power of 2^k that divides each of them, which I called d1 and d2. Then, I used a DP approach with a state dp[d1][d2][60], where I tried to form two disjoint sets contributing to the smallest cost. However, I’m getting WA on test 2. Can anyone help me figure out the issue? Thanks!
Try:
1
17 16
And if you fixed that one and still didn't pass (as I did) try:
8 160
30
CornerCaseForces
I am so dumb I should leave CP ATP
ALL leaked solution :> (src -yt)
... ~~~~~
~~~~~
...
...
Screencast with commentary
The problem C's testcase maybe so water
while there is at least one red element, you have to select any red element with a blue neighbor and make it blue.
should have made "any red element" bold
i request awoo and coordinators to please highlight/bold important informations in problem statements for any upcoming contests
nice round i was 1 line from getting ac on B but its great to make sure that my code works with the corner cases next time
It's really really bad EDU, A is very bad, B > C and B's first test not a useful test. Make a good problem or don't make but give a useful test case LOL, B's test case always pass !!
I understand that B could be trivial, but how is A bad?
A is too much straightforward, in my opinion. We don't see this much straightforward As anymore. That's why I guess
A is not like div2As, but I solved it easily :) but fr it's only implementation I think, no need to think :(
any hint for $$$D$$$?
Think in bit and optimised with dp
the closest to returning to blue, if I could realize x and y can shift same number in D and didn't write continue to avoid it
Please someone tell me how to solve c in a simple way. Please....
Look at my solution. You know that you only need to pick two colors and paint the planks such that starting few planks have same color of first type, while the rest have the same color of second type. Now, fix the number of planks having the type of first color and then check for the possible number of ways to select colors for the second type to paint rest of the planks. Now, suppose that you can color i planks with color-1 and j planks with color-2. Now, it's only possible when
a[color-1] >= i
anda[color-2] >= j
, which is the number of colors which can color at least i and at least j planks, respectively. Hence, total number of ways will be (number of colors having a[x] >= i) * (number of colors having a[x] >= j). But doing so, you're taking such indices for which color-1 and color-2 are same, so you need to subtract such cases. Just visualize it, the number of such cases will be the minimum of (number of colors having a[x] >= i, number of colors having a[x] >= j).bro, you have the best and the simplest solution I have seen so far. even the o3mini has complex solution which was written by all of my friends !
Essentially, you want $$$\sum_{l = 1}^{N - 1} c(l)$$$ where $$$c(l)$$$ is the number of paint combinations where the length of first paint's continuous colored planks is $$$l$$$
Let the number of paints with capacity $$$ \geq k$$$ be $$$g(k)$$$. We can pre-compute $$$g_i$$$ for $$$i = 1$$$ to $$$n$$$ in $$$O(m)$$$ time by storing frequencies of each paint
Now it is easy to calculate $$$c(l)$$$ if you know number of paints with capacity $$$ \geq l$$$ and number of paints with capacity $$$\geq n - l$$$. Let the smaller quantity out of $$$l$$$ and $$$n - l$$$ be $$$l$$$. Then,
$$$c(l) = g(n - l) * (g(l) - 1)$$$, i.e. choose any paint with capacity $$$\geq n - l$$$ and choose any other paint with capacity $$$\geq l$$$ except the paint chosen for $$$n - l$$$ length
I don't seem to properly understand C. As a trivial/slow solution, I would apply the colors to the fence s.t. all of color i is on the left, and all of color j in on the right, and do this for all i and j. This only works if a[i] + a[j] >= n, and if so there should be a[i] + a[j] — n + 1 ways to do this, as seen in the sample testcases. We can express this as the following line of python:
res = sum(a + b - n + 1 for i, a in enumerate(l) for j, b in enumerate(l) if i != j and a + b >= n)
But even this slow solution fails on many testcases in test 2 by printing a too high answer, for example this one:
l = [5, 6, 3, 4, 3, 7, 7, 4]
gives the answer 210, but the actual answer from the judge is 182. Can someone help me understand where my error is?
Edit: n = 7 in the example
what if ai = n? is your formula correct?
Ahh, that's probably the problem, thank you
For B***
Sum of first K + 1 elements is correct but,
(what if k == 1, suppose the maximum is at any index != 0 and != n — 1 then we will always take the boundary elements of array, aka the last blue box)
:)
Are you guys able to see the standings
Yes
DPforces
i think b is pretty hard for b of div2
Can someone please explain D, without magically defining DP.
Never felt so stupid solving B... Implemented maps, vector of pairs, custom sorts...just to be solved by k=1 explicit case.
My Submission
Can anyone tell my why my submission gave WA? I sorted the input then for each index i, I tried to find index
ind
such that for everyj
greater thanind
,arr_i + arr_j >= n
. Then I used prefix sum to find the sum between[a_ind, a_(m-1)]
and used remaining indexes,r = m-ind
and used theans
line. Basically useda_i + a_j - n + 1
for every pair fromind
to the end. Ignore the cout lines, I used them to try to debug but couldn't find any. Thank you in advance.Update: I found the problem. I didn't consider the case where
a_i = n
and also there was a signed overflow in the ans line.Here is a different approach for C no problem https://codeforces.me/contest/2075/submission/311149194