Ciao, Codeforces! We're glad to invite you to take part in Pinely Round 3 (Div. 1 + Div. 2), which will start on 23.12.2023 17:35 (Московское время). You will be given 9 problems and 3 hours to solve them. One of the problems will be divided into two subtasks.
The problems were authored and prepared by me.
We would like to thank
- errorgorn for his fun 🤌 🤡 🤓 😩 coordination;
- Alexdat2000 for Russian translation;
- franv for writing $$$173$$$ lines of checker of problem H correctly at the first try;
- franv for pictures in the editorial;
- dario2994, Endagorion, ffao, Golovanov399, nor for VIP testing;
- Kaey, MrBrionix, lorenzoferrari, nicksms, fwitt, milind0110, jamesbamber, alls, dorijanlendvaj, sunsh1ne, BrehamPie, 31ballons, gamegame, AndreySergunin, zeliboba, Jarnsida, I_L0Ve_MySelF, 1L1YA, MrAndria, TheRubbish, omsincoconut, jerefigo, dazlersan1, t0rtik, nondeterministic, SetBackIsBest, vantaablackk, htetgm, BestCrazyNoob, LaMatematica14, OgradL, bitset, magnus.hegdahl, Mirali777, Nika533, silxi, ttamx, ApraCadabra, pera2008, Sokol080808, A_G for testing;
- MikeMirzayanov for creating Codeforces and Polygon.
Score distribution: $$$500 - 1000 - 1500 - 2000 - 2500 - (1500 + 1500) - 4000 - 6000 - 6000$$$
We hope you'll like the problemset!
Update 1: the editorial is here.
Update 2: congratulations to the winners!
This round is made possible with the support of Pinely!
Pinely is an algorithmic trading firm, with its main focus set on high-frequency and ultra-low-latency trading. They have offices in Amsterdam, Limassol, Singapore, and Shanghai and are open for job discussions. Pinely is a team of winners, awardees, and medalists of various competitions in respective fields such as ICPC, IMC, HITB PRO CTF, and Google HashCode, etc. They constantly face various challenges such as developing strategies for trading, optimizing trading systems to achieve the lowest latency reactions to various market events, and saving and processing large volumes of historical data.
You can find out more about Pinely on their website or from their employees registered here on Codeforces. If you want to join the Pinely team, please send your CV to [email protected] or fill in the form:
Prizes: top 30 contestants and 10 random contestants placed 31-100 will receive a branded Pinely hoodie :)
so many testers
Well, so many problems
ok
I think this round will be exciting
Please, Pinely, can you say that 30 random participants who solve one or more problems will win a hoodie
Please make a gift for the new year
everyone knows that my contribution is still too high
I don't think this is good...
Have you to tried speedforcing SpeedForces?
As a tester, I tested
As a tester, I also tested.
as a not tester, i haven't tested
as a not tester, i also haven't tested
as a not tester, i also haven't tested
as a not obnoxious person, i stop this silly chain
people here are too sensitive
People here are insecure. They downvote on any criticism and I love it
as a not tester, I also haven't tested
As a tester, I tested (not a copy of the previous comment).
As a tested, I tester
as a decider, I am a participant in the competition
last two questions worth 6000 points each?!
Two 6000 problem vs rainboy
rainboy >> Two 6000 problems
Let's try to guess what franv did, something they can only share after the round.
That might be editorial
I don't think so. They could share it.
ig it's finding that (the original) problem E is duplicated?
As a tester, I am not allowed to write anything about the problems which includes my opinion of the problems.
omg 6000 problem round
As a tester, anyone who dislikes this round will be sent straight to the guillotine!
if I lost some points I will send you to the guillotine
He is your uncle, you can't
I will send you too anyway
How dare you, i hope bassam see this
I am going to be specialist in this round
is it rated?
Sure
thx
As a tester
As a tester, I tested
what a beautiful profile you have!
The fella in the right looks like a really smart person.
I think she is pregnant
well. i'm not :(((
:((
.
wow such a cute tester you are
Wich one am I?
second from the left
As a participant, I will participate in this round.
Is it rated?
As a tester, I might have tested.
i want hoodie
As a tester, I liked the problems.
Yay! after solving ABC, Now i have to sit for 2 hours staring at the ceiling instead of 1 ಥ‿ಥ
Edit: Story checks out
i'll be happy if i solve a,b,c quickly
"You will be given 3 problems and 3 hours to solve them"
I am curious about the statement from the coordinator that "**coordinating this round is so hard**".
Why would he have been saying this, any guess?
There are rumours that the round will be unrated because aryanc403 hasn't scheduled the post contest stream yet. Is it true?
Tagging his superfan VatsLakshya for confirmation.
haha :D .Maybe I'm a fan though :)
maybe it'll be rated because that means aryanc403 is preparing to reach red .
It's a busy day :)
Maybe a leetcode stream because it will be short.
The Round seems Nice, I hope I can enter it and finally reach Master.
Is it unrated?
As a tester I liked the problems
As a solver (participate) i hope... i will also like the problem set. Hope i will became pupil after this round. :)
never seen 6000 for a problem > combined score of first 4
Clashing with LC Biweekly. Got to skip this one.
leetcode clashes with cf*
Is it rated?
I hope I can reach Expert in this round!
franv for something that I can only share after the round;
What do you think about this?!
Hope not to become Master after this round XD
As a test, I attest to the testset being tested.
Hoping Positive Delta and reach Pupil or Specialist
bro Im new here. I want to know one thing. your max rating is newbie 753. but in your profile it is showing specialist why?
Magic Section in your profile try it
because of magic
codeforces become magicforces for few days...
Hope to solve at least 3 problems :)
as you are pupil and your atleast 3 problems solving probability is $$$1/9$$$ in div-2 contests your current aim should be to make sure you solve 2 problems atleast in a moderate time so that you can give yourself more time to try $$$C$$$ during the contest to give yourself more chance
Thanks for advice. What I wanted to say is to be able to solve C more frequently (I have solved it only once in div. 2 :p). Thinking that I can solve problem that that is very unlikely is encouraging me to try it harder. I guess that is the first step of becoming able to solve it, right?
Like for me it's like targeting atleast 3 problems in div-2 contest which I must do but and save time for $$$D$$$ so that I can have more chance in it , to me : solving 4 = good contest , solving 3 = average contest , solving 2 = bad contest , I think my $$$ 4 3 2 $$$ should be replaced by $$$3 2 1$$$ in case of you , and yeah gl for today
Yeah, glhf to you too. :)
As a participant , I live.
Question to Pinely HR team:
Is it possible to work remotely in the company?
I doubt a quant firm would let anyone work remotely for IP reason lol. They take it very seriously.
Can't wait trying to solve 4 problems glhf everyone
Hope to become Grandmaster to achieve my goals for 2023......
New Year, high ratings!
Finally university exams are over and I can peacefully give contests on cf.
for me they are this next week but still gonna do contest on cf peacefully
everyone good luck
am I going crazy or has the score distribution changed at least 3 times already, huh?
Wow
I hope I don't have to change my profile picture after this round
you need not at least as long as "magic" is there :)
They have already changed the score distribution 3 times, i see now why coordinating this round is so hard.
I tested the round, and the problems are very enjoyable to work on.
Please, shut the fuck up...
3hours which mean i must stay up to almost 1:30am cuz im in China,i think i will give up thecontest
...a little sad
Thx to all the testers for their contribution!
is it rated？
sunsh1ne tester — good round
can i join the contest without rated
as a non-tester, give me contribution
Have a nice contest everyone
As a participant, i registered
queueforces
Is it contest rated?
yes
Amazing mathforces round """""""""""""iam really enjoying it"""""""""""""""""""
is it only for me or pinned song on problem D is actually Desert Ruins by eliteLAQ??? as a participant, i was violently destroyed by problem B, as a fe2 fan i like pinned song on problem D
Really great soundtracks provided for each problem.
A tiny bit too easy contest.
Now what did franv do?
The checker of problem H.
How to solve $$$F$$$ in at least some polynomial time?
Nice contest, did ABC quickly, was close to solving D, but didn't had enough time...
Hey How to Solve B
for 1<=i<=60, check if 2^i satisfies the problem
power of 2, check the condition , if condition not satisfied then move on next
how do you develop such intuition?
WTF E ?
In problem D, when we are doing operations on x and want to make it to tar. Then won't there be cases where we partition it into y, x+k-y, and then recursively do operations on both of them?
As a rhythm gamer, B was the easiest ever opportunity to beat xi.
any hint for F1?
Notice how much can a[i] differ from a[i-1]. Then do casework
a[i] = a[i-1] or a[i-1]+1 or a[i-1]+2
Can you give a hint for what to do after this?
If a[i] = a[i-1] then don't do anything.
If a[i] = a[i-1]+2, then you have to place a number missed in a[i-1] at ith index and number i in one of the position missed in a[i-1].
If a[i] = a[i-1]+1, then you can place a number missed in a[i-1] at ith index or number i in one of the position missed in a[i-1] or number at ith position
OHH
Thanks a lot
Can someone please explain D?
Imagine you have to change a[i] to an array of same value x and using p operations. So you have this expression: a[i] + p*k = (p+1)*x -> a[i] — k = (p+1)*(x-k). This expression happen when a[i]-k divided by x-k. Using gcd and greedy, you can get x-k = (+-)gcd(array(a))(minus or plus based on a[i]-k)
Split 3 case: All a[i] < k, all a[i] > k, at least 1 a[i] = k.
Won't there be case where I split a[i] into y and a[i]+k-y and recursively do operations on both y and a[i]+k-y to get x?
Wow, what a round! First time solving div1+2 F, and first time actually using all 3 hrs, not just solving something and then staring at the screen
Thank you for an amazing contest!
I suppose DEF were really cool, though didn't solve E much
Super cool DEF. I just dont get why my F2 doesn't work when the solution is almost the same as F1 :(
Can you explain your D solution?
how to solve B!I'm so sad!
check for k= 2 ^(i) where 1<=i<=60
wait why does that work
think in terms of binary number
iterate from least significant to right significant
possible case: 1.all the elements have same bit 2.both 0 and 1 bits are present
if for ith bit second case arises then remainder will be 0 and 1 only for k=2^(i)
For k = 2^i, it is checking whether there are elements differing on (i-1)th bit. If we take first bit where (i-1)th bits are different then previous (i-2) bits are same, so we will be having two numbers 0 and 2^(i-1)
Can't the mod value also be (2^i)-1 and (2^(i-1))-1?
I get it! it's easily solved by converting to binary.but why can we think of binary?
find exactly 2 numbers !!!
so we need to think of ternary if find exactly 3 numbers?
thats what makes cp more interesting lol
I come up with a solution that passed all my test cases, but it's giving me a Wrong Answer (WA) on test case 2. I'm unsure about the underlying idea, but here's what I have so far: if there are both odd and even numbers in the set, then the answer is 2. However, if all numbers are either odd or even, then the answer is the gcd( all the numbers) multiplied by 2. This is the best solution I could come up with after about 2 hours of thinking and trying, but it seems to be incorrect.
according to you, for the case:
3 5 7
gcd = 1.. then multiplied by 2, which is 2.
3%2, 5%2, 7%2 = 1,1,1 which doesn't satisfy the problem requirements
when (gcd==1) I made it 2 and then multiplied by 2 which is 4
which will work in this case and any other case I could think of
3 7 11
in this case "4" also doesn't work
if all are odd then it has one number like 7 , 15 , 21 then ans is 2 and mod value is 1 1 1 , not satisfy the condition
how to predict rating change?
you can use an extension named Carrot, it shows some predicted ratings on the standing page.
so hard(sad)
Fun round, thanks mister TheScrasse
Thank you for the great contest.
I really liked H, and I'm curious to know how to implement the checker for this.
I think you can maintain BST for each odd/even index.
That's certainly true, thanks.
I wrote the checker. We use two treaps, one containing the even indices of the array and one containing the odd indices. To perform an operation we just cut the corresponding ranges from each treap and then swap them (odd indices become even and vice versa).
I got it. Thank you for preparing the problem.
Really liked C and D, at first glance neither looks like a problem that can be solved in polynomial time but they result in really cool formulations.
Also, I don't know if I love or hate that you put a problem with an actual exponential solution right after it xD. Btw, is there any way to prove that the number of good masks is $$$\lt\lt 2^n$$$ for $$$n \leq 19$$$ other than just generating them?
misread your comment
Besides my newbie performance, the music attached to each problem were out of this world!!
What the hell with E?? Seven very similar submissions, five of them TLE on test 7??? Moving the array from inside the function to the outside gets AC???
What's the intended solution by the way? Only have $$$O(\frac {\sum n}n\cdot n^4\log n)$$$ solution.
-update: I actually know the solution for $$$n>=20$$$, but am seeking for a quicker solution for $$$n<20$$$.
If n>=20 you can press every button. For n <= 19 I generated all the good masks (masks of pressed buttons that result in less than n/5 lamps turned on). It turns out that there aren't many such masks, so for every one of them you can check if it's valid (if it is consistent with every constraint from the input). So the complexity is something like O(1000 * m)
There is a simple insight : if you pressed all buttons then only squares indexed lamps are on, which mean $$$\sqrt(n)$$$ lamps will be on. With small n you just brute force bitmask, large n you choose all.
In my opinion, E's statement is too misleading and too unfair for newbie. I thought that if you push button a and button b, both require you to push some button v then you push it 2 times, which violate the rule. I waste a lot of time on that, only recognize in like 5 mins left, my solution failed on the last second due to some stupid bug. If you're experienced you will realize this problem is impossible and realize you misread something.
238568063 Can anyone tell me why this submission for B exceeds TL. I expect it to be $$$O(n^3\cdot log(n^3))$$$. Is it not ? Or is it not passing because there is no constraint on n over sum of all cases ? $$$n^3 = 10^6$$$ only. Shouldn't it pass ?
Well, $$$t \cdot n^3 \log n^3 \le 500 \cdot 100^3 \log 100^3 \approx 6\,907\,755\,278$$$ which seems to be too many operations for one second.
Thankyou for answering. So, in general we always have to account for the number of tests per sample ? I had this misconception that multi-test thing is only to speed up judging-times and the TL is adjusted and set the same way it would be for a single-test per sample scenario.
Not quite.
Let's say your time complexity per test case is $$$O(n)$$$ and there are $$$t$$$ test cases. This means that wosrt total time complexity is $$$O(tn)$$$ for the maximum allowed values $$$n$$$ and $$$t$$$.
If the problem statement gurantees that "sum of $$$n$$$ is at most $$$N$$$", then the total time complexity is at most $$$O(N)$$$. In this case, it often doesn't matter how many test cases there are per input file.
I see. I shouldn't have ignored the line in the statement, that clearly said that there is no constraint on the number of tests. Thankyou.
sir t= 500 , n = 100 then n^3 * t = 5*10^8 , so n^3log(n^3) take more than 1 second
Hmm understood. Thanks a lot.
In problem E is it possible to quickly calculate the number of lamps that will be turned on after n operations? Or does the solution not require this?
in E
if(n >= 20) then sqrt(n) <= n/5 if you turn on all of the lamps the numbers of lamps that's on is sqrt(n) which is 1*1,2*2,3*3,4*4,5*5,...n*n
what remain for u is what if n < 20 solve this with brute force
ty for explaining!
please can some one tell me is there any prerequisite for B & C or is it pure observation i don't wan spoiler. Thanks!
Bitmanipulation and Binary search.
I thought of binary search but couldn't come up with how we can check weather the minimum weight is achievable or not
See this, https://codeforces.com/blog/entry/123496#comment-1096446
Approach to solve C? Anyone please!
See,I can bet you are wondering if i sort both l and r in ascending order then taking the difference would work, but here is one case after which you can solve it by yourself,
n=4 l=1,6,11,18 r=7,12,19,24 c=1,2,3,4
It is already sorted, now if you take diff then it would look like this diff=6,6,8,6 Now,you will multiply the largest diff with smallest cost,so the score will be score= (4*6)+(3*6)+(2*6)+(1*8)=62
but if you place a r[i] which is just greater than l[i],then the score would be less, start placing those r[i] from behind because its always possible to have the r[k] for those l[k] where k<i, It's the basic intuition.
l=1,6,11,18 r=24,7,12,19 (start placing from behind)
diff would look like this, diff=23,1,1,1
now,if you calculate the score it would be score=(1*23)+(2*1)+(3*1)+(4*1)=32 only which is less than 62. So,insert all elements of r in multiset and use lower bound and erase after every iteration.
I hope it makes sense to you.
Thanks man, I had just the same approach just couldn't implement it:(
It's totally fine,do upsolve to increase your confidence.
Bad contest,Bad problems, thanks for wasting our time.
great contest, great problems, thanks for the fun round
Don't thanks me , Iam not the author
oh, i really thought you were the author, sorry
It's ok. Write a general comments to the author
Please downvote him guys, he is my friend and he deserves it
If you see I deserve that ,it is ok Big Respect
Problem D is very cool))
One of the best contests I've ever had
For some reason, I wasn't able to view problems on main or mirror (mirror said something like "This problem doesn't have a statement"). Strangely, this message was shown only on the first 4 problems (I was able to view E atleast) on mirror, while on main I wasn't able to load anything at all. This happened for the first 10 minutes.
I tried opening CF on incognito and it worked fine, so I disabled uBlock and CF-predictor and only then was I able to load the problems.
Can anyone make sense of this?
Great round!
Appreciated the reference to 1656C - Make Equal With Mod.
Thank you for the nice problems! To me, the round was fun.
Kavi orz!
is the contest rated?
Yes
Thank you
Can anyone hack my O(T*2^N*N) solution for E? https://codeforces.com/contest/1909/submission/238581537
The strategy is simple: Backtrack all possible combinations from switch 1 to n, not pressing first for each. Check if it violates any rule every time we press a switch (for smaller numbers, check if it's already pressed, and for larger numbers, set a must-press flag for that switch). Print the answer immediately if we find any solution.
Thank you, it's uphacked now.
Where do you see that it's uphacked? I believe that it's my hack, though it still shows me accepted on your solution and hack as pending
On my machine your code works about 10s:
Right after you submitted the hack, I got a message from System that it's hacked, so I think my solution already got TLE. Perhaps there's some issue while it's being tested on the testers' solutions? (probably a tester's code also got hacked with it?)
In problem B how come the answer is gcd of differences between the numbers multiplied by two ? gcd would give the number which would make entire of the array same , but how come it being divided by two is the ans?
since when we divide all of them by gcd, each are either even or odd, giving 2 distinct remainders
When will the rating changes applied?
FOR C QUESTION WHY THIS IS WRONG
sort(v1.begin(),v1.end()); sort(v2.begin(),v2.end()); sort(v3.rbegin(),v3.rend());
for(int i=0;i<n;i++) { int d=v2[i]-v1[i]; c[i]=d; } sort(c.begin(),c.end()); int sum=0; for(int i=0;i<n;i++) { int a=c[i]*v3[i]; sum+=a; } cout<<sum<<endl;try this
answer is
okie thank you
I had the same question for more than 1 hour. But later I understood why it failed!
somewhat got very lucky 238563505
and saved rating.. 😙
thank you
In my opinion, B was harder than C.(The gap is not big though)
as a fake cm, i brick c
been ridin with you since you were just a pupil, gotta give props to your hustle and the realness in your grind. Keep killin it!
after the rating update , magic changes got reversed
then do the magic again?
The most miserable thing is not that you cannot do problem E, but you realized that you can press all the buttons when n >= 20 in the last 5 minutes of contest.
My screencast and editorial (both in English and Russian)
Typically on rounds it seems that the easy problems are not always that fun / interesting, that was not the case this time! thanks to the authors of abc :)
In que 2 I am getting WA for this block of code can someone please help me with this: int fans = -1; int st = 1; int end = 42; while(st<=end){ int mid = st; ll ans = 1ll << mid; set s; for(int i=0;i<n;i++){ s.insert((1ll*arr[i])%ans); } if(s.size()==2){ fans=ans; break; }else{ st++; } } cout<<fans<<endl; Thankyou in advance <3
Can someone tell me that why the time complexity doesn't exceed in Problem 2 , like there are 500 test cases each with n ranges from 2 to 100 and in one test case we go from 2^1 to 2^57 then total number of operations would be 500 * 100 * 57 ~ 2850000 ~ 2*10^6 . time constraint is 1s and in 1s max 10^6 operations can be done. and can any one give me advise what to do in such situations because i got this answer in the contest duration and i didn't code it because of this time complexity.
learn complexities
-
thanks for the round, problem D directly hit on my weak spot, but it is quite satisfying when I successfully upsolve it and it is very interesting :D
i got fooled by testing system since my solution had (1 >> j) and it violated the range of int but testing system said it was wrong answer. Anyways i didnt lose any rating and changed every 1 to 1ll and it worked. Fun problems, cool songs, i liked the round!
correction: my solution had (1 << j), not (1 >> j)
Thanks for the great round and the strong examples on D! I had trouble with $$$= 0$$$ and $$$< 0$$$ values and would have gotten a lot of WAs without the last two.
I couldn't figure out them (the 3 corner cases) during the contest :(
If my solution is found copied and my submission are skipped then why has my rating deducted for that contest the rating should be skipped. You have first removed the points awarded for the contest and then also deducted some points.It should not happen as contest is skipped for me
Is there a handsome guy who can help me？ How to solve F1? I cant understand the tutorial。
I don't understand what is happening. How zh0ukangyang is the round winner and two first solves but had delta -3321?
It was an alt account of orzdevinwang, and the account was banned and the rating was forcibly set to zero.
Congratulations to hoodie winners! In a few weeks, you will be contacted via private messages with instructions to receive your prize.
As usual, we used the following two scripts for generating random winners, seed is the score of the winner.