hmehta's blog

By hmehta, history, 4 months 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

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The link of Stage 4 leaderboard is not working

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Fixed thanks! :)

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Gentle Reminder! The match begins in around 2 hours and 30 mins from now!

»
4 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

how to solve Strawberry?

  • »
    »
    4 months 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...

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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. :)

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

      I got 5.0s in practice room

    • »
      »
      »
      4 months 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)).

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

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

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

          Just compute on doubles ;p

        • »
          »
          »
          »
          »
          4 months 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.
          • »
            »
            »
            »
            »
            »
            4 months 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$$$?

            • »
              »
              »
              »
              »
              »
              »
              4 months 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$$$.
»
4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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...

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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?

          • »
            »
            »
            »
            »
            »
            4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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.

»
4 months 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.

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

    Update: In div1 250 the validator allowed some invalid inputs. The validator is being fixed and the offending challenges will be nullified.

    Div I results and ratings will be updated later in the day.

»
4 months ago, # |
  Vote: I like it +52 Vote: I do not like it

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

»
4 months 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.

»
4 months 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!

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

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

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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

            • »
              »
              »
              »
              »
              »
              »
              4 months 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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months 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.

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

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

          • »
            »
            »
            »
            »
            »
            4 months 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.

      • »
        »
        »
        »
        4 months 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.

    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Code for div1hard with comments:

Spoiler
»
4 months 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=

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

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