hmehta's blog

By hmehta, history, 3 months ago, ,

The entire Topcoder team was saddened to hear of the loss of ltaravilse.

ltaravilse was an integral part of the Topcoder family. He was a member for over 10 years, a member of our Community Advisory Board (CAB), and was a huge help in getting our first TCO Regional event to visit South America.

SRM 735 and TCO18 Round 2C on Tuesday, June 26, 2018 will be run in his honor and will award $5,500 in prizes in honor of ltaravilse. The prizes of$200 will be awarded to best 20 performers in Div-1 and the prizes of $100 will be awarded to best 10 performers in Div-2.$500 will be awarded for TCO18 Round 2C participants. More details to come... All members will be given an option to donate their prizes to the family of ltaravilse.

The rounds are scheduled to start at 07:00 UTC -4 on June 26, 2018. You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go. Click here to see what time it starts in your area.

Thanks to majk for writing problems for the match.

Topcoder Java Applet Setup Guide : https://drive.google.com/file/d/1gVJZxhWYMuUNx3PfSSTkkk-b9AeJkL4j/view

If you are participating from the web arena, you will be able to switch between the rounds as mentioned below.

•
• +240
•

 » 3 months ago, # |   +36 I'm so sad to hear that ltaravilse past away, but... I think it's not SRM 736, instead it's SRM 735. Actually SRM 735 isn't held yet. Or the order has changed?
•  » » 3 months ago, # ^ |   +2 My bad! Sorry!
•  » » 3 months ago, # ^ |   +14 Match Starts in 25 mins! :)
•  » » 3 months ago, # ^ |   +15 Thanks all for participating — Here are the editorials : https://www.topcoder.com/blog/single-round-match-735-editorials/
 » 3 months ago, # |   +42 Woah, he died? What happened?
•  » » 3 months ago, # ^ |   +40 He had a car accident. Really sad news...
 » 3 months ago, # |   +7 My condolences.
 » 3 months ago, # |   0 Rest in peace, ltaravilse
 » 3 months ago, # | ← Rev. 2 →   +22 Reminder: The contest starts in about 2 hours! :)
 » 3 months ago, # | ← Rev. 2 →   +9 @hmehta ,I registered in SRM 735 instead of TCO round 2C. when I go to register there, the dialogue box in the right displayed already registered but after the start of the contest, it displayed that you are not registered so I ended up participating in SRM 735. Pls, could you consider my advancement(if my solution passed) as per my points in SRM, in round 3A?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +9 Drop an email to me — harshit @ topcoder.com and we will take care of it :)
•  » » » 3 months ago, # ^ |   0 Same happened with me...should i also send a mail?
•  » » » » 3 months ago, # ^ |   +5 Yes:)
 » 3 months ago, # | ← Rev. 4 →   +38 FML. Didn't read that 250 has only a and b as characters, and spent almost the whole contest on it.
•  » » 3 months ago, # ^ |   0 Yeah . I also did the same but figured it out a bit earlier. But I was thinking how should we approach it if it didn't have only 'a' and 'b'.I was thinking of finding for every character the farthest matching character. But I was stuck at choosing the subsequence properly.
•  » » » 3 months ago, # ^ |   +9 If anyone finds out how to solve the problem for a three character alphabet, I'm interested to know.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   -6 For 3 character alphabet I think this might work : answer is either 1,2 or 3.Now for 1 and 3 it is fairly straight-forward.For 2 — remove all a's and check if the remaining string is a palindrome. Similarly remove the b's and c's.I don't have a proof for it. But I believe this may work.UPD : As mentioned below this doesn't work for all cases.Solution 2 : For cases with 1 and 3 the approach is same. For 1 find if string is palindrome. For 3 group all a's , b's and c's together. We can find the Largest Palindromic Substring for the string and remove the characters that form the LPS. Now check if the remaining string is a pallindrome.This is however O(n^2).One greedy O(n logn) solution I can think of is : Initially have an array of size n with all values as 0. Now for each index i from 0 to n find the rightmost unmarked index j such that s[i]=s[j] and i<=j and add the it to a treap with value j-i+1 at position i. Initially let the interval be from 0 to n-1. Choose the interval with maximum size and let it be from x to y. Now repeat the process for x+1 to y-1 and y+1 to n and keep on doing it till the range size becomes <=0. These form the subsequence 1. Now check if the remaining string is a pallindrome and if yes the answer is 2.The reason I use a treap here instead of a segment tree is that this can be extended for larger alphabet sizes.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +11 Well, you can't make a smaller partition for a string abc, so the answer can equal 3.UPD: and for string abacbc it's possible to divide it into 2 palindromes, but not using your algorithm.
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   -11 Yeah that's why I mentioned the 1 and 3 answer cases are straight-forward.Upd : For the abacbc my algo doesn't work.
•  » » » » » 3 months ago, # ^ |   0 A B A B A C A
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 for second solution:abcbaacanswer is 2
•  » » 3 months ago, # ^ |   +42 #MeToo
•  » » 3 months ago, # ^ | ← Rev. 2 →   +17 You should read all previous round 2X: 250s always are too easy. If you can't solve in 5 minutes, then you might misunderstand or miss something.
 » 3 months ago, # |   +11 Hard seems to be similar to https://icpc.kattis.com/problems/money?
