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

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

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!

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

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

The link of Stage 4 leaderboard is not working

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

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

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

how to solve Strawberry?

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

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

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

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

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

      I got 5.0s in practice room

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

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

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

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

          Just compute on doubles ;p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

        given two polynomials, output their product.

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

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

            bad problem for topcoder: multiply two polynomials

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

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

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

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

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

                of course, without any examples on it.

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

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

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

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

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

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

          Its not 7k, but 14k?

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

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

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

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

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

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

Code for div1hard with comments:

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

[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=