Hello Codeforces!
Contest 2050 and Codeforces Round 718 (Div. 1 + Div. 2) will take place on Apr/23/2021 17:35 (Moscow time). It's rated for everyone! The score distribution is 500--1250--1500--1750--2500--3000--3000--4000. You will have 2 hours and 45 minutes to solve 8 problems.
Contest 2050 is initiated by volunteers of the 2050 Conference. You can find out what is 2050 at the end of this blog.
The contest is prepared by
and we'd like to thank
- KAN, budalnik for their excellent coordination.
- absi2011, chitanda, Gromah, Itst, Retired_cherry, Aaeria, HIS_GRACE, A.K.E.E., namanbansal013, Rewinding, yaoR, sshwyR, chenjb for testing the round.
- MikeMirzayanov for the great codeforces and polygon platforms.
See you on Friday and good luck!
We have the following introductory message by the 2050 volunteers:
2050 aims to equip young people to take action and to become volunteers. Every 'last weekend' of Apr, together with the youth, we celebrate the technology at Yunqi Town, China. 2050 is a volunteer-only, not-for-profit unconference.
"Most of the conferences in China are held for those who are already successful in their careers, but none targets young people. 2050 wants to fill the gap, giving Chinese youth a stage to make their own voices heard and maximize their energy and talent," said Dr. Wang Jian.
What to expect at 2050?
At 2050, we call it containers. There are 10 containers: 2050 Youth; Migratory Bird Program; Game On; Mindnet; Youth Stage; Starry Night Camping; Everything Grows; Explorer Space; New Gen Forum; Youth Reunion.
Special arrangement of this year
This year, because of the pandemic and travel restriction, many friends from overseas cannot join us in Hangzhou. This however, cannot stop us from connecting with each other. 2050 will be connecting with 100 cities, to dial in volunteers who cannot join us onsite.
The road to championship @ new gen forum
Algorithms and programming are their pleasures of life. With the belief of victory, they defeated the most powerful opponents. They worked hard to explore the boundaries of human intelligence on the road to the ultimate. We invite the top competitive programming players around the world to share their journeys on Saturday at 23:00~24:00 (UTC+8). If you are interested, please message littlelittlehorse.
Find out more at https://2050.org.cn/en/.
UPD. Score distribution 500--1250--1500--1750--2500--3000--3000--4000
UPD Congratulations to the winners
Editorial
Should we expect 10 problems and there name mentioned above as containers? Also nice to see Retired_MiFaFaOvO after so many days
me too
Looking forward to become a volunteer at 2050 conference virtually : )
haha nice idea
Enjoying the alternate day contests!
The next contest is in a week. Sad
I think there will be a third division contest before educational round. It's usually been like this.
We have already had a "Div-3" contest on 10th April. So, the possibility is quite negligible.I mean, 2 "Div-3" contest in one month-it will not happen so far I think.
sad plus one
it's really great when such organizations pay attention to codeforces, and the codeforces community pays attention to them accordingly!
honored to participate in this round! have fun!
OMG! Chinese Round, I'm so excited!
Edit: Why the downvotes?
you deserve it
Now you deserve it.
I knew it :p
I heard Chinese rounds are generally difficult Is that true?? please correct me if i am wrong
Don't know about difficulty, but they can teach you a lot of stuff : ) Chinese informatics culture is really advanced and highly competitive.....at least I feel so.
Nice.. Thank You;)
Notice the USUAL Timing !!!
Length of the contest is not mentioned
Wait for score distribution .
It is. It's 2h 45m! Check the contests section
Good luck guys :) , hope every one is blessed with AC's and good rating (positive) changes
Do you know that's not possible (that everyone gets a positive rating change)?
Instead of finding math in this, wish you luck for the contest bro Be Positive : )
Thanks! Good luck to you too!
As a tester, I have to say it's a great round with interesting problems. Good luck and have fun!
* u p v o t e s *
ok
Good Luck everyone!!!
"Migratory Bird Program"
Geese!?!?! You brought Waterloo geese to Hangzhou?!? (last I heard, geese are still a pest in the UK, after a bunch were shipped over as gifts for the Queen's Golden Jubilee...)
What's up with the Friday Div 1s lately?
can we expect that the starting problems will be of div 2 level? thanks!
Then what do you think div1 + div2 means?
div 3
i mean ...
lol, you are funny!
Obviously
I was just confirming, never gave such a contest before. :)
I think the first and the second problem will be like Div 2 A and Div 2 B
WLS!! DLS!!
I am going to face Div1 + Div2 Round first time. Can somebody please send link of past contest of this type? This will help me in understanding difficulty of problems in it and practicing them.
Thankyou!
It's more like merge the problems of both division.
Past contests: Codeforces Global Rounds
Thankyou Sir. I will surely check it.
Codeforces Round 621 (Div. 1 + Div. 2)
As a non-tester I can't confirm that the problem statements are interesting because I haven't seen them yet.
Schrodinger's problems
A new chinese round! I am so excited
The length is 2:45, that means 15 minutes shorter than usual global round. It seems it will be hard!
Isn't the global rounds duration 3 hours? Upd : now it makes sense
a new chinese round!
I hope it will be successfully.
what about score distribution ?
Are Chinese Round Pretests as strong as their viruses??!
Are blue coders' contributions as bad as their ratings??!
Codeforces is for practice, not for political defamation
Yaa, it was just a joke but it seems like some people got offended!!
Obviously, you can't insult anyone's motherland
The joke is not funny actually.
Are your words as awful as your ratings??!
[DELETED]
Hope the contest will be held successfully!
How jqdai0815 not in top list rated users?!!
[Retired] MiFaFaOvO
he didn't participate in the rounds for more than six months
He's unactive participating in contests.
Scoring distribution?
There is a noticable difference between problem "A"(500) and "B"(1250).It will create a huge effect on the standings.
There is. A you will solve 15 mins before contest ends with 30 negative attempts and B you won't lol
Good luck everyone!! Hope I will reach expert today :)
congarts Bro
All the best :)
Hope this contest bring +ve rating change. Best of Luck to everyone.
i feel there could be 1 more problem between 1000- 1500 in this contest.
Why is 2050 called 2050?
Bcoz it's 2050 !!
Rating has taken a major dip. Hopefully, I will be able to recover this round.
good luck bro!!!
your submission heatmap is quite an inspiration. even I used to solve a lot of problems last year in quarantine but it is nowhere close to yours.
reminding everyone to drink water during the contest and stay hydrated : )
i remember a similar page on insta, reminding everyone to stop slouching while reading the comments of a post xd.
My Only Dream In Life Is To Reach Pupil :)
have a bigger dream and you will
I showed this comment to my cat its now a tiger.
O_o
Guess people can have an early sleep after solving D.
GridForces
Nice round!
DEBUGS !!! kill me
Implementationforces
I also felt so after wasting a lot of time on B but realised later That you can implement it without much efforts.
I think very poor description for Problem C-Fillomino 2.
yes wording should have been better
Passed all pretests of D. Only 3 Minutes Left !!!
Explanation of C and Input of D is Tricky to Understand.
Please check this submission of C
https://codeforces.me/contest/1517/submission/114039804
How to use DP or optimize it ?
I did it using a version of DFS. Start visiting nodes from diagonal element. Continue visiting to the left node and push it to stack. When left is not feasible start visiting all the down elements
Oh Thanks Feeling really bad that couldn't get this greedy approach during the contest :(
what was wrong in these solutions can anybody tell me
113994955 and 113989915
LongReadForces... Why would write such confusing statements???? Did too much math and don't know how to speak like human anymore?
LongRead and LongCode forces.
How to solve E?
How to solve D
First of all k needs to be even, else you can't come back to the original position. Consider a 3D dp -> $$$dp[iter][i][j]$$$ , where $$$dp[iter][i][j]$$$ represents the minimum cost to reach $$$(i,j)$$$ after $$$iter$$$ steps. Now, it can be built bottom up.
You can perform this for $$$k/2$$$ steps (The path can be going on this $$$k/2$$$ step path twice). and cost for each would be $$$2*dp[k/2][i][j]$$$ .
114025728
In the above solution, you can optimize
I think the English problem statements were not very clear.
Does anyone know a test case for problem C which will give answer -1
Answer is never -1
No
the wordings were difficult enough why make it a trick question then xd
In fact ,many problems use such words ...
there's none of it
In F, can any of the volunteers be the centre?
Holy shit I forgot to mod the answer in E....I feel so stupid rn ugh. The answer is around O(N^2) at most anyways, right? Why was mod even required?
Right. I think for not giving hint.
if there is no mod, answer will be atmost O(n^3).
The matrix inputs are a bit confusing :/
I would like to report the user deepanshupathak03 . During the contest he uploaded a video of the solution to the first problem . Link. In the video in the upper right corner you can clearly see his user name
How did you find it? Did you search for the problem during contest? ;)
No after the contest I was searching for video solutions.That's when I found it. Also you can see thatI submitted the solution to A before the video was released.
Annoying Forces
Solved 4 problems, logic was easy, but were difficult to implement. I wasn't expecting this from 2050 :(
Problem C be like
Tell that to the guys that kept down unless overtaking :P
We somehow survived 2020, and you think about 2050, isn't it too early to make a guess
Is it possible to solve D using priority queue ??
Without dp the complexity would be exponential afaik.
GridForces :))
-83 hack attempt -_- Maybe it's the maximum failed attempt in one contest.
Not to state the obvious or anything but have you seen the attempted ‘hacks’? The guy was very clearly doing it on purpose to sabotage his own rating. Don’t ask me why something would do that — I have no idea — but that’s what he was doing.
I have no idea how my C passed, just kept greedily filling down left down....maybe it wont survive the system tests.
it is correct solution..
What a wonderful contest!! Btw how to solve D? I had some $$$O(n^2*k^2)$$$ idea but couldn't implement due to less time.
DP, Let
dp[i][j][k]be the min-cost to travel exact $$$k$$$ step from point $$$(i, j)$$$. time complex: $$$O(n^2 * k)$$$ since you have at most four directions to go.Well,... how to calculate dp[i][j][k]?
I mean, it is min of all dp[i][j][k-1] cells plus the costs of entering the adjacent cells of it. How to maintain them?
You can see my implement 114022406, I use
std::vector<std::tuple<int, int, int>> dir[N][N];anddir[i][j][d] = {x, xi, xj}means cell $$$(i, j)$$$ is connected with cell $$$(xi, xj)$$$ with cost x.Ah...I think I got it. It is not the min of all cells whos start k-1 dist away and ending in i,j.
It is instead the paths of length k-1 from the 4 adjacent cells.
It would probably have TLEd. You can do it with $$$O(nmk)$$$ DP.
Well the logic I got - Vertices at distance x from (i,j) gives a diamond shaped closed path. For vertex at distance x, you can use dp from the neighbor vertices at distance x-1. Giving a solution of O(k^2). But couldn't implement due to less time
I know how to deal E in $$$O(n)$$$, but my poor implement said no.
the statement was difficult and annoying
I just spent a lot of time trying to find where the error was for my submission of B , (I should have gone to C a lot earlier lesson learnt.) please help find it submission. My logic was to find the minimum lengths of all paths and distribute the top m to m athletes , (in the row where they are initially present) ,the remaining need not be changed.
can someone give hint for B
can minimum m values of all the n*m values be tiredness of m runners ?
we know for sure that if above is possible, there is no better case.
I solved D but two bugs ruined my time. I learned two things:
1st : When you copy a code that is to be duplicated for multiple times for some identical cases, check twice whether you are missing any change that is done to the copied code.
2nd : When you are going to set a variable for a holding a minimum value, initialize it to the (maximum_value + 1) that it can take.
I know this are very basic and natural things, but this things ruined me over. Always basic and natural things are not visible to eyes.
Anyways good contest. Kudos to the team.
How does the dp work in D? I was not able to find it.
Judging from the other solutions, it seems that I overcomplicated it. But here was my thought process:
The entire grid = -1 if k is odd (because for every step forward we take from a cell, in order to eventually come back we need a corresponding step backwards, and so this forces k to be even in order to be able to do this).
Otherwise, You can recognize that the answer is always some "cycle" from the starting position (AKA, we start from a cell (i,j) to some other cell (i', j'), and we come backwards. We repeat this until we get K steps exactly). I think this is optimal because the path towards any cell and back has to be the same path, otherwise there was a better one and we could've taken that one forward and back. This gives the implication that we only care about the min cost of "cycles" of lengths that are divisors of k / 2 (apparently it is sufficient to check for k / 2, but i didn't make this observation EDIT: I am pretty sure this is the case since if any cycle of a smaller length was better, then it would have been included in paths of length k / 2, since they must divide it).
So the answer for any cell is min(dp[i][j][d] * (k / d)) where d is some divisor of k / 2 and the dp[i][j][d] is the min cost of a path that is d away from (i, j). You can compute this by the transition that we either go left, down, right, up from any cell and this is a state forward.
pseudo transition: dp[go in some direction][steps + 1] = min(that state, dp[here] + weight of edge) code: https://codeforces.me/contest/1517/submission/114033176
This contest made me remember that I am bad at implementation :/
Same occurred to me!
Editorials please
Appeal : Start showing tests before system testing ends.
Thanks for the contest! B was nice! So was D, but apparently I have the big stupid.
I also spent way too much time verifying I put in the right amount of zeroes in A. Really should've written 2050 * (ll) 1e15 instead...
ReadingForces
ImplementationForces
finally pupil :'(
BYE BYE PURPLE)))))))
I can't figure out E... too many situations and so complex to implement
Round is cool!
Can we not just calculate all possible path of length
fc, wherefcis a factor ofk, from a cell(i, j)and then consider the min cost path? Wouldn't that give an optimum answer? Submission — https://codeforces.me/contest/1517/submission/114040509Waiting for Editorial...
Let me leave some complaints about constraints/TLs.
D: I saw/heard many $$$O(n m k^3)$$$ passed or was on the border. Assuming the intended solution is $$$O(n m k)$$$, I think this is very bad (why such small $$$k$$$). If $$$O(n m k^3)$$$ is intended, then it is also bad as it was then a constant-factor-optimization contest.
E: I was so lucky that mine passed, but the problem has clearly a messy cases-analysis solution, so I don't welcome 1 sec for this. I personally think the interesting part of this problem lies in the observation part and $$$O(n^2)$$$ -> $$$O(n \log n)$$$ part is boring...
G: Assuming the intended solution uses network flow (I haven't got the details yet, but looks interesting), I am very curious about the time complexity and how you determined the constraints.
In Problem E can you help me figure out why CPPCP is not a valid case for sample 1.
You have 1st and 2nd occurences of $$$P$$$ at distance of $$$1$$$ and 2nd and 3rd occurence of $$$P$$$ have distance $$$2$$$, which is invalid.
I found the problems very interesting, thank you for the round!
It really sucks not being able to solve Div2 D’s consistently even after practicising a lot.
Thanks for this !
auf
Failed D in system test because I put an n instead of m... now that's a dumb systest fail. Oh well, very easy ABCD.
ok.
Congrats Benq for earning the Top Spot in Rating Rankings in advance... Wooooooah!!!
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
Please do this always, first update then remove cheaters.
Do this in Educational rounds also :)
Would it make sense to have an additional "Pending cheaters removal" contest leaderboard status before labelling it as "Final standings"?
I think it is a very good idea to have some temporary status for that
Something like "Preliminary results"
Implementationforces? Problems were nice, but it took me a lot of time to implement.
Can we solve D using Dijkstra? https://codeforces.me/contest/1517/submission/114047555 (What am I doing wrong here?)
Why am I getting "wrong answer You answer is larger than expected. (test case 1)".I have printed n*m values only. Submission
Somebody respond to this, I had the same problem on Prestest 2->3rd test case
i also had the same problem in pretest 2
multiset<pair<int,pair<int,int>>> s............ suppose I want to erase or find {1,{2,6}} and it is present in the set.........how can I erase or find a particular nested pairs in set.......
auto it = st.find(the object) and then you can erase it if its not st.end()
Unrelated but why not use tuple<int, int, int> instead of pair<int, pair<int, int>>
Weak pretest for E:every $$$a_i$$$ in pretests is a big number.
So if you read the condition wrong like this:
$$$\sum\limits_{x\in C}a_x\leq\sum\limits_{y\in P}a_y$$$
it passed the pretest and fst.So sad......
Совпадение произошло по причине простого совпадения. Моё решение 114015470 по задаче 1517D - Исследовательская выставка значительным образом совпадает с решением 114031815 участника fitisovartyom123 по причине того, что задача решается именно так. Я не пользовался никакими источниками, весь код в моей посылке полностью написан мной и никуда не был выложен. С пользователем fitisovartyom123 я не знаком. Осмелюсь предположить, что у нас похожие шаблоны. Опять же, свой шаблон я написал целиком сам очень-очень давно. Учитывая количество участников, глупо предполагать, что у всех решение будет уникальным. Да и сравнив эти посылки самостоятельно, я не скажу, что они совпадают.
Полностью поддерживаю все вышесказанное. Я не знаком с этим человеком и не использовал никаких онлайн компиляторов. Наш код "похож" (хотя это тоже очень сомнительно) по причине того что мы делаем одинаковые действия. Сложно представить 2000 (около количества сабмитов D во время раунда) различных способов решить задачу на дп, в которой из смысловой части только пересчет. Удивительно, как не банятся каждый раунд половина сабмитов Ашек, в которых смысловых строчек еще меньше. Что касается шаблона, я использую такой шаблон уже около года, это можно проверить по моим прошлым решениям задач. Ну и еще возможно не самый убедительный аргумент, но мой аккаунт создан 2 года назад, аккаунт человека, с которым у меня похожи решения создан 3 года назад. За все это время никаких претензий относительно читерства к нам не было предъявлено. Неужели мы решили рисковать нашими аккаунтами ради одного сабмита?
Yesterday I recieved notification of recieving 379 rating and now my profile is showing I'm unrated. Why?????
It will show up again, the rating is being recalculated after cheaters removal. :)
Ratings return when?
kingmanas stop messaging me again and again!! Saale gaandu ab aur msg mt kar mujhe tere chutiye msgs dekh dekhkr pakk gaya hun pareshan karna chod de Main ladki nahi hun chutiye jo ladki smjhkr peeche pda hua hai tu mere!! Ladka hun main aur tu nahi jaanta mujhe main kaun hun tere batch ka bhi nahi hun! Jab tereko maalum bhi hai main kaun hun chutiye toh kyun mujhe apni bakchodi sunaye ja raha hai itne mahine se?? Tere baap ka account ka hai kya jo baar baar msg kr raha hai mujhe ki main use na karun? Apna kaam kar na gaandu