•  » » 3 months ago, # ^ |   0 Yeah, also noticed that, passed now in practice.
 » 3 months ago, # |   +12 Div 2C is exactly this problem: https://www.codechef.com/problems/CHEFDOMA/
•  » » 3 months ago, # ^ |   +9 Sorry about that. Didn't know about this problem and nobody noticed during the preparation.
•  » » » 3 months ago, # ^ |   +23 By the way, you don't really need Fenwick trees in this problem, because at each step the query value changes by exactly 1. You can just add/subtract the frequency of the corresponding value. It might be worth mentioning in the editorial.
 » 3 months ago, # |   +19 I'm such a dumbass. I noticed that string in problem A can only consist of letters 'a' and 'b' only when I read others solutions
•  » » 3 months ago, # ^ |   +24 Same. I was feeling really dumb seeing everyone has done it for > 240 pts and I am clueless even after 50 minutes.
•  » » 3 months ago, # ^ |   0 So, should your submitted solution works for any string?
•  » » » 3 months ago, # ^ |   0 I had submitted some random shit one minute before the end of the contest and it passed tests. Unfortunately, it doesn't work for any string.
 » 3 months ago, # |   +30 First (non-college) contest where I won money and it's a whooping $200! YAY! Liked the round and really excited :D •  » » 3 months ago, # ^ | 0 do you donate? •  » » » 3 months ago, # ^ | +75 Do you ever post with your real account? •  » » 3 months ago, # ^ | +16 Same here .. except that I'm getting 100$ as it's my first contest on topcoder (and I even didn't know about the prizes before the contest).
 » 3 months ago, # |   +8
 » 3 months ago, # | ← Rev. 2 →   +8 Haha, I got AC on 1000 in practice after swapping the order of 2 lines in my in-contest submission. The difference is that for all elements of B negative, when the answer is clearly a 1x1 matrix, my code also ignored too many 1x1 matrices... due to a break statement I used to keep it from being too slow when the answer is positive. I even briefly thought about what it does when the answer is negative, but decided not to bother since there wasn't enough time.Btw, I was messing with SRM 732, 800pt problem, PawnGame, and managed to hack pashka's (the winner's) solution too. That makes 0 out of 2 solutions that passed systests there correct.
•  » » 3 months ago, # ^ |   0 Regarding 732, wasn't it already known that both mine and his solutions are wrong?
•  » » » 3 months ago, # ^ |   +1 I knew yours was wrong, but not yet if his was.
 » 3 months ago, # |   +95 So judging by the editorial, you were aware that the hard problem is mostly the same as the 2017 World Finals problem "Money for Nothing", and still gave it for the SRM? That sounds a tiny bit suboptimal :(
•  » » 3 months ago, # ^ |   +12 Why did you switch to cpp for the last problem btw?
•  » » » 3 months ago, # ^ |   +8 My Java O(N**2) solution was a tiny bit too slow, after rewriting it in C++ it ran in 3.5s on the worst case.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 This problem evolved from the statement and not from the solution. Only then I realised that I have already seen the last step somewhere, but the problem still looked interesting enough. I consider the modeling in the problem non-trivial and the technique used in the WF problem relatively standard/known. I may be wrong in both assessments.Do you think that the number of solvers/their score would be substantially different if it had not been for the World Finals problem? Did you personally recall the problem during the round?I hope you enjoyed the round nevertheless.
•  » » » 3 months ago, # ^ |   +5 Well, my solution (as I mentioned above, AC after fixing a small bug) is O(N2) that utilises randomness and the fact that it's harder to come up with countertests to a whole class of solutions if they take hyperparameters. Up to the point with stack-filtering obviously bad points, it's the same, but then I bruteforce through all pairs (right point, left point), breaking the inner loop if the remaining choices for left point can't give a better answer than the current maximum.
•  » » » 3 months ago, # ^ |   +36 I did not recall the problem until OO0OOO00O0OOO0O00OOO0OO pointed it out after the round ended, and I could not solve it from scratch, instead squeezing in a quadratic solution, so the technique is definitely non-standard for me :)I can't say if it affected the results significantly, my disappointment was more philosophical than practical.Indeed, I have enjoyed the round — thanks for putting it together!