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.
http://apps.topcoder.com/forums/?module=Thread&threadID=920041
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.
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?
My bad! Sorry!
Match Starts in 25 mins! :)
Thanks all for participating — Here are the editorials : https://www.topcoder.com/blog/single-round-match-735-editorials/
Woah, he died? What happened?
He had a car accident. Really sad news...
My condolences.
Rest in peace, ltaravilse
Reminder: The contest starts in about 2 hours! :)
@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?
Drop an email to me — harshit @ topcoder.com and we will take care of it :)
Same happened with me...should i also send a mail?
Yes:)
FML. Didn't read that 250 has only a and b as characters, and spent almost the whole contest on it.
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.
If anyone finds out how to solve the problem for a three character alphabet, I'm interested to know.
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.
Well, you can't make a smaller partition for a string
abc, so the answer can equal 3.UPD: and for string
abacbcit's possible to divide it into 2 palindromes, but not using your algorithm.Yeah that's why I mentioned the 1 and 3 answer cases are straight-forward.
Upd : For the abacbc my algo doesn't work.
A B A B A C A
for second solution:
abcbaac
answer is 2
#MeToo
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.
Hard seems to be similar to https://icpc.kattis.com/problems/money?
Yeah, also noticed that, passed now in practice.
Div 2C is exactly this problem: https://www.codechef.com/problems/CHEFDOMA/
Sorry about that. Didn't know about this problem and nobody noticed during the preparation.
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.
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
Same. I was feeling really dumb seeing everyone has done it for > 240 pts and I am clueless even after 50 minutes.
So, should your submitted solution works for any string?
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.
First (non-college) contest where I won money and it's a whooping $200! YAY!
Liked the round and really excited :D
do you donate?
Do you ever post with your real account?
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).
http://codeforces.com/blog/entry/12079 (thanks to I_love_Tanya_Romanova)
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.
Regarding 732, wasn't it already known that both mine and his solutions are wrong?
I knew yours was wrong, but not yet if his was.
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 :(
Why did you switch to cpp for the last problem btw?
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.
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.
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.
I did not recall the problem until jqdai0815 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!