hmehta's blog

By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 762 is scheduled to start at 07:00 UTC -4, July 3, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to teja349 and Errichto for writing and Vasyl[alphacom] for testing the problem set.

This is the fifth SRM of Stage 4 of TCO19 Algorithm.

Stage 4 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 763 — July 17, 11:00 UTC-4

Good luck to everyone!

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

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

The link of Stage 4 leaderboard is not working

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

There is a typo. Should be 762 and not 761.

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

how to solve Strawberry?

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

    I guess it can be solved by polynomials polynomial multiplication with $$$O(n \times k \sqrt{k}))$$$.(reference: link from GeeksforGeeks)

    But it definitely is not what the solution of writer...

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

    I solved with time complexity $$$\text{O}(nk^2)$$$. I guess it is not intended. The practice room system test shows that it passed in 4.9s while the TL is 5s.

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

      I tried to TLE you and got -25. :( Then my 250 failed from not seeing the length 200 constraint and now I am last place.

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

        I also tried to TLE another solution with the same time complexity since I don't believe mine will pass. Then got -25 as well. :)

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

      I got 5.0s in practice room

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

      I tried hacking a couple of O(NK^2) solutions but they both failed :(

      You can replace the inner dp with fft to get a runtime of O(N*Klog(K)).

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

        How can you do FFT? $$$10^9 + 6 = 2 \cdot 500000003$$$.

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

          Just compute on doubles ;p

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

          It could be non-obvious, but:

          1. Calculate the convolution modulo $$$7 \cdot 2^{26} + 1, 5 \cdot 2^{25} + 1, 45 \cdot 2^{24} + 1$$$.
          2. Use Garner's Algorithm to retrieve the value modulo $$$10^9 + 7$$$.
          With my implementation with using Montgomery Reduction while multiplying in two modints, it passed in about 0.3 seconds in max testcase.
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            How were the three numbers in step 1 chosen?

            Is the idea that the three numbers P, Q, R in step 1 are pairwise coprime, and that PQR is so large that the answer modulo PQR is equal to the actual value of the answer?

            Or am I missing some relationship between P,Q,R and $$$10^9+7$$$?

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

              Yeah, the idea is the same as you mentioned. Here is the condition

              • At least $$$PQR > (M-1)^2 \cdot N \simeq 1.4 \cdot 10^{22}$$$ should hold, because of the maximum possible value of after-convoluted value. So we need at least three integers if we use 32-bit.
              • I used the algorithm called Number Theoretic Transform (NTT). This only works in mod $$$p$$$ when $$$p$$$ is the prime of form $$$c \cdot 2^d + 1$$$ where $$$d$$$ is the least integer that is $$$2^d \geq N$$$.
»
5 years ago, # |
  Vote: I like it +57 Vote: I do not like it

I'll have a rant this time, for a change.

Div1 250 would have been a nicer problem with $$$n$$$ up to $$$200$$$. Test generators in the statement generally reduce problem interest, especially when the problem is not that hard.

Unintuitive and inconsistent test generators (state taken modulo $$$2^{31}$$$ after use in Div1 250, but before use in Div1 500) don't add value to the problemset. Combined with weak samples, they just add frustration for the contestants.

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

    Also in Div1 250:

    • We have to choose the lexicographically smallest sequence $$$B$$$, and only then prepend the length and return.

    • We have to reduce the length of $$$B$$$ to 200, but the returned length must be the original length.

    • There are no examples to check we got the above points right.

    All in all, the problem is a minefield, and not in an interesting way.

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

    But Div1 250 with $$$n \leq 200$$$ can be solved with a very easy $$$O(n^2)$$$ DP...

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

      Sure, but consider two scenarios:

      1. Give the problem as it is.
      2. Give it with $$$n \le 200$$$.

      Is then contest in scenario 1 really better than in scenario 2 overall?

      If the problem is that much more interesting when only the linear solution is allowed, the author may consider using it on a platform which fully supports it, without the generator in statement and without output truncation.

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

        The linear solution is the reason to have this problem. I'm sorry its beauty got spoiled by the workarounds needed for the platform. Honestly, I dislike having to do them as much as you all do and I really hope we'll finally get to use a decent backend soon.

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

          If you are using test generators, why not to give a big example?

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

            There should have been one, and it's a mistake that there wasn't one. Sorry.

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

          I see how the problem is better when it's $$$O(n)$$$. Just, if the author is not locked into writing for TopCoder exclusively, they could use it elsewhere, and come up with another problem which suits TopCoder format better. There are many problems which lose little, if anything, when they are constrained in "olde TopCoder style", with $$$n$$$ up to 50 or so. Would be a win-win.

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

            I wholeheartedly agree. It's very important to think which platform is best for your problem. Big constraints aren't good for Topcoder. If some statement is very long or it describes an existing process/game/whatever that some people know and some don't, it might be a good idea to use it in a long contest like the 10-day contest in Codechef. In Codechef, I also used some problem with local python interactor that was given to contestants and they could use it without hurry. Subtasks are good for OI-style competitions etc.

            It's ofc. easier to distribute problems like that when having some experience but you should still try. In most platforms, it's ok if you just propose one problem btw.

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

            I think 250 was ok if big example test was provided (but you may have made a mistake in your solution that made you dislike it compared to others), we have seen similar output format before even long time ago.

            500 was not ok though. I would buy this "educational" thing a bit if TopCoder was producing any education content (with FFT tutorial for example). But they haven't produced any new content in ages, so better stick with what is common knowledge in Algorithms.

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

The missing constraint that the resulting array should have positive integers is an important part of the Div 2 500 problem. It took me a while to figure out what to do with elements that were not included in the restriction and lost some points. Though I earned 250 points for challenging other solutions.

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

Wow, return only first 201 elements. What a great technology!

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

After submitting the Div.1 250 pt, I recall that I forget the constraint that we need to just return the first 200 elements as what I do in TCO 18 round 4.

And in the challenge phase, I get 200 points from others by bug about this constraint...

I think the constraint is terrible and affect final rank too much.

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

I was writer for the 5 problems (apart from Div1 Hard). I am sorry for many things. I think this is lowest I have ever felt with my mistakes in preparing tasks.

Firstly Div1 Med,

I should probably have stuck to NTT instead of Karatsuba, But we felt NTT might be harder for people so we went with Karatsuba. And I as a stupid compared times of both my Java n*k*k solution and n*k^1.6 and felt it was fine(instead of using an optimised C++ solution).

Now, Div1 Easy, I missed the condition (Aprefix.length < = n)in checkData, which sadly no one noticed. (:

Hope you liked the questions. Thanks for participating!

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

    Why do you want to set such a straightforward Karatsuba/NTT problem?

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

      You are not the target group for the problem. People who are now learning the technique are. From time to time, straightforward $technique problems are needed for all techniques, so that other people can learn and practice the stuff you already know. If all the problems on $technique use it in complex ways, it makes learning harder.

      If you already know it well, the problem should have been straightforward for you to give you more time to try to solve the hard.

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

        OK. So maybe I can send such problems to TC:

        given two polynomials, output their product.

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

          That's unfair, and you know it.

          This is nowhere near the same situation. Here you still had to do the correct modeling of the process described in the statement, discard unneeded parts of the polynomials after each multiplication, and reverse directions appropriately. In order to do that, you need to understand what the algorithm actually does instead of just blindly using a black box.

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

            bad problem for topcoder: multiply two polynomials

            good problem for topcoder: generate using given generators two polynomials and after that multiply them

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

              And then print the xor of the coefficients, I think u forgot this

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

                probably some formula with long long overflow in it instead of xor will suit more.

                of course, without any examples on it.

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

                  return the length then min(200, size) elements in it XD

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

            discard unneeded parts of the polynomials after each multiplication, and reverse directions appropriately

            This sounds very silly, and I think one doesn't need to be red to think as such. I agree the modeling is nontrivial, but it's still straightforward.

            However, I liked the Hard. Thanks to Errichto for a nice problem.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +136 Vote: I do not like it
        • I agree that this problem requires some observation. At least we first need to find $$$O(nk^2)$$$ solution (which is d2 hard), and also need to understand that the transition is of the same form as convolutions. Still, we need to compare the ratio between technical parts and observation parts. We can say that a problem with level 1 known technique and level 2 observation is good, but a problem with level 10 known technique and level 3 observation is completely straightforward. I believe 90% of the difficulty of this problem comes from FFT with arbitrary modulo (which is more advanced than a simple FFT) and thus I don't see much difference from sunset's exaggeration.

        • I also agree that problems that (almost) directly ask the knowledge of advanced techniques are valuable for educational purpose. However, please don't put them in rated d1 contests. There are other places for them — online judges, CF edu rounds, ABCs, etc. (personally I try to make ARCs more idea-oriented.) Speeds on d1 meds have great impact for reds too. What's the main factor of the speed in this problem? Preparedness of your pre-written FFT. (Do you have NTT or just double FFT? or you have a code for arbitrary modulo? Do you have Karatuba instead?) It's not interesting if the ratings of reds are greatly affected that way.

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

      I do not know if I can say it was straightforward NTT (maybe for you it was very obivous). I felt it was a good problem for the Div1 Med level (only some 35 odd people did it (even in them I think there are few optimised bruteforces which passed.)). why do you think if someone found it to be straightforward, try to write optimised bruteforce?

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

        Because 17 * 7k * 7k = 833m, and you gave us 5 seconds.

        Assuming the author is not that good at setting TLs (which turned out to be true), it seemed reasonable to consider this problem just an exercise on modular arithmetics and dp with probabilities, something like a 450-pointer to move on to the hard problem.

        If you wanted only a o(n*k*k) solution, you definitely needed larger limits.

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

          Its not 7k, but 14k?

          Anyways, I surely agree it was my mistake as I said above.

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

            Yep, my fault. And still we see both C++ and Java solutions with no smart optimizations passing in 5s.

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

    Cheer up. Mistakes happen. We can use the experience, and ask ourselves how to improve the process so that they can't happen next time, or at least are less likely to happen.

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

    I think a lot of issues would be easier to avoid with some changes made by Topcoder. Changes that we need to wait for. I would like to see better problem setting software where an author can and should have a lot of solutions, not just one in Java. Validator tests would be nice too. Or let's just use Polygon and export problems to TC from there :D

    And I'm a fan of platforms with different types of contests. CF can use less interesting (more standard and thus educational) problems in Edu rounds, Atcoder has ARC for that. I agree with misof that problems like this one should exist, but experienced competitors don't want to see them in main contests of any platform (SRM for Topcoder, div1+2 round for CF). It hurts much more in case of Topcoder because of a small number of problems in a round.

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

Code for div1hard with comments:

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

[user:hmehta]Problem archive page shows the round as SRM 764. Shouldn't this be SRM 762 : https://www.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=&div1l=&div2l=&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=

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

    yup, that was a typo! this will be fixed in a while