Hello Codeforces!
magnus.hegdahl and I are glad to invite you to Codeforces Round 767 (Div. 1) and Codeforces Round 767 (Div. 2) which will be held on Jan/22/2022 17:35 (Moscow time)! This round is rated for both divisions.
In each division there will be 6 problems and 2 hours to solve them.
We would like to thank the following amazing people:
- 74TrAkToR for great coordination of the round and translating the statements!
- efimovpaul, agrayush13, ak2006, BidoTeima, QuangBuiCPP, mesanu, _Vanilla_, qwexd, FedShat, gupta_samarth, namanbansal013, hbarp, stefdasca, AlperenT, DIvanCode, plagues, voventa, kpw29, ptd, AlexLuchianov, PurpleCrayon, abc864197532, Maksim1744 for testing, providing invaluable feedback and being awesome!
- Nika_Tamliani for helping in the early stages of the round!
MikeMirzayanov for great Codeforces and Polygon platforms!
- You, for participating and upvoting!
Score distribution:
Div. 2: $$$500$$$ — $$$750$$$ — $$$1250$$$ — $$$1500$$$ — $$$2000$$$ — ($$$1500$$$ — $$$1000$$$).
Div. 1: $$$500$$$ — $$$750$$$ — $$$1250$$$ — ($$$1000$$$ — $$$750$$$) — $$$2250$$$ — $$$3000$$$.
UPD1: ak2006 and namanbansal013 have prepared video editorials for most div. 2 problems that will be available on ak2006's channel and namanbansal013's stream
UPD2: Editorial is out!
As a tester, I am asking for your precious upvote.
As a tester, pls help I can't figure out a decent as a tester comment
You can try this as a tester comment :) : "As a tester, pls help i can't figure out a decent as a tester comment"
You might try this as a tester as a tester comment :): "You can try this as a tester comment :) : "As a tester, pls help i can't figure out a decent as a tester comment""
and you can try solve problems
.
You can take this as a reference.
https://codeforces.com/blog/entry/93538?#comment-825976
As a tester, I think problems are great. I highly encourage you to participate in this contest and check out all the problems.
Tip: Having a cool profile picture like mine might help you do better :)
Tip: Having a cool profile picture like mine might help you do better :)So that means I will AK that round?
As the person who has seen the tester irl for 1 time I can say that he is very great dude (vanilla confirmed)
As a participant, thanks for putting the contest on a weekend!
As a Mihai supporter I wish all the Mihai supporters to get +300
upvote announcement blog or negative delta
mihai
mihai.
mihai..
mihai
mihai..
mihai
mihai
mihai
mihai
what usually happens to these comment chains is that each comment gets +50 initially and then they're downvoted to hell
what usually happens to the comment that breaks the chain is that the comment gets downvoted to hell.
Women: I don't know why women live longer than men
Also men:
https://discord.gg/E9MAGEu9
mihai
what has this community come to
mihai
mihai
stfu furry
stfu furry
stfu furry
stfu furry
stfu furry
Stfu furry decreasing sequence !
My contribution became a decreasing sequence.
Time to upsolve: https://codeforces.com/contest/1537
I actually did terrible that contest on vc and wish for more luck this weekend :prayge:
Don't ever upsolve! If a problem appears at one contest, what is the chance that it will appear again?
Don't ever practice! If writing code is required to get points in a contest, what are the odds you'll need to do it again?
bruhh
watch this: https://www.youtube.com/watch?v=cB5jSWxYmrs&ab_channel=ICPCNews
It's true that there are low chances of a problem appearing again. But for flex purposes upsolving is always recommended.
This is a very well prepared round!!!
As a tester, I would like to express my appreciation for the setters and coordinators for their efforts to make this round as enjoyable as it can be, and to invite everybody to participate in this contest!
P. S. also my salary is contribution plz upvote
I really liked the idea of problem D. What a clean observation!!
as a tester, i'm late for commenting
as a tester, I think the problems are great. Recommend participation.
As a tester, the problems are interesting and you will enjoy thinking about them and solving them.
As the video editorialist for most div 2 and some div 1 problems I have tried to make the solutions intuitive and simple to understand so do subscribe to my channel
Yet another Mathforces contest O_o
Little do you know
as if I don't know
Good luck! I wish every grey become green!
I am ready to sacrifice my Delta for your positive.
We both become green after this.
Looking forward to this round!
Wish everyone good luck&positive delta
Btw, that's a great score distribution
Good score distribution! Wish everyone good luck and positive delta)
As in this contest, having official video editorials for every contest will be a great idea. This will motivate the content creators in terms of money and views and will be good for the whole CP community as well!!!
As a tester, I had found that one of the problems could be solved by Googling. But now it's substituted with another great task, mission accomplished! Also, the round is really entertaining, please participate, remember to read all the problems and stay healthy <3
We could have won more rating but you fucked everything up :(
UpvotesForces
Wow that's quite a list of testers! Is it documented somewhere how to volunteer for testing a round?
I'll earnestly try to participate in yours, but, like most rounds, it's 6:35am in my timezone :|
In Romania, we call the process to volunteer for testing as "sa ai pile".
In all seriousness, the problemsetter is the one that asks you first to test their round. Then, it is up to the candidate tester whether they accept or not
Ah, I thought tester responsibilities were something more formal curated by Codeforces coordinators. Gotcha, thanks for clarifying!
glhf
Can't wait to see a new, well-prepared, interesting and fun cf round! GO-GO-GO SlavicG!
<3
As a tester, I want to see bigDuck on standings
As a setter, I want to see bigDuck on standings
As a tester, I believe all of you will enjoy these excellent probelms.
As a fellow tester, I completely agree. Good luck, have fun!
I hope this.
mihai
mihai
Score distribution announced early.
Thanks
74TrAkToR is coordinator, so we should expect combinatoric problem which is in wrong order.
you are right
perfect prediction.
My gut feeling is saying that the problems in this contest gonna be very interesting, gonna get +ve delta
WA is certain but it doesn't have to be ugly
A palindrome round (767). Nice :)
Magnus from Norway. Sounds familiar to me...
It's the 25th most common male name here :D
You certainly play chess.
Can we see Mihai in problemset?
Of course, I'm sure Mihai is shadow ruler of contest
First Norwegian round. (I think...) Let's go!!!
magnus.hegdahl orz
I wish you all to get repeated TLE's and passed pretest but gets failed in system testing may your code gets skipped and you get a minimum of -100. all the worst :) . may you get down by h whole level.
Not again (◔_◔)
seems u have seen this XD
Who? asked
Wishing you the same!!
bad boi
I am a new programming learner. I have just finished the basics of C programming. Can/Should I participate in this contest?
Yes participate
I hope the server won't break down again(
No jinx plsssss.
Wish all participants enjoy tasks and get higher ratings! ^-^
Is it theoritically possible that all the participants get higher ratings ?
This is an easy task for Mike to do :D
ofc
Hope this contest completes smoothly
Cheaters better not cheat. Else I'll whoop your ass
"virtually"
Good Luck peeps!!
abacaba
Why can't I submit my code?
in div2 F1 what does "score of the optimal game" mean? average of all the possible scores? SlavicG
Use clarifications section for clarifications during contest
I think that shuffling problems in div.1 is not a great idea.
Speedforces
How to solve div2E.
And is div2F1 some standard problem as some div1 participants solved that instead of div2E.
Not only they
I just looked at div1 stat and decided to solve F1 instead of E and it worked out
Pretty simple dp
2E ended up being a logic puzzle instead of a coding problem. Once you solve the logic puzzle, the implementation becomes O(n^2).
Ad-hoc-forces!
Problem A to D are too easy, especially Div1 D is much easier than usual .
And I have a O(nlog^2n) solution to E , but it got TLE . So Sad ...
And problem B seems to be hard to implement . I don't like this round :(
Seems that Div.1 E has a way too strict TL? My $$$O(n\log^2 n)$$$ solution keeps going TLE. Or maybe the expected solution is $$$O(n\log n)$$$ then just ignore me.
Yeah, O(n log n) is intended.
Well, I have come up with an $$$O(n\log n)$$$ solution (requiring $$$O(1)$$$ LCA), and it seems a bit harsh to code. I guess it would be better to set both $$$O(n\log^2 n)$$$ and $$$O(n\log n)$$$ solutions as acceptable. Anyway great contest!
+1
My $$$O(n\log^2)$$$ solution didn't pass but after changing it to $$$O(1)$$$ LCA it passed.
But I heard that it is not needed, since we only need to find the vertex with the smallest $$$dfn$$$ and the one with the largest $$$dfn$$$.
An interesting thing is that I first read the statement wrongly . I mistakenly think we should work out the max of sum. I found it in the last 10 minutes when checking the example . So I changed some parts quickly, and have no time to make it faster.
In fact, me the same, I even finished my 3k code and then found myself not passing the sample.
But I used Kruskal and the problem become asking sum again!
O(1) LCA. Never heard of that. At least now I know something like this exists. Thanks for your comment.
Farach-Colton and Bender Algorithm
How To solve C and D of Div2 ???
D was DP i guess and I solved C as I build reverseMEx array(mex till i from n) and then brute-forced from being (might get TLE in sys testing)!
If any of the strings in the list is a palindrome, the answer is yes! If there is either zyx | zy for any string xyz, then the answer is yes! The trick is to check for zy because we are only storing strings in hashmap. To do this, we find for every ch in small alphabets if reverse(zy(ch)) belongs to hashmap then the answer is yes! Otherwise, the answer is no.
C: The basic idea here is to keep taking elements until the mex for the current set of taken elements cannot be increased by any element present in the remaining elements.
Now to increase the mex of the current set of elements, mex itself is required to increase itself. So, I kept all the elements in a multiset and then checked if the mex of the current set of elements is present in the remaining elements or not. If it's not present then we can start a new set of elements from here. Else, just take the current element and then increase the mex till it can be increased.
Now to increase the mex, I have created a hash table and put the current elements in there. Now, until the next element is not present in the hash table, keep increasing the mex. This is the basic idea. Code
D was mostly observation.
Trivial Case: If the input strings are palindrome, then return True.
Observations:
Now the palindromes that can be created will be of length at least 4. If you break a palindrome of a given length only in segments having 2 and 3 only. Then the first and last segment will also be of length 2 or 3. I can construct a palindrome out of the first and last segment only. So I can have the following combinations of lengths:
Now all that's left to do is check if we can create a palindrome considering the current string as the last part.
For this purpose, I can have previous strings in a set and then reverse the current string and check if it is present in the set or not. This part is easier said than done. Have a look at my implementation to understand it better. Code
I regret ever making fun of line trees, I didn't pass E because I had no template for them QAQ
Only If I got 30 more seconds I would have submitted D,!!
Great contest
but feel sad for sitting there trying to solve 2E for 70min but stuck at the last step
Is there a formula for 1628D2 - Game on Sum (Hard Version)?
$$$O(m)$$$ formula (can maybe reduce to $$$O(1)$$$)) after preprocessing:
if $$$m < n$$$. If $$$m = n$$$ then the answer is simply $$$k * n$$$.
FML
I found an $$$O(n)$$$ formula for D2 instantly, but I kept treating $$$n, m, k$$$ as queries and completely forgot that $$$O(n)$$$ would just solve the problem...
Please share the formula.
For $$$m > 0$$$,
Turns out this on OEIS as A193605 if you remove $$$k$$$ and multiply by $$$2^{n-1}$$$.
Here's some intuition for how to find the formula.
Take your DP solution for D1 and formulate it as a path on grid problem: you start at $$$(0, 0)$$$, you want to reach $$$(n, m)$$$, you have a $$$\frac{1}{2}$$$ probability of moving to $$$(i + 1, j)$$$ or $$$(i + 1, j + 1)$$$ from $$$(i, j)$$$, and if you reach a cell such that $$$n - i = m - j$$$, you can only transition to $$$(i + 1, j + 1)$$$ and add $$$k$$$ points to your score. Answer is expected score over all valid paths. Now you can count grid paths with binomial coefficients and powers of $$$\frac{1}{2}$$$.
(The exact indexing might look different depending on your DP.)
Submission for Reference
((SUM(i=0 to m-1) (m-i)*(n choose i))/2^(n-1))*k
Same, smh
I declare myself the dumbest person on this planet when I realized after 40 mins that string of length 1 is always a palindrome, so you only need to handle strings of length 2 and 3.
I never realized it at all, so you are definitely not the dumbest :|
I realized it only after reading this comment.my code had the cases (1,x,3) for all 1<=x<=3 as well(the numbers denote the length of the string)
Can someone tell me what is wrong with this code for D? I broke it into cases...failed pretests Code
Try on this test case:-
Problem div2 E is my favorite problem I've seen in recent memory. :)
Based 1C solution: Just steal constructions from math contests lol
Too bad I never practiced on such old ISLs in my high school years...
How to solve div2 promblem E?Is it should be divided into 2 * 2 grids to solve?
I could think out diagonal XORsum of problem E 10 minutes before contest over. that was close
Unfortunately, I only got it 5 minutes after the contest (arghhh). As an aside, F1 looked pretty nice. Too bad I didn't have enough time to solve it. You don't see DP with fractions too often.
A-D great stuff, thanks!
Sometimes there are problems having very intuitive algorithms (but to prove their correctness requires time) so I'm wondering whether there are people eagerly submitting such intuitive algorithms without formally proving them. Those submissions still can get Accepted when they are lucky.
After participating in several contests at Codeforces, I realize that perhaps I have to submit things very quickly, without carefully thinking about their correctness, otherwise I will get a low rank because of late submissions.
Do you think this is good? In other words, do you think it is common and acceptable to do such quick but not reliable submissions in competitive programming?
(I don't like unreliable things, so I feel uncomfortable when I have to do such quick submissions.)
-is-this-fft- mentioned his style of solving problems in this Blog
That is roughly how I feel I solve problems: try to really understand the problem, gather insights about it. And at some point, you have found enough observations that you can piece together a solution. The solution isn't proved afterwards — the proof develops alongside the solution. It isn't always like this, but very often it is.
I feel after a certain point it becomes difficult to solve problems without proving.
who did place hacks format before output format in 2E? WHO DID THAT?
loved the contest! strong pretests and amazing problems ... :)
Me reading Mihai as
Mithai:)I forgot to check if the given strings are palindrome and failed on Div 2 D
Peculiar Movie Preferences Video Solution.
Don't forget to like and subscribe!!
https://www.youtube.com/watch?v=xBkDyMHVTJ0
Does anyone realise that after a few hours there will be the first 4000+ rated user in entire history of codeforces?
очень классный раунд, спасибо авторам!
Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!
Looks like Mike has to think about the new name for 4000+ rated users real quick. Tourist is almost there
Mihai is very abnormal person, i mean look at his movie choice.
My Submission Div2 C it is giving tle on test 5 can someone plzz help me out ??
The link is broken. Didn't understand the idea, but if it's only tle, maybe it's because of initialising of set with 200000 values for each run.
yaa exactly this was the error. I changed it to n and it is accepted now. Thanks for pointing out. Dont know how can i do this blunder.
Could someone please point out my mistake for div. 2 D? Here is my submission
nvm figured it out
What was the mistake ? Actually I am also getting error on same test case u got .
try this
expected output is "YES"
Yeah works fine on this.
As the Victor from 1628C - Grid Xor, why did you, mesanu, steal my grid????
As the Mihai from all the problems, if I steal your grid, I get your IOI medal.
As your RMI team leader, I challenge you to get one this year and return mine, please
My AC submission 143728411 for Div2 C/ Div1 A gives a runtime error on this test case:
I'm not sure why this happens. Could someone perhaps explain why this happens?
Update: Nvm, this test case isn't valid.
accidentally put this comment not in the editorial :/
Hey, Div 2 Problem B i submitted the same code but in different C++ version, in C++ 17 it got accepted but in C++ 20 it gave me wrong answer and because of this i had 3 wrongs submissions, can someone please tell me why this happened, like the code work in one version but in the other newer version it gives WA?
Code:
- C++ 17 (AC) : 143715633
- C++ 20 (WA) : 143715622
Any help is appreciated!
Short Answer: Never trust floating-point arithmetics. Use integer arithmetic instead to get accurate results.
The problem isn't because of the compiler version, it's because of floating-point arithmetic.
Floating-point arithmetics(especially,
float) are usually very likely to be inaccurate, because, unlike integer types, floating-point types can’t represent exact values. Also, they can give different results on different compilers or machines. For example, some hardware architectures may support advanced floating-point operations, and some compilers may use different floating-point instructions depending on the system.If you run the codes below by the “Custom Invocation” feature, you can see that GNU G++17 7.3.0 and GNU G++20 11.2.0 (64 bit, winlibs) give different results.
Don’t use floating-point types if you can go with integer types. If you absolutely need them, use
doubleinstead.Oh thank you so much i will be careful next time!