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

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

We will hold AtCoder Beginner Contest 180.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

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

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

Wow that's an early announcement

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

How to solve D?

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

How to solve B(only Euclidian distance part) and D ??

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

Solution for F, anyone?

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

    Let DP[n][m][b] be the number of ways to build a graph with n labeled nodes and m unlabeled edges with b being a flag for restricting the size of the maximal connected component.

    From there at each iteration and to avoid double counting you only look at the components covering the first node.

    For example if I want a component of size 5 and n = 10 first I find the number of ways I can choose nodes to form this component which is 9 choose 4 (node #1 is already included). Then I find the number of way to build a path (5! / 2) or a cycle (4! / 2) and call the appropriate state.

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

      I didn't get how are you avoiding double counting?

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

        cause if you reverse a chain, the result will be the same as the origin, so there are k!/2 ways to form a chain with size k, or you will count a chain twice.

        as to circle, you should consider symmetry and shift, so there are k!/2/k = (k-1)!/2 ways to form a circle with size k.

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

          He is referring to the over counting of the total number of ways to make the connected components using DP, not the over counting of a particular component itself.

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

        sorry, i misunderstood it.

        for example, with node 1, 2, 3, 4 and 5,

        • choose 1,2 to form a component, and then choose 3,4,5 to form a component.
        • choose 3,4,5 to form a component, and then choose 1,2 to form a component.

        these 2 ways generate same graph, but if you count it more than once, then double counting happen.

        if you only look at the components covering the first node, you will only count the first way.

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

How was E intended to be solved? I just copy pasted a DP code from stack overflow and calculated distances of graph[i][j] using the formula in the question and got AC.

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

    Travelling Salesman Problem using dynamic programming

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

    Well, I just honestly implemented dp for traveling salesman problem... I guess it was the intended solution

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

    I guess the main difference in the problem was to visit at least once, while in standard TSP it is exactly once.

    So consider if the problem was a general directed graph, then the standard DP solution would not have worked, but since the shortest path between two vertices, in this case, is the same as their direct edge between them, the problem had the exact same solution.

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

      Even for the general graph, we can run floyd warshall first, then the classic TSP. It's a shame I took 50 minutes in this problem.

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

        I never thought they would straight away give classic tsp for a problem at "E". Man .. I took so long to implement floyd warshall version of it .. . Should have tested with the classic version first

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

        Can you elaborate on the Floyd-Warshall + TSP Solution for general graphs, or share any resource to learn from.

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

          This is what I did in my submission in contest,now you would have run through comments that direct edge is always optimal in this problem which i never observed so instead what i did was to first apply floyd warshall on the graph with saving a "next" Matrix in order to trace the path when i move from a node to other because when I would do so unintentionally I would also visit some unvisited cities(maybe or maybe not). Now after doing this i just do normal tsp and updating the mask. However i did see printing some paths and saw that direct edges are the shortest ones but thought they have intentionally given such samples.

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

    if n<=20 its 95% of the time bitmask dp

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

    Can you share the link? I searched for such one, but did not found any, and was not able to implement a bugfree version.

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

Was solution to E was intended to be solved using floyd warshall and then tsp, or did I do some overkill ?

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

    I don't think you need floyd warshall. Since the distance metric used always gives shortest path between two vertices.

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

    I solved it using dp

    hint1
    hint2

    my code :

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

This is my solution to B problem, can anyone tell me why it's WA My code

Edit: After Changing everything to long long, it is working now, even long double didn't work, can anyone explain to me why long long is working and remaining are not.

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

    Try long double instead of double, and sqrt instead of pow.

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

      Tried now, but still shows WA, can you please help me out and point the mistake in this

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

        You have to take max of absolute of arr[i] instead of just arr[i] to calculate 3rd distance. This is the same which I did and llost 700 ranks bcoz of that

        EDIT: sorry I overlooked that part.

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

How to solve Problem F? DP?

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

Hi, could someone point out my mistake in B

Edit: But x[i] is long long right?

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

Could someone help me.. i dont know why my dp runs incorrectly :< https://paste.ubuntu.com/p/nrYYHqvxw7/

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
  1. TLE
  2. AC Solution after contest 4th problem why anyone?
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Because a * x will overflow for big cases, leading to a negative number and an endless condition

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

How to solve d please explain anyone?? i was thinking it was dp but other's solution just amazed me

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

Why this solution gets TLE while this gets AC? Using int instead of long long should result in wrong answer instead of TLE, then what other reasons behind it?

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

    For bigger values of n, i * i will overflow and will result in i * i <= n being true.

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

Please can somebody explain why using even unsigned long long is giving WA on D? I tried different values of x,y,a,b and checked but they were all running fine, but during contest ((ull)x*a<2e18) dosen't work but ((double)x*a) worked; why??

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

How to solve E?

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

    Use dynamic programming with bitmask, dp[i][j] is the min cost of visting all cities specified by state i with the last visiting city as j. For a given dp[i][j], if we already know its result, we use it to make the next hop. For all valid hops from a city that has been included in i, to a city j from 0 to n — 1, update dp[next][j] where next is i | (1 << j).

    The final answer is dp[(1 << n) — 1][0].

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

I have a problem with B. I am using long long and long double wherever needed and I am still getting compilation error. I think I am getting an error while using "abs(x)". Here's my code, plz help : problem B

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

    There are a few problems:

    The error with abs function is due to ll being defined as unsigned.

    Then after this, you will be getting a WA because you have your cd as cd=max(cd,x) instead of cd=max(cd,abs(x))

    After that, you still are getting a WA because you are submitting problem B's solution for problem A :)

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

Hello guys, I need your help on my solution to the third problem. Here's a link to my submission, I kept getting TLE. How could I have optimized my solution? https://atcoder.jp/contests/abc180/submissions/17476685

On the second problem, I was flat out getting Wrong Answer. What was wrong also? https://atcoder.jp/contests/abc180/submissions/17474677

Thank you very much. PS; ABC 180 was my first CP contest, so also, any general tips for CP will do.

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

A question: How much would be the corresponding rating of problems C, D and E on codeforces?