The second attempt of the first Online Round of the 2020 Topcoder Open Algorithm Competition has arrived! Round 1B will be held on Tuesday April 28, 2020 at 07:00 UTC -4.
Did you win an
- Automatic Berth* a.k.a Bye* for Round 1 or
- Qualified to Round 4 from Online Stages 1 and 2 or
- Advanced to Round 2 from Round 1A?
We have a parallel rated round for you all!
How many will qualify?
The 750 highest scorers from each Round 1 will win a spot in Round 2 of the Algorithm Competition.
Some Important Links
| Match Results | (To access match results, rating changes, challenges, failure test cases) |
| Problem Archive | (Top access previous problems with their categories and success rates) |
| Problem Writing | (To access everything related to problem writing at Topcoder) |
| Algorithm Rankings | (To access Algorithm Rankings) |
| Editorials | (To access recent Editorials) |
Good luck to everyone!
Gentle Reminder: Round Begins in 55 mins!
Hey buddy ... I m already selected in TCO 1A but i want to give TCO 1B too ...when i click register button it says -- Registration in this competition is by invitation only. What can i do ?
There is a parallel round for you, if you are in web arena — you will see a small button with numbers to see and register for parallel contest:
Difficulty of all problems was on the easier side. Not sure though if this was expected in Round 1.
Very true, It was like speedforce.
It was quite intentional. We actually moved 250->500, 500->900 and removed the 1000 to allow more people to have non-zero score in the official round. Of course, people in the parallel round didn't get anywhere near as enjoyable round I suppose, but we did try to run a 1B, and not a parallel round :)
Edit: See the editorial for a more lengthy explanation why the problems were so easy: https://www.topcoder.com/2020-tco-algorithm-round-1b-editorials/
I think for anyone who is say, blue or better, this round was very easy. But then would it not make sense to put more people in the "automatic to round 2 by rating" list?
Then why make this round rated for Div.1....
As regards the harder version of 900, with N < 10^10, could you please provide some examples of the numbers, which are very far from different primes?
1e10 I guess, because you need to pass at least 1e8 numbers (to get out from 99XXXXXXXX and 100XXXXXXXX)
Similar to the one I put in the analysis, but with more digits I guess would work — something like 4,450,000,000 — you'd need to pass through 100,000,000 numbers until you change the second 4 to something else. Mip182's example also works (although then it doesn't make sense to go up, as once you have 11 digits there is no way you can have them all different).
Thanks for your tests. Actually I couldn't find a different prime with 10 digits (the sum of all the digits = 45 -> it is divisible by 3), so N<=10^18 is immediately reduced to N <= 10^9. For this, I tried N=445000000 and brute force works very fast: Execution Time: 0.165s.
This is an alternative solution, comparing to a complicated dfs/bfs generation.
What about if you start from 10^9? I'd be quite surprised if 100M * 9 divisions run in 0.165s, although I guess many of the numbers don't require all 9 divisions to get to a repeated digit. Still, sounds strange.
It found the following: 987654103 in Execution Time: 0.201s.
When we reduced the N from 10^10 to 10^9 you don't need 10^8 passes but only 10^7 and it is fast.
Just wanted to know that for going back and fro from a number and checking the given constraints will be accepted in last problem? For 50000000 ans is 50123467 . The running complexity will be around 10^9 . Correct me please if I am wrong.
Will there be a 1c round? I missed 1a due to bugs in web arena and missed 1b due to oversleeping.
No, see here: https://tco20.topcoder.com/competition-overview/algorithm/algorithm-rules
Looking at this page. It seems they recently added 2C round.
Where?
At bottom of same page.
ONLINE ROUNDS 2, 3, AND 4
Online Round 2 consists of Matches 2A, 2B, and 2C. All Competitors who advance to Online Round 2 can compete in these Matches for the 600 spots in Online Round 3.
*2*C, not 1C.
It was a copy paste error. They stopped 2C last year. hmehta said he will fix this on website.
Why do all users have field Adv equal to N in statistics of round https://community.topcoder.com/stat?c=round_stats&rd=17962&dn=1 ?
In Round 1A all right https://community.topcoder.com/stat?c=round_stats&rd=17906&dn=1 .
Can someone please explain solution to 900 pointer, I read the editorial and I understand main ideas, but it would help if someone could explain for the given constraint and also for tighter higher constraint $$$N$$$. Basically I wrote wrong kind of brute-force which checked first in an interval whether number is prime or not and then it checked whether digits are distinct.
But I failed on system tests. As mentioned in editorial, during hacking phase, I tried some numbers near $$$44,500,000$$$, and a little up, down. My solution was giving over $$$1500ms$$$.
Any help is appreciated, and also for higher constraint how to approach.
Looks like brute force works for the higher constraint too. You can't have a distinct prime with more than 10 digits, as there are only 10 digits. You can't have a distinct prime with 10 digits as the sum of all the digits = 45, so such a number is divisible by 3 and not prime. So N < 10^9. I wrote the brute force solution where I check if all the digits are distinct and if they are I check if the number is prime. The last check is done by trying all the primes <= sqrt(x). So far there is no test which tles that.
So there is a guarantee that such a prime exists within certain bounds of our $$$N$$$. So we can just hope so or is that more evidence to it, I agree checking distinct first is obviously more efficient, but what if the gap is too big say of the order of 1e7 or so, so checking digits would make it around ~1e8 (along with sqrt(1e7) computations on some candidates with distinct digits)
Although I get your saying that the above should not be the case, but that is only my intuition.
Thanks!!
If you can find a pair of 2 primes which are far away, then maybe it will time out. For the distance of 1.5e7 it works fast in practice (0.2s on tc).