Hello! Codeforces Round 946 (Div. 3) will start at May/20/2024 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
You will be given 7 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Round is based on UKIEPC 2024: Spring Practice. Please refrain from participating in this round if you are familiar with the tasks of this competition.
I would like to thank:
Authors of the original competition: Aksenov239, MaxBuzz, RobinFromTheHood, darnley, izban, pkhaustov, lsantire, az453, fedor.tsarev, Shoaib Jameel.
MikeMirzayanov for help with ideas and Polygon and Codeforces platforms.
-is-this-fft-, peltorator, tute7627 for red testing.
ibraevdmitriy, kaikey, gmusya, nika-skybytska, Giga_Cronos, diskoteka for yellow testing.
TypeYippie, kzyKT, tepamid, ahshafi for purple testing.
Abo_Samrah, Zandler, sam07a, YESMAKHAN, xygzy, Klaus26 for blue testing.
Morvolzz, dasha..zhilina, sutekine, Muhsen, Gojova, Acanikolic73 for cyan testing.
You for participation.
Good luck!
UPD: Editorial is out.
well-balanced div3 round, GL for all participants 🏆
I can barely contain my excitement! I hope this will be a good one! GLHF!
That's good username, ain't gonna lie.
As a tester, I hope you to enjoy the contest. Tasks are quite interesting and educational. Good luck!
Can I get the following test case:
Test Case 2: wrong answer 1110th numbers differ — expected: '5', found: '4'.
int t =0 ;
void testcase (){
if (++t==1110){ for (int i = 0 ; i <n ; ++) cout<<arr[i]<<'|'; cout<<"\n"; return ; }}
try to avoid seeing your wa this will affecr the ability of discovering wa
Good round, come and participate.
Another Vladosiya round!!!
hoping to return back the blue handle
As a participant I have to say im excited.
wishing to get my Pupil back
Well GLHF, let's gain some rating!
as a tester , i hope you enjoy the round , a realy very good round <3
This is my coach (sam07a) :), who is yours?
You have higher rating than your coach..?
This 's my coach Who is yours?
As a tester, I encourage you to read all the problems.GL and Happy Coding.
Hope i can solve till E this time
Looking forward to an AK, and GLHF to all participants, rated or not!
Hope to reach cyan this contest : >
Mewing cat ready for the contest
bye bye
Beautiful Contest...
I Loved Solving the problems...
Especially the relation "Money Buys Less Happiness Now" with "Money Buys Happiness" won my heart :)
Thanks for nice tasks.
Funny that I solved G by accident couple months ago.
E was tough
Teach me your ways big bro you’re so strong
E had a nice dp thing. Take dp[i][x] to mean the minimum number of pounds you need in order to obtain at least x happiness at month i.
The transitions are:
for a certain happiness x, we know that dp[i][x] is at most equal to dp[i — 1][x] (that is, the answer for the previous month). dp[i][x] can also be dp[i — 1][x — h[i]] + c[i] if c[i] + dp[i — 1][x — h[i]] <= the amount of money we have garnered so far.
dp[i — 1][x — h[i]] + c[i] represents the minimum cost to get at least x happiness assuming we buy happiness at month i. Of course, we can only afford this if it is less than our current amount.
We don't want x — h[i] to go below zero. So dp[i][x] = min(dp[i — 1][max(0, x — h[i])] + c[i], dp[i — 1][x]).
After this, in order to make the dp[i] represent the minimum number of pounds to get at least x happiness, we just let dp[i][a] = min(dp[i][a], dp[i][a + 1]) for a going from the sum of all happiness to 0. Aka just take suffix minimums.
The base case happens at month zero (or at month 1 actually since you technically have no money at month 1). The minimum number of pounds we need in order to obtain 0 happiness at month 0 is 0. The minimum number of pounds we need to obtain x >= 1 happiness at month 0 is infinity.
The answer will be the highest index in dp[m] who's value is not equal to infinity.
There was a lot happening in this problem.
Ohh I see it now! I thought of dp[m][h] but instead assumed min cost to get exactly h and couldn't move anywhere with transitions so weak.
Thankyou this solution is very good, I hope to achieve this level of dp sorcery soon.
Try seeing this...
https://mirror.codeforces.com/contest/1974/submission/261935786
Very much like Knapsack when we take dp on values instead of weights.
Thanks, I just remember solving Knapsack — 2 on AtCoder I'm so stupid bruh.
In problem C, I have wasted a lot of time in addition to 3 wrong answers because I thought that 1 <= ai <= 9
fail to solve D
hardest Div3 I've ever taken
byebye cyan hello green
Me too. I failed on C but succeeded on D. Even D takes a lot of time. Why we should move both the rover and the helicopter? If we may only move one, it will be much easier.
yes, I do aware that but still, implementation was too heavy
there are too much corner cases, loc easily beyond 100
75, 3-4
ifs: 261907165Div. 3 like Div. 2.5
more like Div3: Algorithms, Div 2+: Implementation. I spent over an hour trying to debug F.
I agree first 4 were all implementation based.
yeah same, i only realized after like 30 min that they for some reason swapped the x-axis and the y-axis. couldn't solve G (in contest) then :(
Though, I was not able to solve it, E was amazing.
Though, I was able to solve it, C was disgusting.
Does E have any connection with knapsack II of atcoder dp contest?
Not sure, but the atcoder problem can be solved using the idea mentioned in point 5 of this blog
More or less.
humiliating
The hardest div 3 I've ever seen.
(corner_case)Forces
Can someone pls tell me how did you solve que C? I tried solving it using brute force and got TLE multiple times 261901233
Think of how find the number of beautiful pairs of triples that differ in the third element... then think of how to extend it
good tasks
In this round, there were three problems based on my ideas: 1974B - Symmetric Encoding, 1974C - Beautiful Triple Pairs, 1974F - Cutting Game.
C was tough or it uses some specific technique that i wasn't aware of.
check the tuples where item of position K is unique. Tuples's positions = {0,1,2}
I will show logic for K=0, but similar logic can be used for K = 1 and K = 2.
For each tuple. Create a map that stores {1,2} as a key and a list of integers the 0s as values. Then sort that list. Then you can figure out how many items are strictly less than n, with a linear scan.
i did the same but miscalculated the number of tuples.I think its time for solving some Combinatorics problems.
Is there any solution for E using maps? If yes, can someone fix my code 261908381?
Well I tried to optimize your code, eliminated the use of one map in this submission 261926879. But it still gave TLE.
I initially also got a TLE during the contest on test case 14, that is because I did not notice the upper bound over all the test cases was on sum of
hiand notm.Thanks
This solution got accepted 261959135. But yeah now I am forming Happiness-money as key-value pair instead of money-happiness, considering the upper bound.
Hardest Div 3 ... Only div 3 B solved ... can some one tell me the logic of C
use a map for each triple:
count += the number of triples that have atleast 2 similar elements
count -= the number of triples that are the exact same
hmmm, do map can carry triplets .... i think i have to learn stl library in brief .. Thank you .
I just used a map<vector<int>, int> and it passed.
map can carry any pair of datatypes(
map<T,T>)for the case of task C, it is possible to solve it using 4 maps, 3 of them are
map<pair<int,int>,int>and the 4th one ismap<tuple<int,int,int>,int>(for 3 equals)is D that easy ? there are a lot of submissions...how to solve it
the most important is to notice that the opposite directions like (N, S) and (W, E) are remove each other.
I took more than one hour to solve D
how did so many people understood this: each character in the string s is replaced by its symmetric character from the string r (the first character of the string r will be replaced by the last, the second by the second from the end, and so on).
I feel like I lack the ability to guess the problem statement
There is a picture in the problem statement that explains it
The time limit and constraints of C could be managed better. Other than that, the problems were nice.
any hint for E? I tried dp[m][x] using map but obviously I get TLE;
Try dp[h] = max money we can have after buying $$$h$$$
vstiff can you tell your transitions ? for the dp states and why so reason too please
Basically just two transitions:
1) buy everything
2) get salary
I've solved with dp[m][total_happiness]
obviously it passed
Hi daud04, I see you have done recursive DP, can you please explain your solution in detail if possible? I couldn't think of a way dot it recursively as money from previously bought happiness can still be leftover and help us in future, I did it iteratively : link , If anyone else know this please feel free to pitch in.
my dp state is [index][required_happiness] and it returns the minimum required money i must have before entering the state to buy required happiness.
(i'm just going forward here)
as a knapsack dp, there is 2 option.
if i buy the happiness of the index , i must have a[index] value now , and must have the to money to buy remaining happiness from next indexes, as i can store this k for next indexes , substituted k from next dp cost.
nice problem set! i have seen same ideas like in these problems before, but they are usually in div2 and too hard to solve. thank you for introducing them for me!
Really nice contest. Problems were not too difficult, and liked the problem E especially. Problem D was implementation heavy and if not for some mistakes in it and time wasted in debugging it, this would have been my first contest to solve all problems as I solved G just few minutes after contest ended :(
I have a bonus problem (Harder version of problem $$$C$$$) : A pair of triplet is good if elements in any two positions are not equal and equal in one position , count the number of good pairs
wouldn't it be equal to the total number of pairs — number of pairs with exactly 2 matches (current problem) — number of pairs with all 3 matches?
you also have to subtract number of pairs with 0 matches
Tough C, I come up with the the solution pretty quickly but spent many times to implement it 261860863
And D also a terrible implementation(at least for my code) I neerly smashed my laptop when I realize what I am coding 261856874
And can someone help with my E? At first I thought it was a signed int overflow (because it did't WA until test case 10) but it seems to be more than that... 261884565
I tried submitting your code 261934590 and got it accepted. The idea was that a particular state can be visited many times, you assumed that it can be only once.
If it is visited more than once, we minimise the value of
dph[i][j + a[i].ss]for every such visit.Oh my god, I actually have realized it but my brain didn't go right and made huge amount of small mistakes when I tried to modify it :(
And It should have been Accepted if simply to add a more
!in my last minute submitted code rather than failed in test case 1 (:_;)Anyway, thank U very much orz
Are all submissions tested against the test cases from successful hacks at the end of the hacking phase?
Hardest div3 I've ever taken, C is harder than an average C in div2.
A: Really easy problem, as it should be (800)
B: Already semi-difficult, similar to 2B in some ways (1000).
C: Extremely difficult to implement and solve for its position, analgous to easy-mid Div2C/Div3D (1300)
D: Easy to solve, ananoying to implement(1300).
E: Elegant but hard. DNS (1700).
F: Got me stuck in debugging hell for an hour (1900).
G: DNS (2000)
dns is short for what?
Did Not Solve.
???
I'm a noob and it was very easy IMO. Done it in 12 minutes.
*Deleted
got AC on D after contest simply by removing pre-check, but simulate answer then checking correctness.
I don't see that in your submissions...
I had the right idea on C with the three maps but I couldn't think of the way to sum them up correctly :(. Problem D was really nice, the concept and everything. E was also cool but I didn't really have time to solve it. First time I solve D and don't solve C on a contest which I didn't expect to be fair but I'll take it.
Try this way for C
AC in 999ms for me https://mirror.codeforces.com/contest/1974/submission/261840334
Any idea how to do this faster? https://mirror.codeforces.com/contest/1974/submission/261915177
don't copy the string every time you find a duplicate character
done thank you :)
In F, what if k is fixed in input and instead of moves being given, both players play optimally to maximize their score?
n^4 dp !!
I am surprised that ChatGPT was able to solve problem G in this round. To be more specific, I was stuck on G, so I put the problem statement into ChatGPT, which is a hot topic right now, to try to get some clues. Initially, it presented me with an incorrect greedy code (a simple greedy method of looking from the front and buying if possible). Then, I provided an example that would fail with this solution (Test Case 3: 6 4, 4 10 3 8 6 10). To my surprise, it then gave me the correct greedy algorithm using priority_queue! (This might have been a lucky punch, though)
I am unrated so I am not particularly affected, but for contests like div-3/4 with many typical problems, ChatGPT might be able to solve quite a lot of them...... (I haven't tried it yet, but I think it can also solve problems like F, which have straightforward and typical approaches but may be a hassle to implement.)
(My prompt: https://chatgpt.com/share/05ad0c4b-33a1-4480-8f46-c7a87a60f019 we need to fix some details (input and the timing of adding X), so we can't just copy and submit, but the main idea is totally correct. I think if the prompts were further elaborated, the code will follow those instructions too.)
Thanks for such a great contest. I loved it
How to solve C?
Can anybody please tell me why I'm getting WA on test 4? Submission
With
1 <= a[i] <= 1e6then these may not work:int abc = (v[i]*100)+(v[i+1]*10)+v[i+2];int _ab = (v[i]*10)+v[i+1];int _bc = (v[i+1]*10)+v[i+2];int _ac = (v[i]*10)+v[i+2];I think you can use
pairinstead of combining into a singleintvalue.G was pretty similar to this problem: 1526C2 - Potions (Hard Version)
I had a strong feeling that i have seen G like problem before, seems to be this.
Orz it's really the same
Great contest, but I think that problem A could have been written in a better way: there are too many people who did it after 10 mins, meaning that the statemenet was not clear at all. Something like "an app can only be placed on a single screen" would have been enough. I was (wrongly) thinking of application on multiple screens, so that, e.g. 4 screens could contain 15 y app. Hope next time I'll be sharper in statement comprehension
Please explain why D is failing on test 4 261864972.
Can someone explain why my solution 261888809 with $$$N=10^5$$$ failed, but the same solution 261919448 with $$$N=$$$$$$\sum\limits_{i = 1}^mh_{i}$$$ passed in 1974E - Money Buys Happiness where $$$N$$$ is the maximum number of elements in $$$dp$$$ array. I guess my time complexity is $$$O(N*M)$$$ which should pass. And what does this statement It is guaranteed that the sum of $$$\sum_{i}h_{i}$$$ over all test cases does not exceed $$$10^5$$$ means?
I got the same TL as you because I initially did dp with $$$5 \cdot 10^4$$$.
The problem is $$$t \lt = 1000$$$, so taking in your case dp till $$$10^5$$$ will make the worst case of $$$10^5 \cdot 10^3 \cdot 50 = 5 \cdot 10^9$$$, which is too much. (in my case it was twice less, but still too much).
But taking $$$N = \sum_{i = 1}^m h_i$$$ resolves this, cuz then the worst case will be $$$m \cdot \sum_{i = 1}^t N_i$$$, but we know that sum of all $$$N_i$$$ over $$$t$$$ cases is not greater than $$$10^5$$$, then the worst case will be $$$50 \cdot 10^5 = 5 \cdot 10^6$$$ which is good enough.
Oh yeah, now I realised when you mentioned it, basically overall time complexity is $$$O(T*M*$$$$$$\sum_{i}h_{i})$$$ and they have mentioned that $$$(T*$$$$$$\sum_{i}h_{i})$$$$$$\leq10^5$$$ so worst case will be $$$5*10^6$$$ which is fast enough whereas in my case, it will be $$$5*10^9$$$ which is TLE. Thnx mate.
C was unusually hard for Div3. E was nice.
Hopefully back to blue after this one.
I got the correct intuition for C but then I thought HashMap<Integer,HashMap<Integer,HashMap<Integer,Integer>>> must not be the intended solution, should have continued
You can also do it using 1 TreeMap<Triple, Integer>. (TreeMap cus ez to write a comparator for triple). Use -1 to represent a "hole"
Yeah, even I did something similar to that. 261823516
Is E solvable using recursive dp?
I've solved it using iterative DP https://mirror.codeforces.com/contest/1974/submission/261897619
I found this submission which uses recursive dp : https://mirror.codeforces.com/contest/1974/submission/261868908
Questions C and D Detailed Video Editorial
English C : https://youtu.be/wGj3J4W50HA D : https://youtu.be/c6U-YiF0MCo
Hindi C : https://youtu.be/8Sd-qodaa7w D : https://youtu.be/hduAMjuv9co
Problem B is getting too many successful hacks. Can someone tell me what seems to be the problem with the solution approach of those who are getting hacked.
what they did wrong was they declared the answer as an empty string and instead of pushing m[s[I]] back , all of them added it to the current string and replaced the current string. This made each operation having a cost of i(current) length , giving the end time complexity of O(n^2)
Wrong approach => ans = ans + map[s[i]]
Correct approach => ans.push_back(map[s[i]])
That is completely misstatements. ans = ans + mp[s[i]]; doesn't lead to O(n^2) complexity.
Actually, I tried to change one of hacked submission this way and it worked. Sad that it wasn't caught by our max test.
unordered_map is easily hackable. Don't know what's wrong about default map solutions.
can we solve E with recursive dp ?
I would appreciate your kindness if any of you could just debug my code for E, Thanks. https://mirror.codeforces.com/contest/1974/submission/261937456
TL can occur because you loop through $$$10^5$$$ values in dp on each test (look at this https://mirror.codeforces.com/blog/entry/129611?#comment-1150814). Change to the sum of $$$h_i$$$.
I still get TLE, please have a look, sir. Submission link after changes
It seems that you use
memset(dp,-1,sizeof(dp)), the complexity of which is the size ofdp, thus $$$5\times 10^6$$$ approximately.If you do this whenever you process a test case, as the total number of test cases can be $$$1000$$$ , you reach a total complexity of $$$1000\times 5\times 10^6=5\times 10^9$$$ , which is clearly wrong.
good round, especially like F and G this round.
20 lines of code for problem D
link
who less?
Little suggestion to turn 20 lines of yours to 15. Check this part:
Simplify it to
for(char c: ss) pm[c]++;. Easier debug this way too.XD You are right. I missed that. Thanks
Only if I wouldn't have spent so much time on C :(
for Problem E, is it the right approach to find the minimum number of money required to obtain x amount of happiness given i months using dp?. And then check what is the maximum possible happiness for which he can pay the money.
Yeah. it's right. I did the same way.
Thats great.Can you please explain what were transition eqn. you wrote, I am not able to find bug in my code
knapsack
as a knapsack dp, there is 2 option.1. if i buy the happiness of the index , i must have a[index] value now , and must have the to money to buy remaining happiness from next indexes, as i can store this k for next indexes , substituted k from next dp cost.
My ugly solution for D, but it works.
C and D are much tougher than regular Div3. Btw, a tip for the likes of D is jotting down all possible negative cases first, then either deal with the correct one or a much more trivial yes-or-no decision making.
Btw, anyone having a hint for G? I have a few ideas but I'm afraid I was overthinking at contest...(Nvm, I read a comment above and realized I was way too stupidly overthinking... T.T)Thanks for the contest! The problems were of pretty good quality as compared to recent div3 rounds. Hoping to reach Expert by the end of main tests!
implementation forces with too easy G. E and F were better imo.
What are some approaches that can be used to solve F? I was thinking either some sort of dp or something with geometry. That is to say, we somehow determine the number of points in a bounding box, and each cut makes this bounding box smaller. Then, by keeping a record, we can determine the numbers of points obtained for each cut. Or are these ideas a bit to "direct"?
It's direct, but it's kinda the motive of it. When moving the bounding box, you'll figure the points that would be left out of the box.
Maintaining those points would require a sorted data structure with add/find/delete operation — as this data structure should add the points initially, find the points that are before/after a certain threshold, and delete those points. Still the number of points in the original box is quite large, so these operations should be fast enough instead of a naive linear one in array. For my most convenience, AVL/RBtree-based data structures (i.e.
setat C++ andTreeSetat Java) should work well enough.Can you explain your idea of how you deleted elements from the opposite dimension. I mean, if the move is U or D, how did you deleted those coordinates from the data structure where the coordinates are stored optimally for L/R operations (if you even are using a 2nd DS for that matter) ?
First, my solution, just in case my words were unclear.
We'll store two different sets for two dimensions, each will store a tuple $$$(x_i, y_i, i)$$$, and sorts them accordingly by the dimension defined. Thus, each point has two copies: one at the L/R set, the other at the U/D set.
If cutting from a dimension, for example L/R, we can list the tuples that would be excluded from the L/R set, thus getting their indices in the process. With the indices, we can reconstruct the corresponding tuples from the other U/D set, and delete them as well. With this, each tuple will only be accessed/constructed/deleted twice at most, keeping everything $$$\mathcal{O}(n \log n)$$$ just fine.
That's so concise and clear. Thanks for explaining!
Oy blin I had fun this round. E was pretty, unfortunately I couldn't solve it.
The naming of problem 'E' is really interesting!!!
I read so many comments about C being too hard. Can anyone tell me what was so hard about it? Wasn't it a simple map count problem? If it were Div.2 I would've used better hashing just to be more sure.
I think it's not very easy to come up with the idea of counting each pair (1-2, 2-3, 1-3) individually, as well as it's not something you'll see much in easier problems to count a pair or a tuple as a whole. If you're used to such problems then it's easy, but not for most (like, 2/3 of the official participants) who need to challenge 3C problems.
Ohh! Okay!! Great learning opportunity then.
For problem G, can someone please spot the error in this code . I am trying to use a multiset to store the costs at which happiness has been bought and then using the upper_bound function.
You are removing the hapiness with cost just greater than the one you are inserting in else
if(!s.empty())condition.. you need to erase last element of s ieauto it=s.end(); s.erase(--it);Thanks
Just had a look at the problems and Kudos to the authors for constructing such a great problem-set. I absolutely loved the similarities/differences (and their implication) between problems E and G.
hey MikeMirzayanov what is this partial behaviour towards flagging solutions.
This user -> looneyd_noob is out of competition for the solution: https://mirror.codeforces.com/contest/1974/submission/261894175 but i also noticed the solution of this user -> Shaxx19 who is not out of the solution even having a very similar solution just variable name changed and some comments added and even submitted 10 minutes later; this is his solution https://mirror.codeforces.com/contest/1974/submission/261900757 the entire nested for loop is same with same indentation. Man he needs to get out of contest, you are doing very wrong and people's trust will reduce from this platform. Please get him out of competition.
hey MikeMirzayanov what is this partial behaviour towards flagging solutions.
This user -> sjy is out of competition for the solution: https://mirror.codeforces.com/contest/1974/submission/261826313 but i also noticed the solution of this user -> frank11_sjy who is not out of the solution even having a very similar solution just variable name changed and some comments added and even submitted later; this is his solution https://mirror.codeforces.com/contest/1974/submission/261825867 the entire nested for loop is same with same indentation. Man he needs to get out of contest, you are doing very wrong and people's trust will reduce from this platform. Please get him out of competition.
yes there are various cases i noticed also like @sjy @rohan786 @frank11_sjy @kovi05007 who seem to have similar maybe they use ideone
Hope this is their first mistake, hope mike can cancel their div3 competition score and give a penalty warning
Bro, I want to ask if MikeMirzayanov will solve it if I complain here.