Блог пользователя hmehta

Автор hmehta, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +44
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

What about div2?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    $$$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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2 Medium?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится +91 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +40 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +37 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

Brothers get money

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +63 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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].$$$