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!
Gentle Reminder: The match begins in 2hours and 30 mins
How to solve medium in Div2?
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++.
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.
Thanks to espr1t for the contest! I liked the Div1 problems very much.
Thanks! The Div1 250 / Div2 600 turned out to be more "evil" than I anticipated, but all in all the contest went fine :)
Distinct numbers required was a really nice touch to 250!!!
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... :)
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.
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.
This
mod > sqrt(LLONG_MAX)in the middle problem was quite viperousCan 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.
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.
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?
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
leftandright), we want to choose one element from each of them so that their sum modulomodis 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
modis just $$$x + y - (10^{15}+37)$$$. Two pointers are used here, because if we iterate over $$$x$$$ in ascending order then the minimal $$$y$$$ fromrightsuch that $$$x + y \geq 10^{15}+37$$$ decreases.Got it. Thanks a lot.
What's tricky about this test? Could you somehow pass examples with overflow bug and fail on this one?
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 justx = x * power % mod, which leads to overflow.I rewrote my solution so that it doesn't cast to
__int128_tand 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.My solution fails all the examples with no casting because it produces negative hashes. Don't you have negatives?
Actually idk lol maybe this guy didn't test his solution on samples. My code to find the test looks like this:
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.
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).
hmehta why updating rating on website taking days ?
It would be nice if someone fixes this.
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! :)
Not fixed yet , tested in last round hmehta
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.
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.
Because 28 was the perfect number for N. Get it? 28 is perfect...
Please share the link of editorial.
Here's my writeup until the official blog is posted: https://docs.google.com/document/d/1LUR7Z3N4b3c0xV9IaKYsgLcaXwkSgDq7PZVQWIVj7pY/edit?usp=sharing
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
In the practice rooms: In applet — when you do “Run System Tests — you will get a pop up with the system tests results
To check on which test case the solution failed in the match, you can see that in the match results: https://community.topcoder.com/stat?c=problem_solution&rm=332610&rd=17531&pm=15436&cr=40489841
It works, thank you!
I am unable to start Top Coder Arena on Ubuntu 18.04 after the latest update of Java and Iced Tea Web. I have written a blog on it here https://mirror.codeforces.com/blog/entry/67464 and I have also asked it on stackoverflow but after wasting a whole day, I am still unable to start the Applet Arena. I have never participated using Web Arena before. Is there any one who can help me to start Applet arena on Ubuntu ?
Did you add the java exception list? Incase it still doesn't work. Please log an issue at support@topcoder.com :) We will help you launch the arena
Actually It is now working after downgrading some apps. I have downgraded IcedTea to version 1.6, uninstalled open-jdk 11 and installed open-jdk 8 . I followed this answer on AskUbuntu https://askubuntu.com/questions/1134881/icedtea-8-cannot-run-any-jnlp-application-maybe-due-to-openjdk-11 also I have mentioned it in my blog so that others can get help here https://mirror.codeforces.com/blog/entry/67464 . Everything works fine now . Thank You
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.