Привет! В 20.05.2024 17:35 (Московское время) начнётся Codeforces Round 946 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Раунд основан на UKIEPC 2024: Spring Practice. Пожалуйста, воздержитесь от участия в этом раунде, если вы знакомы с задачами этого соревнования.
Большое спасибо:
Авторам оригинального соревнования: Aksenov239, MaxBuzz, RobinFromTheHood, darnley, izban, pkhaustov, lsantire, az453, fedor.tsarev, Shoaib Jameel.
MikeMirzayanov за помощь с дополнением набора и системы Polygon и Codeforces.
-is-this-fft-, peltorator, tute7627 за красное тестирование раунда.
senjougaharin, kaikey, gmusya, nskybytskyi, Giga_Cronos, diskoteka за жёлтое тестирование раунда.
TypeYippie, kzyKT, tepamid, ahshafi за фиолетовое тестирование раунда.
Abo_Samrah, Zandler, sam07a, YESMAKHAN, xygzy, Klaus26 за синее тестирование раунда.
Morvolzz, dasha..zhilina, sutekine, Muhsen, Gojova, Acanikolic73 за бирюзовое тестирование раунда.
Вам за участие.
Всем удачи!
UPD: Разбор опубликован.
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!
As a tester, I hope you to enjoy the contest. Tasks are quite interesting and educational. Good luck!
thanks for contest. I am exciting
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
i also got this same error, if u get the solution to this let me know
Good round, come and participate.
Another Vladosiya round!!!
hoping to return back the blue handle
I hope that I will be aque 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.
orz
Hope i can solve till E this time
Waiting for this contest. Thanks codeforces
OMG Vladosiya Round! <3
OMG Vladosiya Round!
I hope I'll become pupil this time
Looking forward to an AK, and GLHF to all participants, rated or not!
you guys are doing so good... i'm trying my best just to stay at pupil
Hope to reach cyan this contest : >
дадут ли мне рейтинг если я участвовал и решил более одной задачи в двух контестах? сейчас мой рейтинг 600+
Today is a good day for the score
Mewing cat ready for the contest
bye bye
time for green
good luck for everyone:)
Hope for a good contest.
Best wishes everyone <3
wishing all GL , Hope i will become green in this round
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://codeforces.net/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
I tried knapsack. It gave Memory Limit Exceeded.
Any better way to do it? My code: https://codeforces.net/contest/1974/submission/261922894
its actually because we can't have current money as our 2nd state in dp because x<=1e8 as a result 50*1e8 will always give MLE. we have to use happiness as our 2nd state of dp
I'm struggling to write a recursive dp for the above-described state $$$dp_{idx,happiness}$$$. I've looked into many submissions but all of them have iterative dp solutions. It would be great if I could get a recursive dp solution. I tried to define $$$dp_{idx,hp}$$$ as maximum money I can have from $$$idx...n$$$ with happiness $$$hp$$$
More or less.
I have nice solution for C, using custom comparator for std::map. It came very handy. You may have a look :- https://codeforces.net/contest/1974/submission/261857159
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
that's a $$$O(N^{2})$$$ time complexity , you should try less
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.
I also thought of the same approach, but spent a lot of time implementing it and miscalculating
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.
Ah , got it .. Thanks
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.
For me 4th was easier than 3rd. I solved the 3rd one but wasn't able to optimize it. I just needed few min to submit 4th.
I paired up N with S and E with W. For each pair, I assign either both H or both R. For example, if some pair of N and S are assigned H, then they cancel out, and they effectively do not move the helicopter.
There will be unpaired ones left over. We just have both the H and R assigned to an equal number of unpaired ones for each direction, then they will end up in the same position. If H and R have equal of each, then that implies that the total number of unpaired ones must be even for each direction. For example, if we have NENNNE, then there are 4 N and 2 E, so we just let H and R have 2 N and 1 E each. NENNEE is not possible, because there are odd N, or odd E.
the easiest solution would be to just follow the moves of other robot and brute force it. there is one specific case when following solution won't work and that is when we have one movement of each direction each. we can handle that separately. here's my submission
I took more than one hour to solve D
Почему в последнее время див3 такие сложные
Please add an option to filter out non-official (* asterisk) contestants. How can we see the real standings without such an option
There is a checkbox called "show unofficial" on the top right corner of the standings page, untick it
Thanks!
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
when I have difficulty in understanding the statement i directly go to the example, and I think the example was clear
Took me some time but using set and map kind of helped.
Yeah the wording of that problem tripped me up too. I interpreted it as each character in string r acts as a key with the value as the symmetrical character in string r. Then search each string s character in the hashmap to find its decoded character. It worked in the end
I was only able to understand it because of the illustration that was provided.
There is a picture in the problem statement that explains it
AHHHHHHH....should've tried 4th instead of wasting time on 3rd.
Yeah, you're right. Thankfully I thought of this soon enough to solve D, otherwise I would have not been able to solve either of them in time.
Hardest div 3 ever implementing C takes a lot of time and even D is also tough to implement
exactly , D took lots of conditions to print correct answer , it should be yes / no type with C and C should be D.
I got tle in D couldn't optimize
i tried c problem with hash, wasn't much difficult to implement. but i got intituion for d but couldn't implement it. a lot of conditions were there
I also implemented C with hash map by making pair of two elements of a triplet as key and another element of triplet as value,But I overcomplicated to optimise more.
D is very tricky to implement because of the condition that each device must execute at least one instruction.
yeah in c u can manage 4 maps string key and int value, where first map denotes triplet starts from a[j],a[j+1], second map triplet end a[j+1],a[j+2] third a[j] and a[j+2] and fourth having triplet itself. so at any position we can get total triplets.
for refrence:
unordered_map<string,int> m1; unordered_map<string,int> m2; unordered_map<string,int> m3; long long ans =0; for(int i=2;i<n;i++) { string s1 = to_string(a[i-2])+","+to_string(a[i-1]); string s2 = to_string(a[i-1])+","+to_string(a[i]); string s3 = to_string(a[i-2])+","+to_string(a[i]); string s4 = to_string(a[i-2])+","+to_string(a[i-1])+","+to_string(a[i]); long long a1 = 1ll*m1[s1]; long long a2 = 1ll*m3[s2]; long long a3 = 1ll*m2[s3]; long long a4 = 1ll*m1[s4]; // finding all triplet ans+=(a1-a4)+(a2-a4)+(a3-a4); // updating tripletes m1[s1]++,m3[s2]++,m2[s3]++,m1[s4]++; }i got d but after the contest done lol !!!, like we can just manage their states of R and H
Problems were kinda hard according to div3
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
nvm got it
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!
I hoped Brute Force would work on Problem C with 4s Time Limit but NOPE...
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 :(
failed to solved d, was able to get intution. couldn't code it
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
Not getting what is wrong with my memoization solution of E: 261908791
Appreciate the help if anyone could.
D 261878026 seemed easier to implement than C 261849652. My C almost took 1.2 secs. I think it might get hacked lol
My solution for C uses four maps and an idea of inclusion and exclusion. But I couldn't solve D in +1 hour.
261867166
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...
Bruh your last contest was on March 1, and you haven't participated since then and complain??
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://codeforces.net/contest/1974/submission/261840334
Any idea how to do this faster? https://codeforces.net/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 wish that problems next time be less implementation T_T
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.)
Problem G was a pretty standard priority queue problem. After taking current happiness if the cost becomes higher than the money we have. We have to remove some happiness we prevously take. Which one should we remove ? Of course the most cost happinesses.
I gave problem E to GPT-4, and after 2-3 attempts it come up with an almost correct answer, and then i provided some hints and i got the correct answer.
Here is the almost correct solution
and here is the correct solution
But don't get the wrong idea, I didn't use CHATGPT during Contest, nor do i want to suggest using it. I just wanted to check the capability of GPT-4 for dynamic programming problems.
Any insights into why this submission is giving an incorrect result for test case 5: 261917349
You can use
long longinstead ofint.Just realized and got ac, 'integer overflow' destroyed this contest :(. Didn't even spent time on D which was very much implementation only.
Problem C is nice, I was so intense solving it, switched to C++ after getting MLE with Haskell, couldn't make it in time but still made my day.
Thank you guys for a nice contest!
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.ohh shit. I misread the constraint :(
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
I am unable to figure out why my C is failing
https://codeforces.net/contest/1974/submission/261920538
It fails on 1110 testcase on Unit Test 2.
mine fails on 1108 in the same testcase
https://codeforces.net/contest/1974/submission/261872195
i spent so much time on this problem :(
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 <= 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.
idea of D was simple but implementation was ugly..
Problem C and D sucked the living soul out of me. Took whole 2hr to solve them. Really hard for a Div3.
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"
Your solution is amazing
Thank you :)
Yeah, even I did something similar to that. 261823516
Is E solvable using recursive dp?
i implement recursive dp but it gives a wrong output my dp state is dp[index][buy or do not buy]
let me know if you were able to solve it using recursion or any other dp state
I've solved it using iterative DP https://codeforces.net/contest/1974/submission/261897619
I found this submission which uses recursive dp : https://codeforces.net/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.
How does an O(n) solution lead to a TLE hack in particular?
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 someone explain the second last given test case of problem E?
you can buy 2,3, and 5th tokens to get maximum happiness.
Okay now i see, i understood the question completely wrong. Thanks
'C' is quite tricky implementation!!!
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://codeforces.net/contest/1974/submission/261937456
TL can occur because you loop through $$$10^5$$$ values in dp on each test (look at this https://codeforces.net/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.
Thank you for the contest codeforces! Newbie here...Felt C was bit harder compared to D , anyone else?
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)It was the coolest Div. 3 that I have ever done. However I did it well, I solved A-D tasks.
In my point of view, C was way harder than D. I did a ugly implementation with a giant code.
I expect to get green.
Thanks for the contest !!!!
well-balanced div3 round, but i stucked D ;-;
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.
My solution for problem-D assign first N-S to Robot and E-W to Helicopter and track the positions.
My Solution
A good Round. But i think F>G
i got a problem with the submission i submitted the code but till now it is showing as it is in queue can u check it once
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!
lets go!!! pupil coming back. thanks for this round. my solution to D is way too stupid and I don't even have a solid proof/reasoning on why it passes but AC is AC. Getting Pupil back with specialist performance. Lets go!!!!
Oy blin I had fun this round. E was pretty, unfortunately I couldn't solve it.
Great
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.
The early rating updation nowadays means, the system has been updated.
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
Can someone point out why this JAVA solution for problem
Cis getting TLE? solution_linkI have implemented it using
HashMapand a similar solution written in C++ has got accepted.Update: Accepted using
TreeMapin 3874ms :( linkHere you go, an implementation for problem F :-
https://codeforces.net/contest/1974/submission/262012373
This required me custom camparator for std::set and good use of upper_bound() and erase() of std::set.
Dear Codeforces Team,
I want to address the issue regarding my solution (ID: 261392643) for problem 1973B, which has been flagged for similarity with many other submissions. I assure you that I did not share or receive code from anyone. Here's my explanation:
Independent Work: I wrote my solution independently and did not share it with others. Common Approach: The problem might have a common solution approach many programmers use, leading to similar code. No External Sharing: I did not use any public code-sharing platforms like ideone.com.
Additionally, my solution (ID: 261370439) for problem 1973A has been flagged without any issue or information. If needed, I can provide more details about my approach to solving the problem to demonstrate my independent work. I am committed to fair play and integrity in this competition.
Thank you for your understanding.
Best regards, redbear_
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.
I wrote my code on ideone, and hence might have been the reason.If needed, I can provide more details about my approach to solving the problem to demonstrate my independent work. I am committed to fair play and integrity in this competition.
Thank you for your understanding.
hey MikeMirzayanov what is this partial behaviour towards flagging solutions.
This user -> looneyd_noob is out of competition for the solution: https://codeforces.net/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://codeforces.net/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.
I noticed that someone has raised concerns regarding the similarity between my solution and another user's solution, and is requesting my disqualification from the competition.
I would like to clarify that my solution is indeed my own work. Any similarities to other submissions are purely coincidental, as the nature of coding often leads to similar logic and structures when solving the same problem. I have added proper comments to demonstrate my understanding of the code, which the other user hadn't.
I would like to ask who I should complain to if I find someone who submitted the same code as me in the competition. I want to cancel the score changes for both of us at the same time to ensure the fairness of the competition.
hey https://codeforces.net/profile/MikeMirzayanov
hey MikeMirzayanov what is this partial behaviour towards flagging solutions.
This user -> sjy is out of competition for the solution: https://codeforces.net/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://codeforces.net/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.
This kind of thing happened and I hope 945div3 doesn't give me a rating, but no one seems to care about this game anymore
my rating decreased to the rating that I got in the my 2nd last contest WHY ??
All of a sudden, my ratings got rolled back few hours ago! I wasn't notified of anything. The points just disappeared.
@MikeMirzayanov