Привет! В Feb/13/2024 17:35 (Moscow time) начнётся Codeforces Round 925 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи были придуманы и написаны нашей командой: myav, Gornak40, ibraevdmitriy и Vladosiya.
Также большое спасибо:
MikeMirzayanov за помощь с идеями и системы Polygon и Codeforces.
nigus за красное тестирование раунда.
htetgm за фиолетовое тестирование раунда.
natalina, JuicyGrape, lockdown, kotikk за синее тестирование раунда.
RedDreams за бирюзовое тестирование раунда.
the_Incharge, Aurora__, Longqiang за зелёное тестирование раунда.
Всем удачи!
P.S. С наступающим днём святого Валентина!
UPD: Давайте продолжим серию анонсов с фотографией авторов :)
UPD2: Разбор
Wow, you put a lot of effort to make a lot of quality div3. Thanks for a lot good div3 round to help beginner to advances in CP.
Yeahhhh!!! Div 3 Letsssss Gooooo
Div 3 are my favourite. Lots to learn.
the round number and date is wrong please fix
Fixed
speedforces let's go
Thursday, October 12, 2023?
I hope this is my last round before cyan
We at same rating
lol
Thank WHO for red testing 😳
My first unrated Div3 I mog everyone
don't make your gf sad, prepare gift after contest
cp and gf? nah man something doesn't feel right. Just don't touch grass and stay home I guess
отличные фотки, а как насчёт подождать 2 года в очереди, как все остальные?
поплачь хз
I had no idea authors could be so pretty. I'm blushing (,,>﹏<,,)
mmm, why?
I was hoping the authors would see it and feel happy.
You see, not everyone has a valentine (╥﹏╥).
No, I mean why you thought that authors couldn't look pretty. As far as I'm concerned they're all human beings, just like the rest of us
If I became an author, I would be a good counter-example :)
But you are correct. Everyone is beautiful. That's why its great to have pictures of the authors in the announcement.
so sweet post. Happy Valentine's Day. Do spend time with ur loved ones, instead of attending contests
I love CP 😎
I am the one in the button right on Valentine's day :,-)
I don't get it,why are authors making a 'C' with their hand?
May be because Mike also did the same on his picture (to hold the burger)?
It's not the letter "C", it's half a heart (we tried, ahahah) We wish the community a happy Valentine's Day!
Got it,that makes sense,i need to go out and meet some real people.
Thanks for the contest but why y'all throwing up gang signs?
Bro failed to get some contribution XD
Lol, at +116, even 100 upvotes on this comment won't change my contribution at all
congrats on CM performance
Practice and maybe you could too lol.
Bro waited 5 months to post hate comment. :)
Valentine's Day ? Oh man, i am CPer
Happy 46th day of the year then
My first unrated contest
They are so similar
Good person
Maybe he has a rat that makes him code hmm
why are the names of the authors written in reverse
Hopefully my last rated div3
why the solution will be out 5 minutes before the contest ends?
Hope positve delta for all rated participant.
Fells like C
Good luck to everyone.I hope to become expert on this round.
Hope to reach expert again
Disgusting problem F
It's not, F is basically "Detect cycle in a directed graph".
how to represent it as a graph?
Code — 246203312
You basically ignore the first element of each line.
Construct a directed graph based on the other ones and detect if any cycles are present using a topological sort.
If there is a cycle, then "No", else "Yes".
Damn! I was thinking of graph but then I wrote this 246240679 wierd solution which got accepted.
you can do "F" just by making first line as 1, 2, 3, ... n, and these ai changes in next k — 1 lines too.
Then for each line just check order is maintained (i.e. curr element is less than last)
As an edge case: ensure "1" is correct in all.
submission
Got the right idea for F about an hour after the contest started but spent the next hour debugging double-hash. :(
Hope no one tries to hack me after I write this comment. :(
please hint for C
You MUST choose x as the first OR the last element.
three possible ranges you will select from k to n , from 0 to n-k , or from i+k to n-k. k is the index is where there's no more duplicates from the beginning or end from the array, like [1,1,1,2,3,4,5] k is at index were ai is equal 2 , so we can make the range we select [4,7] , same from the back. i+k to n-k is when the duplicated at front is the same from the back . sorry for bad explaining
You can look for the longest segment of equal elements from the start, let's call it a, and the longest segment of equal elements from the end, call that b. Now, there are two cases:
(1)If the first and last elements are equal, you can choose the contiguous segment of elements not in either a or b. (notice, if len(a) + len(b) > n, the answer is zero. Else the answer is n — len(a) — len(b))
(2)If the first and last elements are not equal, you choose the equal element as the element that comes in the longer segment. (notice, the answer in this case is n — max(len(a), len(b)))
i am annoyed i couldn't get F i didn't think it will be cycle detection at all.
Problem D is nice, thanks for the contest. But how to solve F?
I feel like idea of F was simple but the implementation was tedious. Also, loved G!
Any hints for G?
Try reducing this problem to a stars and bars problem Try to think what are the prerequisites if we want to place the 4th block at any place same goes for the 3rd Think which blocks are the limiting factors and which we can take care of irrespective of their quantity Have a Great solve!!
Maybe it's just me, BUT F seemed way easier than both D and E, although didn't spend much time on E after I saw F, which I had just the right idea for. Overall very fun Contest.
Quick hints for all the problems before the Editorial comes out.
A: Just brute force on each index using 3 for loops.
B: As the water can't flow backward, therefore the amount of water in any prefix can only decrease or stay constant.
C: Check if all equal, else count prefix equal length and suffix equal length.
D: What if we store the remainders in pair<int, int>?
E: Replace each number by the count of its trailing zeroes, now play the game greedily.
F: We can easily create the order from the first 2 arrays given (if k = 1, then its YES). Just make sure to handle one edge case [1,2,3,5,4] and [2,1,3,5,4], basically those in which there are 2 possible orders)
G: Pieces 1 and 2 can only appear alternatively, and the pieces 3 and 4 will always fit in the between their occurences. Also, pieces 3 and 4 can be repeated, while 1 and 2 can't. Try fixing Piece 1 or 2 as the first piece in the chain, do you get some general pattern?
Personally, I didn't like coding F, the idea was interesting, but implementing the checks was very irritating. Or maybe I have complicated it. Overall, this set was very interesting!!
Simple way to do F
Yeah this subproblem looks way more easy and familiar, I was just hasty and went with my first thought.
In F, I think the simplest way to code is model it as a graph and use topo sort. I think that makes implementation really easy with template :)
F feels like AtCoder style problem, doesn't it? :)
I think it's more like the first few problems of a regional.
can up please tell what's wrong with this
I did F after constructing the graph and checking if the number of SCC is equal to $$$n$$$:)
F — "Detect cycle in a directed graph."
Submission- 246203312
How to combine pieces in the second test case of problem G (one sample way would be enough, please)?
121212121244 or 121244121212
Hmm, but there are only 2 pieces of type 2 and single piece of type 1:
c = [1 2 5 10]Sorry I misread it as second last test case, for the 2nd tc, here is one,
333332124444444444 or 333332444444444412
Thanks! Now I see why I could not solve the problem :)
I just wanna say thank you for making this contest, I was able to solve till F( can't believe I did this )
I think I have very unique solution for problem D: Problem D Solution
I used modular operations for storing single value in map
I did not get the logic behind your code. int v = mod*a + b ; int fv = mod*fx + fy ; why did you do this?
For pair $$$(a,b)$$$ we interested in pair $$$((x-a)\mod{x}, b)$$$
Code editor is not working, keeps running and no result, makes the whole experience shit. Cant run test cases.
How to solve G: https://chat.openai.com/share/3647110d-401a-4591-9dda-840260a0317d
you just calculating binomial coefficient, how is this related to solving G?
Because the only thing that came to my mind was:
which led me to the formula: $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$, and I didn't realize that it was effectively just comb(i + j, j), so that's what ChatGPT told me.
https://mirror.codeforces.com/contest/1931/submission/246186250
The best solution to hack:)
^-^
Here is how you can choose the next type of element to add in problem G.
Two nice observations:
Hey, which tool did you use to generate such graphs?
https://www.tldraw.com/
When I saw other's solutions,I found the problem E very easy. However,I think F is easier than E because I can get the idea to solve it without thinking.(if you know something about graph)
I was wondering whether this contest gives any rating? I am 401 rated. I have participated and solved 2 problems but haven't got any rating. Can anyone tell me if i'll get any rating?
ratings will be updated after the hacking phase and 100% system testings.
Does the following work for F?
Rearranging any of the participants except the last one cannot change the last participant from the permutation. Therefore, we can find the real permutation by checking which one has the last participant only once. Now, that we have obtained the real permutation, we can compare all of the
kinputs to the real one and check.This doesn't work when
k == 2but in that case we can simply check subsequences ignoring the first two numbers.Better Idea:
Simply Ignore the first Position of Every observation. Take an edge pointing from v[i] to v[i+1] (1 <= i <= n-2) for Every participant observation.
Check for the cycle in the graph, If the cycle exists then NO else YES.
How to check if a cycle exists? I tried doing it using DFS but it exceeded the time limit.
246185460
check this blog detect cycle in directed graph
Thank you!
TLE coz of MAX maybe, You are unnecessarily assigning 2e5+7 values to the array, even when N = 1.
Just imagine for the test case where t = 10^4 and N for each case belongs to {1,2,3,4,......2e5}, even if k = 1.
As this test case fits under the given constraints, You will be doing 2e5*(1e5)/2 roughly around 1e10. That's y.
I think so, I can be wrong.
Yeah, I think that was the problem. I just resubmitted resetting only n values and it got AC. Just missed it during the contest :(
246262272 Maybe hashing was unnecessary, also who knows if this might get hacked.
Loved the beautiful Stars and Bars problem (G) Got to the solution but didn't submit earlier as I was unsure if it would be rated for me Nonetheless Here's my solution in case any one wants a reference: https://mirror.codeforces.com/contest/1931/submission/246256160 :)
As an expert I failed D: TLE on test 9. Here is my code: 246198274. Could anyone help me with debugging? I think this is O(nlogn).
Edit: This is O(y). Forget it
How to solve E? Didn't get any idea at all :(
1) Ans "yes" if number of digits in the last number >= m + 1. Anna in each step tries to reverse number with maximum zeroes on the end. Sasha in each step does concatenation number with maximum zeroes on the end with any number without zeroes on the end (number without zeroes on the end is guaranteed to exist, since it either exists initially, or Anna will make it her first move)
it is optimal for both of them to the choose the numbers which have most no. of zeros at the end
multiset<pair<trailing_zeroes, digits>>and just model a gameI think you should reduce the time limit of this problem. this submission -> https://mirror.codeforces.com/contest/1931/submission/246247517 runs in 1 second. this submission should not get AC because # of testcase is 10000 and this submission is executing a for loop of 200005 every test case. that's more than 2e9 operations.
!What is this submission code
is he know the testcase?
it's hacked
Yes but how did he AC in the first place?
testcases were week
Oh no, we didn't make tests with all possible t value! What a weak testset!
After successfully wasting 1.5 hour on B i smashed binary search in B
can someone hack it?
246247536
why would you even think of binary search . you already know that the good value is sum/n . that's the only way you can make tha array the same
Video Editorial for problem B (Audio : Hindi) TUTORIAL VIDEO LINK
Thanks to the authors for an interesting div 3 without clay and with tasks that are fun to solve. After this div and the Cognitive Technologies Olympiad, I realized that the name Gornak in the list of authors => good Olympiad/div.
Can G be solved using inclusion exclusion ?
May I ask why I passed 3 questions but didn't receive a rating in the end? Or who should I seek help from? I really want this rating, thank you.
Rating appears after 1 to 24 hours from the end of a contest, and if there is a hacking phase, like this contest, then it may last up to 24 hours or less.
in Problem E , i wrote code which was absolutely right, the only thing i missed was, if number>=10^m then number of digits should be >=(m+1) not >=m (it was pretty close :) )
I made the same mistake
I got a TLE on D in System Testing , it's just getting worse
How to solve Problem G?
Stars and bars
wow that was very cool
really enjoyed this contest, particularly problem D. start to see some common patterns on int-mod problem..
What is a int-mod problem?
problem which play around with mod and remainder, usually have tag like 'number theory' 'math'. just see how similar is solution to 245923071 and 1931D - Divisible Pairs problem statement.
my respect to Aleksander Gornak
I was getting runtime error (STATUS_ACCESS_VIOLATION) in E, during contest , but after contest when i submitted same solution it got accepted . runtime error during contest code link.
accepted code after contest. Thanks
The problem is this for loop here:
for(ll i=vect.size()-1;i>=0;i-=2).In C++, the return type of
std::vector::sizeis an unsigned integer. Whenvectis empty, thenvect.size() - 1becomes0 - 1which then overflows toUINT_MAX. This causes out of bounds error which is why your program got runtime error. (It seems that this is changed in C++20, which is why your other code got accepted)To fix this, you just have to convert
vect.size()into any signed integer type. For examplefor(ll i=(ll)vect.size()-1;i>=0;i-=2). New codeVideo explanation of Problem G (Chinese)
One of the best rounds I've ever participated. Thanks to all the writers and testers for offering us such a round.
The best div3 round contest I've ever participated!Thank you!
when will the rating come out?
you need to wait that the system testing ends first (is around 80% right now). after that eventually the rating will be updated.
Oh,Thank you.This is my first time to attend CF.(I find out my G turned out to WA,It used to be AC)
First CF got G AC,congratulations!
I'm waiting the rating, too.
Thank you for your encourages!
Can anyone tell me where have I made a mistake in these two codes? Only difference I have made from my side is making the capital N,small n? Basically I had initialised all visited array elements to zero in reset function. Thankyou in advance.
1st submission 246198873
2nd submission 246233252
I don't understand why exactly gives you another answer (actually I'm more curious of how didn't get you RTE hahaha weird stuff)
But the reason why the change works is because in the WA submission, you have the following code:
and
fris#define fr(i,a,b) for(int (i) = (a); i <= (b); (i)++)So, the cycle in
reset()will access to the position $$$N$$$. But the arraysg,visandvis1are of size $$$N$$$, I change you code putting a -1 and now it gets TLE, that makes a lot of sense, because $$$t = 10^4$$$ and $$$N=2e5+69$$$, so you will do around of $$$2\cdot 10^9$$$ operations just to reset.ok got it....thankyou for your help :)
In Question 4 this code exceeds time limit on test case 33 cant understand why its o(n) approach can someone please help me?
include<bits/stdc++.h>
using namespace std;
define ll long long
int main() {
int t; cin >> t; while(t--) { ll n, x, y; cin >> n >> x >> y; unordered_map<ll, ll> dp; ll a[n]; ll ans = 0; for(int i = 0; i < n; i++) { cin >> a[i]; ll f = (x - a[i] % x) % x; ll l = a[i] % y; ans += dp[f*y+l]; dp[(a[i] % x)*y+a[i] % y] += 1; } cout << ans << '\n'; } return 0;}
Worst case time complexity of unordered map is o(n) while normal map is of o(logn) that's why it is giving Tle. I got AC with your solution by just changing unordered map to normal map
But may I ask why I still haven't received a rating? It should have been a long time since the hack phase ended. I really want the rating for div3 this time, thanks.
You must wait for some more hours after the system test. Codeforces needs time to calculate rating changes. Just chill
Why there is no rating change? My rating is less than 1600
It takes a while after the system test for codeforces to remove cheaters and recalculate the rating changes.
By the way, have we met somehow before?
can anyone just tell me which are valid patterns in G? I can't find any for 1 2 5 10
One of the valid sequences is:
2 4 4 4 4 4 4 4 4 4 4 1 3 3 3 3 3 2
Thank you... I didn’t notice self loops.
when it will be rated?
I am new to code forces this is my first contest, I have solved two questions still didn't get any rating. Did I miss anything?
Don't worry too much, it will be updated soon . Within an hour, I think .
Just wait bro ... A Div 3 contest usually takes more than 24 hours to give you rating change ...
24 hours after open hack session?
No,it should be after hacking by 2 or 3 hours
okay :(
Give me my rating pls((
its taking forever
Finally blue. Was a great experience.
Same I am very happy :)