AlexSkidanov's blog

MemSQL start[c]up Round 2
By AlexSkidanov, 11 years ago, In English

Hello everyone!

The second round of MemSQL start[c]up will take place on August, 3rd, 10:00am PDT. There will be two contests running simultaneously, one for people who participate onsite, and one for everybody else who advanced to the round two. Both rounds share the problemset and are rated based on the combined scoreboard.

Onsite participants will have special prizes for first three places. All onsite participants as well as the top 100 in the online contest will receive a start[c]up t-shirt.

People who have not advanced to the round two can participate in the round unofficially. Unofficial participation will be rated.

The contest will be 3 hours long, and will feature 6 problems. The score distribution is 500-1000-1000-2000-2500-3000.

The problem set has been developed by MemSQL engineers pieguy, nika, exod40, SkidanovAlex and dolphinigle.

Good luck and happy coding!

UPDATE: Editorial is up!

Announcement of MemSQL start[c]up Round 2
  • Vote: I like it
  • +138
  • Vote: I do not like it

Comments Comments (77)
| Write comment?
»
11 years ago, # |
  Vote: I like it +28 Vote: I do not like it

are other people allowed to join unofficially for fun? maybe in a separate room?

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

    Will be div2 edition?

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

      Div2 participants are welcome to register for the round unofficially, but the problemset might be too hard for them. Expect problems A and B to be comparable to Div2-C and problem C to be as hard as Div2-D or E.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it -29 Vote: I do not like it

        It's ok, I think most of Div.2 participants could solve at least two problem in this contest.

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

    Yes, it will be possible to participate unofficially.

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

is it rated for Div2 participants?

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

    Yes

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

      That's not exactly the answer to the Haghani's question. AlexSkidanov only stated, that round will be rated for those not advanced from round 1

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

      I hope all the commentators could give your reasonable comments. I don't know why this comment(just contains a "Yes", and it's a fact) got two "down"s.

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

    It will be rated for all the users.

    We welcome Div2 users to participate, but if you register for the round, please be advised that this problemset is not designed for Div2 participants, and you might end up with 0 problems, which will result in a significant loss of rating.

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

      if i register but don't attempt any problem, then will i loss point? is there pretest as usual cf?

      Edit: (i asked about rating, cz, there was a notification while registering, it said something like:- "it will not easy for div2, u may loose point, do u still wish to register?" )

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

        u won't...but the rating isn't the most important thing.Just have fun. at least you can do better than me,LOL

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

Hello I have a question.

How can I register the online contest officially if I have advanced to the round two?

According to the statement above, both official and unofficial online participators need to register the online version. I assume the system will automatically recognize the official particpator (who passed the round 1), am I correct?

Thank you

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

    Yes, it automatically registers those who have not advanced to round 2 for the unofficial track. After you register, please double check, than in the list of registrants you do not have a star symbol next to your handle (star symbols means registered for the unofficial track).

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

Are unofficial participants competing for T-shirts?

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

Hope a good contest for div 2 participants ;)

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

What does the "Unofficial participation" mean? What kind of participants will be considered as unofficial participants.

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

    People who have not advanced to the round two can participate in the round unofficially. Unofficial participation will be rated.

    If you register for an online round, but you have not advanced to round 2, your participation will be unofficial (in the dashboard and the scoreboard such participants are marked with a star).

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -31 Vote: I do not like it

      Thank you.And Will there be round-3? If so, a man who have not advanced to the round 2 but get a high rank in round 2 unoffically, can he participant in round 3 as an offical participant?

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

is it for sql language,

or we can participate in any language

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

Anyone know why profile page says "The page is temporary blocked by administrator." ?

Edit: after system tests it keeps msg as before..

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

    Because when a contest is running they blocked some pages that are not necessary at this moment.

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

    I think it block it until the rates change completely

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

when is the rating changed

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Could anybody tell me some smaller input so that I could figure out the mistake in my code for B. It was hacked on some large random test case when it was possible to have a subsequence of length 100. http://codeforces.me/contest/335/submission/4223108

