Hello CodeForces Community!
We would like to invite you to our next monthly contest and we’re sure you’ll enjoy — the September Lunchtime 2018 sponsored by Sharechat! Get ready for a three-hour test of your coding brains and pit yourself against the best. And there’s more! We have exciting full-time job opportunities by ShareChat for professionals across the globe. More details can be found on the September Lunchtime contest page.
Joining me this time on the problem setting panel are:
Problem Setter: kingofnumbers (Hasan Jaddouh)
Problem Tester: teja349 (Teja Vardhan Reddy)
Editorialist: taran_1407 (Taranpreet Singh)
Statement Verifier: Xellos (Jakub Safin)
Russian Translator: Mediocrity (Fedor Korobeinikov)
Mandarin Translator: huzecong (Hu Zecong)
Hindi Translator: Srijan Dubey
Bengali Translator: solaimanope (Mohammad Solaiman)
Vietnamese Translator: VNOI Team
Contest Details:
Time: 29th September 2018 (1930 hrs — 2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://www.codechef.com/LTIME64
Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes:
- Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie. (For those who have not yet received their previous winning, please send an email to winners@codechef.com)
Good Luck! Hope to see you at the contest!
I am thinking about hosting a stream soon after the contest to discuss the tasks from the contest.
What is your opinion on it?
Incase there is good response from community, I will host a stream discussing problems from the contest.
Stream Details:
I will be starting the stream at 10:40 pm IST ( 10 minutes after the contest) at https://www.twitch.tv/teja349 . I will try to take questions after solving each problem. I see there is a lag close to 1 minute on twitch. Is there a way to get rid of it or maybe my system resources cannot process,
Youtube link: https://www.youtube.com/watch?v=GJfD2PEY7pA .
Comments and suggestions are most welcomed!!
I think streaming is a very good idea.
Good opportunity to prove that you are not a robot
Incase you feel stream will be helpful. Upvote this comment.so as to get some quantitative idea.
Will streamed video be available after live streaming?
I just hope the Codechef Server doesn't go down during the contest.
+1 for stream. :)
Nice problems.
Although not mandatory, but an explanation of sample should be given as it really helps.
Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
How to solve "Match the Streams"?
I was using sqrt-decomposition with map to store frequencies of element, but it gave TLE for second subtask.
You can map integers from sequence b before queries, all other values can be same as 0.
P.S. I was doing this task for 2+ hours and still I didn't get AC :D
Yeah I did same and then sqrt decomposition..Total complexity was
, but it gave TLE :(
Nope, my complexity is
. You can have next value for each block cnt[i][j] ( amount of numbers i in block j).
allllekssssa sorry if that's too trivial, but isn't
ican be upto 109, which you can't store in cnt[i][j], and I don't think coordinate compression will help here because there's an incoming stream of c's...can you please elaborate a bit more on your approach or post your code.
The main trick is mapping only elements from sequence B, all other values are not important for result and can be equal to 0. Now you will have at most 105 different mapped elements, and each will be in interval [0, 105].
How will you calculate this array cnt[i][j], go over sequence B and when you come to element Bi, then
++.
Update queries can be easily handled, for whole block i current answer is same as cnt[c][i], for edge blocks just go over all important position and change answer.
You can see my code down in some of the next comments.
My solution AC-ed with BlockSize=750.
why? Isn't block size of 320 sufficient?
No, my solution is O(Nlog(X)/X+X) per query. For N=100000, optimal X would be ~750.
can you provide some hints for your solution
You can make it in
(or even 
if you use hash map):
I have 10-15s delay. Connecting through ethernet helped. It was worse via wi-fi. And don't use big high FPS, I guess.
The problems were nice, but the testcases were really weak. I got AC on 2 questions with a randomised approach.
COINPART problem got accepted with randomised approach, but which is the other one?
You must change something on site, it is too slow for normal contest!
I am usual participant of Cook Offs/Lunchtimes, but this is too much for my nerves, and I seriously think to stop it after this bad experiences with site.
Tasks were interesting!
yes, even after the contest end, some of the content is too slow to open.
Biased Juded Problem was really nice. I wish that problem was on codeforces, hundreds of hacks would have been there including mine (:( ) on not realizing that the minimum time limit was supposed to be equal to 1.
I got TLE on fourth task with time>3sec. I submited the same code after contest and I got AC for 1.15 sec. I really think problem is not in my submission and solution.
If someone would check my last submission for MATCH2, I would be really thankful.
Can you tell why my code is giving TLE. for match2 According to me complexity will be (N+Q)log^2(n); https://www.codechef.com/viewsolution/20389388
please provide the links of submissions.
Here are submissions: TLE AC
I will send those submissions to the technical team
Let me also share my fault during the contest, for 1st problem directly I wrote Q*log(N) solution and submitted, but unfortunately it gived TLE and I shocked, try to find my mistake for 10 minutes and decided to submit same code again, but this time passed in 0.12 sec. p1 and p2.
I can't find it in problem statement of problem Biased Judgement, so I will ask it here. Can we test problem on an empty subset of tests?
yes, it's allowed but we decided remove test-case where choosing empty subset is the only correct output because we noticed that wasn't clear from statement and we couldn't change the statement because it was already late and statement was already translated to many languages.
Can you tell why my code is giving TLE. for match2 According to me complexity will be (N+Q)log^2(n) https://www.codechef.com/viewsolution/20389388
I created a segment tree with map on every node So build time O(Nlog^2(N)) and per query time O(N log^2(N))
Same code got AC with fast IO :( https://www.codechef.com/submit/complete/20397847
Test cases of problem BJUDGE were weak particularly in Subtask #2 and that is the reason a lot of people managed to score 70 with incorrect code.
Please update the test cases in at least the practice version of the problem. teja349
The editorials for first four problems are ready and will be available once admin moves them to public. Editorials for last two would be available within one day.
Hope you all had a great contest.
Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
I am getting runtime error in Match2. Can anyone help me in finding error? Solution link
Hi, teja349. I am doing the problem MATCH2 with sqrt decomposition. I have two code that is identical except for one line, but they did not behave as expected. Would you like to help me check them? I think it might be related to the compiler on the Codechef.
In this submission 1, I asserted "br < 349" on the 35th line and got passed. However, in this submission 2, I asserted "br < 350" on the same line but got runtime error. I felt somehow lost. Would you like to do a favor to help me figure it out?
Thanks in advance!
Any other's help will also be appreciated :)
Undefined behaviour or they changed tests, I guess.
https://www.codechef.com/viewsolution/20373923 and https://www.codechef.com/viewsolution/20400424
What's the difference? One got TLE 1s while the other one got AC 0.17s. Thanks for making me spend extra time to write a solution without map.
Edit:
https://www.codechef.com/viewsolution/20377308 and https://www.codechef.com/viewsolution/20377751
What's the difference? One got CE while the other one was able to compile.
That's surely weird! I will report this to technical team.
Can't the problem "Biased Judgement" have multiple solutions? e.g. For the sample testcase 1, the time limit could have been any integer greater than 7 seconds.
Yes it could have multiple solutions and you were allowed to print any of them. Just make sure that your solution will allow all submissions i with d[i] = 1 to pass and j with d[j] = 0 must fail
If so, it should have been mentioned in the problem statement, wasted a lot of time trying to figure out a unique solution :/
How to solve Coin Partition?