hmehta's blog

Topcoder SRM 735 in memory of ltaravilse
By hmehta, history, 6 years ago, In English

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.

  • Vote: I like it
  • +240
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Woah, he died? What happened?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    He had a car accident. Really sad news...

    → Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

My condolences.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Rest in peace, ltaravilse

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Reminder: The contest starts in about 2 hours! :)

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

@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?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    Drop an email to me — harshit @ topcoder.com and we will take care of it :)

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +38 Vote: I do not like it

FML. Didn't read that 250 has only a and b as characters, and spent almost the whole contest on it.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      If anyone finds out how to solve the problem for a three character alphabet, I'm interested to know.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it -6 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it +11 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it -11 Vote: I do not like it

            Yeah that's why I mentioned the 1 and 3 answer cases are straight-forward.

            Upd : For the abacbc my algo doesn't work.

            → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          A B A B A C A

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          for second solution:

          abcbaac

          answer is 2

          → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    #MeToo

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Hard seems to be similar to https://icpc.kattis.com/problems/money?

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Div 2C is exactly this problem: https://www.codechef.com/problems/CHEFDOMA/

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Sorry about that. Didn't know about this problem and nobody noticed during the preparation.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Same. I was feeling really dumb seeing everyone has done it for > 240 pts and I am clueless even after 50 minutes.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So, should your submitted solution works for any string?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

First (non-college) contest where I won money and it's a whooping $200! YAY!

Liked the round and really excited :D

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do you donate?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +75 Vote: I do not like it

      Do you ever post with your real account?

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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).

    → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

http://codeforces.net/blog/entry/12079 (thanks to I_love_Tanya_Romanova)

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Regarding 732, wasn't it already known that both mine and his solutions are wrong?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I knew yours was wrong, but not yet if his was.

      → Reply
»
6 years ago, # |
  Vote: I like it +95 Vote: I do not like it

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 :(

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Why did you switch to cpp for the last problem btw?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      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!

      → Reply