### hmehta's blog

By hmehta, history, 5 months ago, ,

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.

Good luck to everyone!

• +32

 » 5 months ago, # |   0 Auto comment: topic has been updated by hmehta (previous revision, new revision, compare).
 » 5 months ago, # |   +2 Gentle Reminder: The match begins in 2hours and 30 mins
 » 5 months ago, # |   0 How to solve medium in Div2?
•  » » 5 months ago, # ^ |   +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 months ago, # ^ |   +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 months ago, # |   +30 Thanks to espr1t for the contest! I liked the Div1 problems very much.
•  » » 5 months ago, # ^ |   +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 months ago, # |   +8 Distinct numbers required was a really nice touch to 250!!!
•  » » 5 months ago, # ^ |   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 months ago, # ^ |   +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 months ago, # ^ |   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 months ago, # |   +27 This mod > sqrt(LLONG_MAX) in the middle problem was quite viperous test28 NWLRBBMQBHCDARZOWKKYHIDDQSCD XRJMOWFRXSJYBLDBEFSARCBYNECD YGGXXPKLORELLNMPAPQFWKHOPKMC 
•  » » 5 months ago, # ^ |   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 months ago, # ^ | ← 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 months ago, # ^ | ← 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 months ago, # ^ |   +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 months ago, # ^ |   0 Got it. Thanks a lot.
•  » » 5 months ago, # ^ |   0 What's tricky about this test? Could you somehow pass examples with overflow bug and fail on this one?
•  » » » 5 months ago, # ^ | ← 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 months ago, # ^ |   0 My solution fails all the examples with no casting because it produces negative hashes. Don't you have negatives?
•  » » » » » 5 months ago, # ^ |   0 Actually idk lol maybe this guy didn't test his solution on samples. My code to find the test looks like this: codewhile (true) { int n = 28; string a[3]; for (int i = 0; i < 3; ++i) { while (a[i].size() < n) { a[i] += (char)('A' + rand() % 26); } } if (EllysHash().getHash(n, a[0], a[1], a[2]) != EllysHashBad().getHash(n, a[0], a[1], a[2])) { cout << n << "\n" << a[0] << "\n" << a[1] << "\n" << a[2] << "\n"; return 0; } } 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 months ago, # ^ |   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 months ago, # | ← Rev. 2 →   +48 hmehta why updating rating on website taking days ?It would be nice if someone fixes this.
•  » » 5 months ago, # ^ |   +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! :)
•  » » » 4 months ago, # ^ |   +5 Not fixed yet , tested in last round hmehta
•  » » » » 4 months ago, # ^ |   0 It's a website cache issue which will take time. We are on it!
 » 5 months ago, # |   +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 months ago, # ^ |   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 months ago, # ^ |   +27 Because 28 was the perfect number for N. Get it? 28 is perfect...
 » 5 months ago, # |   0 Please share the link of editorial.
•  » » 5 months ago, # ^ |   +29 Here's my writeup until the official blog is posted: https://docs.google.com/document/d/1LUR7Z3N4b3c0xV9IaKYsgLcaXwkSgDq7PZVQWIVj7pY/edit?usp=sharing
 » 5 months ago, # |   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 months ago, # ^ | ← Rev. 2 →   +8 In the practice rooms: In applet — when you do “Run System Tests — you will get a pop up with the system tests resultsTo 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
•  » » » 5 months ago, # ^ |   0 It works, thank you!
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 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://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 ?
•  » » » » 4 months ago, # ^ |   0 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
•  » » » » » 4 months ago, # ^ |   0 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://codeforces.com/blog/entry/67464 . Everything works fine now . Thank You
 » 5 months ago, # |   +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.