Hello, Codeforces!
I and 0x4F5F6F have curated a Solo Practice Contest in the gym, [contest:105005]. The level of questions is medium. This is for anyone who loves giving contests and solving problems. This contest will be of most interest upto Expert rated coders, but I would also like to invite Div. 1 coders to participate as well. For anyone who wants to practice or just wants to go through the problems can register for our contest here. Hope you will enjoy solving the problems!
I would like to thank:
our problem setters AdityaDargan, -tsukasa-, BitWizz and myself.
our problem testers 0x4F5F6F, AdityaDargan, -tsukasa-, BitWizz and myself.
myself for the amazing poster design.
Contest Details:
- Date/Time: [contest_time:105005]
- Problems: 6-7
- Duration: 2 hours 15 minutes
- Contest Invite: Invitation Link
We hope that this contest, regardless of your background, rating and result, will increase your exposure to competitive programming and make you better than you were yesterday. Have fun!
Note: You can also register for the contest while it is going on. You may want to check out our group for past contests.
UPD1: The registration has started!
UPD2: We have made the contest private, you can access the contest with this link.
UPD3: We are really sorry to say that G was comparable to one of AtCoder's problem. In the future contests, we'll make sure this doesn't happen again. But we can agree on the fact that rest of the problems were actually interesting and quite fun to solve!
UPD4: Congratulations to the winning contestants!
Congratulations to first solves as well!
- A: pattagobhii
- B: tt12
- C: Tobo
- D: UP84
- E: pasricha_dhruv
- F: cpchenpi
- G: cpchenpi
UPD5: The editorial is now available here!
Let's follow the trend of photo of the authors :)
As a problem setter, I feel you would enjoy solving the problems !!
As a problem setter, I feel you would enjoy solving the problems !!
As a participant this time, I feel I would enjoy solving the problems!!
I JUST HOPE I DONT STUCK IN STARTING PROBLMES ......
Excited for Coding Challenge Alpha V. Thanks to the organizers and problem setters for creating this opportunity to enhance our skills.
Wow. Excited!
As a problem tester, I really liked the problems and highly recommend everyone to participate in the contest !
Nice problems, any ideas for F?
expand x into r-l+1 and rearrage the terms to make something meaningful
Problem G is exactly the same as this atcoder problem from abc342 which was held on 24th feb (Literally 10 days ago).This is just LAZY.
and here is the problem E (very much similar) click me
they didn’t even change the samples :(
We are really sorry to say that G was copied from AtCoder. This was definitely not expected from our side, and our testers did their best, but unfortunately they were unknown that this problem exists. Had if I tested, I would've identified G as I participated in that contest.
In the future contests, we'll make sure this doesn't happen again. But, I am pretty sure we can agree on the fact that rest of problems were actually interesting and quite fun to solve!
How to Solve D?? When Editorial will be Published ?
Use Two pointer and then find number of Thala substring ending at Right index
void solve() {
}
How to solve C ? ;-;
Irish army can fire at the positions which are from l-k to l+n-1+k. so you have to kill the german soldiers in that range and all of them should have +ve strength and at max n germans soldiers should be killed.
Editorial : Problem A :
It's not hard to notice that if we have x same kind of stones, then we will need at least x boxes. So the answer is maximum frequency of any element in the array.
void __jaiShreeRam() {
}
Problem B:
Since we have to take the shakes from a single shop, so we will move to each shop and will try to find how many maximum shakes we can buy from that particular shop with the amount of money we are having.
No. of shakes we can buy from i'th shop will be : min(a[i], money/price) And we will take the maximum of each shop
void __jaiShreeRam() {
ll money,q; cin>>money>>q;
ll ans = -1, ind_ = 1;
ll shakes = 0;
while(q--){ ll a,m; cin>>a>>m;
}
cout<<ans<<'\n';
}
Problem D:
I was completely exhausted today in my work, Internship e.t.c so my brain was not able to figure out the approach during the contest because I haven't focused on constraints and alphabets. I've also asked the solution for D above but later on I was able to figure out the solution and I have done it in simpler manner than the guy explained above. By the way Thanks to him for explaining.
Let's fix the left point of my substring [l,r] for now. Now think how much do we have to traverse for r ?
There will be at max 26 alphabets, and we want 7 char as max. So In worst case we have to check for at most 26*7 = 182 . So my r will be from l+1 to min(n,l+182). After this max frequency will become 8.
So we will iterate over l and check for r how far we go and getting the substring with at max 7 freq. of any character. To check this we can maintain a vector of size 26.
void __jaiShreeRam() {
}
cout<<ans<<"\n";
}
Problem G :
You must be familiar with the data structure SEGMENT TREE.
We can use Segment tree to solve this. And each node of segment tree will store 3 things left(left point of the segment), right(right point of the segment) and a multiset, in which we will store the values of each segment. So that after cancellation we can restore the state of the array.
Now Just process the queries. if query is of type 1 then add the element x by updating the multiset. if query is of type 2 then remove the element and restore the state by removing element from multiset if query if of type 3 then print the maximum by querying max from segment tree.
This Problem is Very interesting. Try by yourself so that you can improve your understanding of segment tree.
I'll share the code also If you want. So please do reply if you are facing any issues in Implementation