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

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

Topcoder SRM 789 is scheduled to start at 13:00 UTC -4, August 30, 2020.

Registration is now open for the SRM in the Arena or Applet and will closes at 12:55 UTC-4. The coding phase will start at 13:05 UTC-4, so make sure that you are all ready to go.

Thanks to square1001, lg5293 and misof for writing the problem set. Also thanks to misof for testing and coordinating the round.

Choose Your Competition Arena

There are two ways to compete in Algorithm Competitions or Single Round Matches (SRMs). Read here to find which works best for you.

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!

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

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

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

Gentle Reminder: Match begins in an hour

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

I found the Div1 1000-pointer very nice, thanks!

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

The editorial has not been posted right? I don't see it when I click "Editorial". Anyway, how to solve the second and third problem?

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

    500: Assume $$$C \le 13$$$. A state will need information of two previous rows to transit to next state but the number of states is very small (about thousands) not $$$2^{26}$$$. Nothing else...

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

      Yea it is also worth noting that the number of states is bounded by Fibonacci numbers due to the condition that no two bases can be adjacent, which is less than a thousand here I guess.

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

        For one row the number of valid placements of bases into n columns satisfies the recurrence ways[n]=ways[n-1]+ways[n-3], which gives an upper bound of O(1.4656^n), better than Fibonacci. (Bases must be at least 3 apart, so if you place a base into column n, you need to leave the next two free.)

        In a similar way we can find an even tighter bound for the number of ways to fill two consecutive rows with n columns: O(1.8393^n). Thus, solutions that only construct reachable states and then iterate over all valid ways to fill the next row actually run in O(some polynomial * 2.6957^n). That's quite less than the naive estimate of O(poly * 2^(3n)) = O(poly * 8^n).

        For n=13, 2.6957^n is roughly 400,000.

        The task is also solvable in O(poly * 2.3325^n) with a more complicated implementation: when going from one state to another you need to generate only the valid ways of filling the next row given the bases you already placed, instead of going through all ways of filling the row in vacuum and filtering out the ones that create a conflict.

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

      I see. Thanks.

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

    For hard, I think something like this works (I haven't coded it yet):

    Call a number x special-winnable if P1 wins when we are forced to only play with special numbers in a pile of size x.

    Crucial claim: If there exists a pile of size x > 0 where x is special-winnable, P1 wins. Additionally, there exists a winning move for P1 starting from pile x.

    Proof

    With this lemma, we can finish off the problem. First, we can determine all special-winnable numbers via a simple dp.

    Let us start by determining if a state $$$a_1, a_2, ..., a_n$$$ is a P1-win. If any of the $$$a_i$$$ are special-winnable, P1 wins. Additionally, if a player turns a pile into a special-winnable pile, that players automatically loses by the claim (since the next player can win by performing some move in this pile). Hence, both players now must avoid turning piles into special-winnable piles.

    By the definition of special-winnable, we note that if x is not special-winnable, any special move will turn it into a special-winnable pile. Hence, we cannot even perform any special moves if we want to win!

    Thus, the rest is easy since not playing any special moves mean that each pile is independent. We can compute the grundy number for each pile and xor everything.

    Counting the number of winning states can be done in a similar fashion via brute force since constraints are small.

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

It seems like the official editorial is ready!

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

Lewin misof square1001 Can you please help me with SRM 789 Div2 Hard/Div1 easy question ThreeDigits? I tried every input possible I tried to run the script to see if my solution works with 0<=x<100 && 0<=y<100 && 1<=z<100 my solution works for these inputs but when I submit on topcoder it is giving WA. Here is my solution.

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

    I would be suspicious of the part where you do to_string(long double). Try rewriting that step using integer arithmetic only.

    (Also note that systests in the practice room will tell you the test case you are failing on.)

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

      I didn't have used much of the topcoder site so can you tell me how can I look for system test cases for SRM or any other competition problems in practice mode?

      Edit: Got AC. the issue is with to_string first I have to multiplied the answer by 1000 then divide by 1000 after convert into long then use to_string because to_string doesn't take care of precision by itself