### teja349's blog

By teja349, history, 3 years ago,

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: Discombobulated (Taranpreet Singh)

• Statement Verifier: Xellos (Jakub Safin)

• Russian Translator: Fedosik (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.

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:

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,

Comments and suggestions are most welcomed!!

• +58

 » 3 years ago, # |   +58 I think streaming is a very good idea.
•  » » 3 years ago, # ^ |   +66 Good opportunity to prove that you are not a robot
 » 3 years ago, # |   +238 Incase you feel stream will be helpful. Upvote this comment.so as to get some quantitative idea.
•  » » 3 years ago, # ^ |   +27 Will streamed video be available after live streaming?
 » 3 years ago, # |   +46 I just hope the Codechef Server doesn't go down during the contest.
•  » » 3 years ago, # ^ |   0 "Due to too many requests, we have temporarily taken down this page. Please bear with us. Thanks." Just like me, it seems they also knowingly coded brute force approach to harder problems in designing codechef. Just in case...
 » 3 years ago, # |   0 +1 for stream. :)
 » 3 years ago, # |   0 Nice problems.
 » 3 years ago, # |   +23 Although not mandatory, but an explanation of sample should be given as it really helps.
 » 3 years ago, # |   +8 Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
 » 3 years ago, # | ← Rev. 2 →   +25 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.
•  » » 3 years ago, # ^ |   0 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
•  » » » 3 years ago, # ^ |   0 Yeah I did same and then sqrt decomposition..Total complexity was , but it gave TLE :(
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +1 Nope, my complexity is . You can have next value for each block cnt[i][j] ( amount of numbers i in block j).
•  » » » » » 3 years ago, # ^ |   0 allllekssssa sorry if that's too trivial, but isn't i can 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.
•  » » » » » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 My solution AC-ed with BlockSize=750.
•  » » » 3 years ago, # ^ |   0 why? Isn't block size of 320 sufficient?
•  » » » » 3 years ago, # ^ |   +1 No, my solution is O(Nlog(X)/X+X) per query. For N=100000, optimal X would be ~750.
•  » » » » » 3 years ago, # ^ |   +6 can you provide some hints for your solution
•  » » 3 years ago, # ^ | ← Rev. 3 →   +1 You can make it in (or even if you use hash map): Code#define all(x) begin(x), end(x) int sm[4 * maxn]; int to_push[4 * maxn]; vector sgm[4 * maxn]; int build(int v = 1, int l = 0, int r = n) { if(r - l == 1) { sgm[v] = {b[l]}; return sm[v] = (b[l] == a[l]); } else { int m = (l + r) / 2; build(2 * v, l, m); build(2 * v + 1, m, r); sgm[v].resize(r - l); merge(all(sgm[2 * v]), all(sgm[2 * v + 1]), begin(sgm[v])); return sm[v] = sm[2 * v] + sm[2 * v + 1]; } } int cnt(int v, int c) { return upper_bound(all(sgm[v]), c) - lower_bound(all(sgm[v]), c); } void push(int v, int l, int r) { if(to_push[v]) { sm[v] = cnt(v, to_push[v]); if(r - l > 1) { to_push[2 * v] = to_push[2 * v + 1] = to_push[v]; } to_push[v] = 0; } } int upd(int a, int b, int c, int v = 1, int l = 0, int r = n) { push(v, l, r); if(a <= l && r <= b) { to_push[v] = c; push(v, l, r); return sm[v]; } else if(r <= a || b <= l) { return sm[v]; } else { int m = (l + r) / 2; return sm[v] = upd(a, b, c, 2 * v, l, m) + upd(a, b, c, 2 * v + 1, m, r); } } 
 » 3 years ago, # |   +8 I have 10-15s delay. Connecting through ethernet helped. It was worse via wi-fi. And don't use big high FPS, I guess.
 » 3 years ago, # |   +54 The problems were nice, but the testcases were really weak. I got AC on 2 questions with a randomised approach.
•  » » 3 years ago, # ^ |   +3 COINPART problem got accepted with randomised approach, but which is the other one?
 » 3 years ago, # | ← Rev. 2 →   +59 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!
•  » » 3 years ago, # ^ |   +1 yes, even after the contest end, some of the content is too slow to open.
 » 3 years ago, # |   +5 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.
 » 3 years ago, # | ← Rev. 2 →   +16 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.
•  » » 3 years ago, # ^ |   0 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
•  » » 3 years ago, # ^ |   +8 please provide the links of submissions.
•  » » » 3 years ago, # ^ |   +8 Here are submissions: TLE AC
•  » » » » 3 years ago, # ^ |   +8 I will send those submissions to the technical team
•  » » 3 years ago, # ^ |   +18 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.
 » 3 years ago, # |   +16 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?
•  » » 3 years ago, # ^ |   +8 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.
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   0 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))
•  » » » 3 years ago, # ^ |   0 Same code got AC with fast IO :( https://www.codechef.com/submit/complete/20397847
 » 3 years ago, # | ← Rev. 2 →   +20 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
 » 3 years ago, # |   +5 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.
 » 3 years ago, # |   0 Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
 » 3 years ago, # |   +8 I am getting runtime error in Match2. Can anyone help me in finding error? Solution link
 » 3 years ago, # |   +19 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!
•  » » 3 years ago, # ^ |   0 Any other's help will also be appreciated :)
•  » » » 3 years ago, # ^ |   +19 Undefined behaviour or they changed tests, I guess.
 » 3 years ago, # | ← Rev. 2 →   +11 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:What's the difference? One got CE while the other one was able to compile.
•  » » 3 years ago, # ^ |   0 That's surely weird! I will report this to technical team.
 » 3 years ago, # |   +3 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » 3 years ago, # ^ |   +3 If so, it should have been mentioned in the problem statement, wasted a lot of time trying to figure out a unique solution :/
 » 3 years ago, # |   +3 How to solve Coin Partition?