hmehta's blog

By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 777 is scheduled to start at 11:00 UTC -5, Feb 03, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Prizes — Top 2 members on the Div I leaderboard will be awarded $777 each.

Thanks to Witaliy for writing the problems. Also thanks to misof and lg5293 for testing the problem set and coordinating the round.

This is the fourth SRM of Stage 2 of TCO20 Algorithm Tournament and TCO20 Regional Events Qualification

Stage 2 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs

Update: Congratulations to the brothers! — neal and scott_wu for winning $777 each!

Some Important Links

Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What about div2?

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Is there a way to set the Topcoder arena to light mode permanently? Currently it goes back to dark mode again every time I go there.

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

    Arena has light mode?!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, that was lucky. I was sure at least one of my submissions would fail. >40+th to 10th place

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Can someone suggest what's wrong with such dp for d1-500, please?

upd: I don't check if $$$s[i-1]=s[i-2]$$$... It's not the only problem though

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

    Does it even fit in memory?

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

      Umgh, yes, why wouldn't it?

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

        Ah, I miscalculated by the factor of 10, sorry

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any solution of Med better than $$$\mathcal{O}(N^3)$$$ using bitsets?

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

    $$$O(N^3)$$$ without using bitsets? It's better in a way. (The number of state transitions has a good constant since we delete pairs of characters, and cache friendliness is decent.)

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

      It's hard to come up with a test where it is really $$$N^3$$$. Passes system tests in <0.03.

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

    Sure, I have quadratic solution. We can remove a segment of $$$A_0A_0A_1A_1 ... A_kA_k$$$ between B and C if either As, B and C include all colors or $$$B = A_0 = A_1 = ... = A_i$$$ and $$$C = A_k = ... = A_{i + 1}$$$. Now for each position in t we will go from left to right and store potentially suitable positions (s_j = t_i) in deque. If we then find some position for which we find it possible to match previous prefix of t, we check if we can delete everything between either end of deque and that position (if we can, remove corresponding end, set corresponding position as good and repeat). Of course we will empty our deque if we have to non-equal chars.

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

how to prove that the answer for div1 250 is less than $$$10^7$$$, if it's not -1 ?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div2 Medium?

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

    Divide the string into blocks of equal letters. You can never erase a block completely, but you can always erase it down to the last one or two characters (based on parity) by using one character from an adjacent block and three from your block.

    Special case: if all letters are the same, you cannot erase anything.

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

      Hi, this is the solution I ended up coming up with, but I was distracted looking for a DP solution for awhile.. I noticed others in my room had a DP solution but failed system testing. Does a DP sol exist?

»
5 years ago, # |
  Vote: I like it +91 Vote: I do not like it

I have no idea why in Easy every case (except default=1) has a solution. I checked it by running all possible tests, but I want to know if there is good proof.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -17 Vote: I do not like it

    No, determining whether all integers eventually appear in the sequence is an open problem, even for the case defaultValue = 0. See https://en.wikipedia.org/wiki/Van_Eck%27s_sequence

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

      So what was the purpose of including this problem into the contest?

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

        What's wrong with including this problem? We see problems in competitive programming that rely on open problems (Collatz conjecture, Goldbach's conjecture, etc.) all the time.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +37 Vote: I do not like it

        Thanks for your comment (downvotes for providing correct information are sometimes hard to interpret correctly, even though in this particular case I did have a strong suspicion about what the reason might be :p ).

        I do like the problem, and I'll be glad to explain why.

        First, these sequences themselves are cool and bringing attention to them using a competitive programming problem is a good thing in my book. Patterns like this one, the more famous Collatz sequence, cellular automata, Busy Beaver Turing machines, Langton's ant, etcetera, etcetera, are scattered all over computer science and they all carry an important message about the world we live in: very small deterministic systems can often produce complex chaotic behavior that is hard to describe. Building up intuition for when this kind of behavior can occur is a useful tool for a computer scientist, and problems like this can contribute to that.

        Second, the problem itself is perfectly fair. It has exact constraints and within those constraints it is correctly solvable. We do not need to rely upon any unproven results.

        Third, it's not a new thing in programming contests either. There have been similar problems before. The one I liked most was a problem based on Langton's ant, but I was unable to find it now. I think it was most likely from a Polish (or maybe Russian?) ICPC-style contest. The problem was about having some small initial configuration of a variant of Langton's ant and having to tell its position after 10^18 steps. The core of the problem was that solvers had to either know or discover via simulation that in this particular model the initial chaotic behavior eventually always terminated and turned into periodic one. Problems like that are cool, and I think they absolutely do belong here, even if the underlying mathematical problems about the general case are still unsolved.

        Fourth, when compared to regular stuff you get at the div1 easy level, the problem is in some sense much closer to what some of us do in actual research. In practice you won't get a nice gift-wrapped toy problem with a solution, you are given a problem to solve and you need to use algorithms as tools to solve it. In this case, the problem was to investigate the behavior of the sequence, make an assumption about said behavior, realize that with a good implementation you have enough resources to verify that assumption using exhaustive search, do so, and submit. Going through this process of thinking and implementing stuff correctly isn't hard, but it isn't trivial either, and div1 easy still seems like an appropriate judgment of the difficulty involved.

        Wow, that came out longer that expected. Kudos to everyone who actually read this far. TL,DR: I think the problem is OK and I tried to explain why I think so.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So what is the official solution for Div1 medium ?

I think I had something like best[i][j] if you can match s[1..i] to t[1..j], and when you skip characters from s they need to pair up + you can't skip characters from s if t[j] == t[j-1] (But this is N^3)

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    This is my solution during testing:

    Let's get the run length encoding of both sequences, and call each of these parts a block. A block has a color and number. If there is only one block in T, then T and S must be the same.

    It helps to look at things backwards as adding characters from T to S. Each block in T must correspond to a compatible block in S, where a block in T is "compatible" with a block in S if it has the same color, it has the same parity, and the number is equal or less.

    If we look at the matched blocks of S, we must somehow generate everything else, and this is several independent problems between matched blocks. We can figure out when we can generate everything in between two already matched blocks in S. We can solve this with a little case work, and find out this is possible if the two blocks are already adjacent (nothing to generate), or all blocks in between have even size and the colors, including endpoints, don't alternate between only two colors (this can be proven with induction).

    This leads to a dp solution, dp[i][j] -> true iff we can match first i blocks in T with first j blocks in S. For a fixed i, we sweep from lower j to higher j and keep track of some information to figure out if all previous blocks between the last possible matched position are even size and don't alternate. You can see the code for more details.

    code
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong in N*N*3? My solution got challenged. Your text to link here...

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

    You seem to return NO for "GRRBBR", "GR"

    Problem is you make your removals always right to left

»
5 years ago, # |
  Vote: I like it +61 Vote: I do not like it

Brothers get money

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

    When you are a target and finish second in the world, but your big brother still beats you :(

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Did anyone managed to open the Stage 2 TCO20 Points Leaderboard? I tried three different times (in different dates and times) and every time it times out trying to fetch the results.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to do 1000?

EDIT: Conceptually it's not too difficult (although somewhat annoying to implement). Just maintain a data structure that supports the following operations for a fixed $$$d$$$ modulo $$$10^9+7$$$. Assume that $$$a[-1]=a[-2]=\cdots=0.$$$

  • Add $$$x$$$ to $$$a[i]-a[i-d]$$$ for all $$$0\le i\le y.$$$
  • Compute $$$\sum_{i=0}^ya[i].$$$