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

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

Hey All!

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

The round is prepared by espr1t and tested by adamant

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

Stage 4 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 760 — June 12, 21:00 UTC-4

Good luck to everyone!

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

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

Gentle Reminder: The match begins in 2hours and 30 mins

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

How to solve medium in Div2?

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

    Generate all primes with five digits and then loop through and all the pairs and generate the third with the help of sum values provided and if the third value is a distinct prime then ans++.

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

      I had the same approach. It was very tight limit of 2 secs. One test case failed for me out of 126. That test case took 1.54s to run on ideone.

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

Thanks to espr1t for the contest! I liked the Div1 problems very much.

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

    Thanks! The Div1 250 / Div2 600 turned out to be more "evil" than I anticipated, but all in all the contest went fine :)

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

Distinct numbers required was a really nice touch to 250!!!

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

    It actually made sense — I added it because if you were to tell me your three favourite numbers I guess you wouldn't tell me one of them twice... :)

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

      Well, I agree it makes sense but I'd better highlight that in example tests. It doesn't give out the exact solution to the problem to have such a test.

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

        For that I agree as well — but it wasn't until the challenge phase when I realised that so many people will miss that — I expected few people here and there (which would make for a non-boring challenge phase) but I was indeed sad to see so many people failing because of it.

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

This mod > sqrt(LLONG_MAX) in the middle problem was quite viperous

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

    Can you give some hints on solving it? I, very naively, thought we could do greedy, but then I realized they want minimum value after mod. How to do this? Maybe don't give solution to problem, but something related to how to minimize an answer under a modulo.

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

      Meet in the middle: you can break the string down to two halves. Compute hashes for all possible strings in each half: $$$\mathcal O\left(3^{n/2}\right)$$$ such hashes for each half. Now the whole string hash is something like $$$127^{n/2} x + y$$$ where $$$x$$$ comes from the first half hashes and $$$y$$$ comes from the second half hashes. So multiply the list of first half hashes by $$$127^{n/2}$$$ and then minimize this expression by sorting the list of hashes and doing some two pointer stuff or whatever.

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

        Oh right. So basically $$$3^{28}$$$ is too big to try all possibilities. But, even after you calculate all $$$3^{14}$$$ hashes of first half, and second half, for calculating all the whole hashes $$$127^{\frac{n}{2}}x + y$$$, won't you basically get complexity of $$$3^{14} * 3^{14}$$$. Basically, I never really understood how Meet in the middle works.

        UPD: So, by two pointer, did you mean that we don't calculate all whole hashes, and instead try to figure out some way to minimize whole thing, by sorting hashes of first half and hashes of second half?

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

          After we calculated all $$$127^{\frac{n}{2}}x\pmod{10^{15}+37}$$$ and all $$$y\pmod{10^{15}+37}$$$ and sorted these vectors (call them left and right), we want to choose one element from each of them so that their sum modulo mod is minimized. There are two ways to do this:

          • we choose such $$$x$$$ and $$$y$$$ that $$$x + y < 10^{15}+37$$$. Then their sum doesn't need to be taken modulo smth, and therefore the answer does not exceed left[0] + right[0].

          • we choose such $$$x$$$ and $$$y$$$ that $$$x + y \geq 10^{15}+37$$$. It's clear that $$$x + y < 2\cdot(10^{15}+37)$$$, so their sum modulo mod is just $$$x + y - (10^{15}+37)$$$. Two pointers are used here, because if we iterate over $$$x$$$ in ascending order then the minimal $$$y$$$ from right such that $$$x + y \geq 10^{15}+37$$$ decreases.

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

    What's tricky about this test? Could you somehow pass examples with overflow bug and fail on this one?

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

      Well, the solution is to calculate all possible hashes of the left half and the right half, then multiply all left hashes by $$$127^{\lfloor n/2 \rfloor}$$$ and do something with two pointers. The "multiply by $$$127^{\dots}$$$" part can be implemented with something like x = (__int128_t)x * power % mod, with iterative multiplication by $$$127$$$ or just x = x * power % mod, which leads to overflow.

      I rewrote my solution so that it doesn't cast to __int128_t and uses the last option instead and ran it locally until it found a test where two my solutions produce different output. Then I hacked one guy in my room with this test.

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

        My solution fails all the examples with no casting because it produces negative hashes. Don't you have negatives?

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

          Actually idk lol maybe this guy didn't test his solution on samples. My code to find the test looks like this:

          code

          So, you see, it may be that my solution, being written like this, produces negative hashes on samples too, i didn't verify the contrary.

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

    I originally had the problem with MOD = 1000000007, but unfortunately as the string grows longer the answer becomes smaller. With it most inputs with N = 28 (with relatively diverse letters) had answer 0 (and almost all < 10).

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

hmehta why updating rating on website taking days ?

It would be nice if someone fixes this.

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

    Yeah there is a recent bug which delays it! I think I know the issue will fix it tomorrow and hope it will br updated quickly in the next round! :)

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

I just don't understand why the limitation in Div1 500 is N<=28 but not 26 or 24. This limit is TOO TIGHT and painful, it took me a long time to do some needless optimization to make my program faster enough to meet the 3s requirement.

And finally I got MLE as a result because I returned a length-3^14 vector instead of passing its reference. That is really ridiculous tbh.

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

    Would you mind sharing your code here? I also returned a vector, used binary search instead of two pointers but my code ran in 1.5s.

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

    Because 28 was the perfect number for N. Get it? 28 is perfect...

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

Please share the link of editorial.

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

How do you view the systests in which you failed? When I run them, it just tells me if I've passed all of them or not. I remember viewing them long time back on the web arena

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

I found another solution for Div1 250 / Div2 600.

The idea is not to brute-force two prime numbers, but to brute-force all possibility of three five-digit integers, which the sum of each digit matches.

Let three distinct integers $$$A = \overline{a_4a_3a_2a_1a_0}, B = \overline{b_4b_3b_2b_1b_0}, C = \overline{c_4c_3c_2c_1c_0}$$$, when $$$X = \overline{x_4x_3x_2x_1x_0}$$$ means the digit correspond to $$$10^i$$$ is $$$x_i$$$, for five-digit integer $$$X$$$.

We can assume $$$A < B < C$$$. So, for digit of $$$10^4$$$, we can say that $$$1 \leq a_4 \leq b_4 \leq c_4 \leq 9$$$. In maximum there are $$$13$$$ possibilities when $$$sums_4 = a_4 + b_4 + c_4 = 15$$$.
For digit of $$$10^1, 10^2, 10^3$$$, the condition is $$$0 \leq a_i, b_i, c_i \leq 9$$$ (and of course $$$a_i + b_i + c_i = sums_i$$$). There are maximally $$$75$$$ combinations when $$$sums_i$$$ equals $$$13$$$ or $$$14$$$.
For digit of $$$10^0$$$, since $$$A, B, C$$$ has to be five-digit primes, we can say that $$$a_0, b_0, c_0$$$ is in $$$1, 3, 7, 9$$$. Confining to this, there are maximally $$$9$$$ combinations when $$$sums_0$$$ is in $$$11, 13, 17, 19$$$.

Thus, there are maximally $$$9 \times 75 \times 75 \times 75 \times 15 = 56 \ 953 \ 125$$$ possible combinations. The worst case is like $$$sums = (11, 13, 13, 13, 15)$$$. It means that we can brute-force all possibilities.