In that case my code prints out some non printable character. I am unable to figure out why ?? Any help would be appreciated !!

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

    Small inputs: "a" "aa" "aaa" "aaaa" "ab" "abc" "aba" "abac" "abcbabcc". (This isn't meant as a joke, I really used that to debug my solution :D)

    Just write a random generator and make your own input(s). It's hard to find a tricky case here, anyway, so any random string should do.

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

      Oh, it was a silly kind of mistake.
      string t;
      t += s1;
      t += s2;
      where s1 and s2 are two characters
      is not equivalent to
      t += s1 + s2;

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

    "abababababababababababababababababababababababababcbababababababababababababababababababababababababa"

    (101 characters in the string, 100 characters in the solution)

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

Why doesn't multiset in STL have such common operations? Just to find the maximum and the second largest number?

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

    What's wrong with *--st.end() and *----st.end() ?

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

      Multiset, not the set. And many numbers will be same.But I want the second largest number strictly. For example, 5 5 4 4 3 2 1 MAX 5 The Second Largest 4

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

        You can use map with values equal to the number of occurences of each key.

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

        I din't think you need element strictly lower.

        In that case you may use *--st.lower_bound(*--st.end()).

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

      So we must use BBT

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

    It does.

    set<int> st;
...
set<int>::iterator it=st.end();
int mx=*(--it); // max
int mx2=*(--it); // second largest
    → Reply
»
11 years ago, # |
  Vote: I like it -19 Vote: I do not like it

no one solved problem F. I am curious to know the approach of this problem. btw it was very gud contest. :) :)

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

When will we be able to register for practice?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -47 Vote: I do not like it

    i dont know why this comment was ratting +.while my comment is usefull more

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

i solved B in O(n^2) by using the fact that there are only 26 variety of characters. if n >= 3000 then there is a character that has occurred more than (3000/26) >= 100 times.

so I print a string with length 100 with only this character if n < 3000 then the problem would be the same as LPS (longest palindrome subsequence) which is solvable in O(n^2) if don't think this was the intended solution

and problem C is very similar to problem SGU 328. but with lower constraints (it is solvable in O(R))

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

    I think your solution for problem B is the intended solution, that's why the 100 constraint is there.

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

      Probably. I didn't come up with that solution but a different one with complexity O(100n) that doesn't depend on the number of types of characters.

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

        Sounds like your idea is better than quadratic. Because with 500 types of symbols it would be necessary to process whole length of string (50000). Could you explain in short words?

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

          Let F(i, j) is the maximum index k > i such that we can obtain a palindrome of length 2 * j from characters in [1, i] and [k, n] (j characters in each part).

          Actually, we also need to know the maximum index of occurrences that is less than k for each type of characters. In my submission 4225240, I construct a table in O(26n) for finding in O(1). In case the number of character types is large, this can be handled in O(log(n)).

          So, overall complexity is O(100n + 26n) or O(100n log(n)).

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

    Ken Ichi Kawarabayashi would say: "100 is a constant, alphabet's size is a constant, so B can be solved in constant time" :P

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

Thanks a lot for these nice, short and clear problems.

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

Why the problem-setters' nicks point to topcoder profiles instead of codeforces profiles?

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

Thank you for onsite competition!

It was perfect!

And congratulations to Seikang who won poker tournament!

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

Thanks for the contest and the onsite event! (great problems, awesome people, and tasty pies) Thanks for the poker lessons. I finally learnt! (and for the prize XD)

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

    I'm glad you liked the pies (that was the true prize, of course).

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

      +1 key lime pie, ping pong and beer :) Thanks MemSQL !

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

    Damn! I missed the pies while walking around San-Francisco :(

    BTW, I also enjoy the event very much but I still think that my performance was quite poor and I got the prize spot only by luck.

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

    The onsite event was great indeed! Thanks a lot.

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

    Yes, it was great! I played the poker first time and it was funny :)

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

Will any editorial be published? I would gladly read solutions to E and F.

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

Thanks to MemSQL engineers for your contest. I was an offical participant (passed round 1) and finish the online contest with rank 74 (solved 2 problems). So when and how can I receive a T-shirt?

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

    We will be sending them out shortly. Someone will contact you to confirm your t-shirt size and address very soon.

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

when would the editorial be published？

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

    Yes, dolphinigle is polishing it up right now and will publish it as soon as it is ready.

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

Any news about the T-shirt?

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

is there anybody knows something abouth T-shirts?

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

Has anyone received their t-shirt yet?

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

I've received my shirt now as well. Thanks for this!

→ Reply