hmehta's blog

Topcoder SRM 759 — Registration Open
By hmehta, history, 6 years ago, In English

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!

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

Comments Comments (36)
| Write comment?
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

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

How to solve medium in Div2?

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

    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++.

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

      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.

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

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

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

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

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

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

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

    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... :)

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

      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.

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

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

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

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it +19 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it +8 Vote: I do not like it

        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?

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

          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.

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

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

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

      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.

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

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

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

          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.

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

    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).

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

hmehta why updating rating on website taking days ?

It would be nice if someone fixes this.

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

    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! :)

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

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.

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

    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.

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

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

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

Please share the link of editorial.

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

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

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

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.

→ Reply