hmehta's blog

TCO20 Round 1B
By hmehta, history, 4 years ago, In English

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!

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

Comments Comments (28)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gentle Reminder: Round Begins in 55 mins!

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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 ?

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

      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:

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

Difficulty of all problems was on the easier side. Not sure though if this was expected in Round 1.

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

    Very true, It was like speedforce.

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

    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/

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

      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?

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

      Then why make this round rated for Div.1....

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

      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?

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

        1e10 I guess, because you need to pass at least 1e8 numbers (to get out from 99XXXXXXXX and 100XXXXXXXX)

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

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

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

        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.

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

          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.

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

            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.

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

      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.

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

Will there be a 1c round? I missed 1a due to bugs in web arena and missed 1b due to oversleeping.

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

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

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 .

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

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.

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

    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.

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

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

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

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

        → Reply