Блог пользователя hmehta

Автор hmehta, история, 4 года назад, По-английски

TCO20 Round 2A and Parallel Round of TCO20 Algorithm Round 2A are scheduled to be held on Thursday, July 9 at 07:00 UTC -4.

Both the rounds will be _rated_

Please note that you must register for this round in the Arena. Registration is now open for the round in the Arena or Applet and will close 5 minutes before the match begins, so make sure that you are all ready to go. Click here to what time it starts in your area.

Members eligible to compete in Round 2A include:
- Members who won an Automatic Berth* a.k.a Bye* for Round 1
Advancers to Round 2 from Round 1A or Round 1B

Members eligible to compete in the Parallel Round include:
- Members who did not qualify for Round 2
- Members who didn't compete in Online Round 1
Qualifiers for Round 4 or TCO20 Algorithm Finals from Online Stages 1,2 and 3

Don’t know how to compete in Topcoder Algorithm Competitions?

Check out this guide to successfully compete in an algorithm match.

You can compete using:

  • Topcoder Java Applet - You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide.)
  • Topcoder Web Arena(Beta) - Please watch this video for step by step guide

Best of luck to you in the Arena!

  • Проголосовать: нравится
  • +64
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Gentle Reminder: The rounds begin in 4 hours.

»
4 года назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

Why is this contest not held on a weekend :(

It becomes really hard for people who are working to participate in the contest.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Agree! But a lot of factors come into consideration while scheduling, however, next year we will try and keep TCO Rounds on weekends preferably. However, there's a Round 2B on Saturday, July 18 12:00 UTC -4. Looking forward to seeing you compete in one of these :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does the Parallel Round have same problems? Also, are these Div1+2 combined?

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

I don't seem to be able to register (although I got a bye, according to https://tco20.topcoder.com/competition-overview/algorithm/algorithm-byes). Anyone else having the same problem?

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

How to find the string for l=7 in problem B?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Try to find any period with digits 1,3,7,9 Shortest length of the period is >7 which is why some many failures

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Any Intuition behind this, cause I thought it was trivial to solve for a number which is prime for 6 out of 7 possible cycles. And then print the number in such a way so that the 7th cycle is non-prime.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It's because if we take any digit of 2,4,6,8 it will be divisible by 2 when that digit comes at last place. Same with digit 5(divisible by 5).

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I was trying using only 1,3,7 :(

»
4 года назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

Not really a fan of B which involves pattern finding via program and then hardcode the pattern :( (ALL submissions in our room has a pattern string in their code)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    I hardcoded the solution for B as well. During the challenge phase I found dreamoon_love_AA 's solution and was awestruck by how beautiful it was. In my room, dreamoon_love_AA, me and IH19980412. He ruined all of our dreams by hacking all the B's solution in the room.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      After long time to do experiment, I got to know "repeating L-digit prime won't work when L = 7" and luckily this findings help me gain 3 challenges :)

      Well, the key point of this problem is "strongly believing that it is possible to gain perfect score" and I think problems of this type tend to have low success rate in SRM.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I just googled something like "primes rotation" and found wikipedia article about Circular primes where I read the same thing which you discovered after long experiments :)
        Hovewer, it didn't help me to solve the problem in time, but also gave some additional points on challenges ^_^

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Hope Topcoder has the function that we can remove our submission. Before the contest end, I found my solution is wrong but I cannot withdraw it...

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +49 Проголосовать: не нравится

    Not sure about others. But for me, both 300 and 400 were finding patterns. Too much work for 75 mins.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +30 Проголосовать: не нравится

      I think 300 was fine to some extent. But 400 was boring.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      Actually, 300 is not too much work. It is actually solvable in 180 seconds...
      (Some coders actually gained more than 297/300 points for this problem)

»
4 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится
»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

what is the cutoff for being eligible in next round?

»
4 года назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится

Exercise: What happens for L=8?

I can die without knowing it.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    If my computing are correct, then there is no string of length $$$n > 32$$$, where each substring of length $$$8$$$ is prime.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

      Thanks, my life is changed after this information :)

      I do not know how did you validate your answer, I implemented dp solution in compelxity $$$O(4^l \cdot n)$$$ based on observation that answer must contain only digits (1, 3,7 and 9) — I think such idea can be used for bigger values of $$$l$$$ in case there is solution for each prime substring.

      I had bug during contest, but I can rewrite it fast if you have different way of calculation.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

        Well, I just generated all $$$8$$$-digits primes, and for each of them calculated all valid transitions (if we have some prime P = p1p2...p8 then I add directed edge to any prime Q = p2p3...p8x). And now if there is cycle in graph, then there exist string each substring of which of length $$$8$$$ is prime. Otherwise, we are interested in the longest path (for $$$L = 8$$$ it's length is $$$25$$$).

        Upd. Ah, now I see that this is exactly what was written in the editorial...

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

          Now I'm interested in what happens in $$$L = 9, 10, 11,\dots$$$ and so on.

          However, the cycle exists if $$$L = 19, 23, 317, 1031, 49081, 86453, 109297, 270343$$$. That's simply because, repunit $$$11111\cdots111$$$ will be a valid number.