UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248） Announcem...

We will hold UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）.

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

We are looking forward to your participation!

• 41 minute(s) ago, # ^ |

  yes!!

• 20 hours ago, # ^ |

  I got innumerable TLEs and it TLEd on only 1 test case most of the times. I used lower_bound and then implemented by own binary search function but none worked. Don't know how to improve my solution further :)

  • 19 hours ago, # ^ |

    I got an AC in D problem. So basically what I did is I created a map<int, vector> and then stored the indices of all the elements in that map. Then I just took lower_bound and upper_bound of l and r respectively of that vector in the map.

• 20 hours ago, # ^ |

  I represented a line as the set of all points (in the input) it passes through

• 20 hours ago, # ^ |

  my sol: let visi,jvisi,j be: if the line with point ii and jj is used, set it 1, otherwise set it 0. Then we can simply mark all pairs of points on the same line.

  sample code

• 20 hours ago, # ^ |

  I made a set<array<int64_t, 3>> and stored as form ax+by+c=0ax+by+c=0 reduced to lowest form using gcd(a,gcd(b,c))gcd(a,gcd(b,c))

  and stored both a,b,ca,b,c and −a,−b,−c−a,−b,−c in set

  and printed size of set / 2 as answer

• 20 hours ago, # ^ |

  ← Rev. 2 →  

  +4

  We know that the equation of a line is y=mx+cy=mx+c, where mm is the line slope and cc is the intersection point with the y-axis. To avoid working with floating-point values, let's manipulate this equation a bit. So far, we have y=ΔyΔxx+c⟺yΔx=xΔy+cΔxy=ΔyΔxx+c⟺yΔx=xΔy+cΔx Now, we will represent each line with the triplet (Δx,Δy,cΔx)(Δx,Δy,cΔx). And to avoid the problem of having lines with the same slope up to a constant factor, we can re-assign Δx=Δxgcd(Δx,Δy)Δx=Δxgcd(Δx,Δy) Similarly, Δy=Δygcd(Δx,Δy)Δy=Δygcd(Δx,Δy). With this representation, we can easily check if a point lies on a line. My submission here.

• 20 hours ago, # ^ |

  ← Rev. 2 →  

  +3

  I represented a line as the set of all points (in the input) it passes through. There are O(N^2) lines that pass through at least 2 points, and each line has size O(N), so you can explicitly enumerate all such lines in this representation.

  (optimization: instead of "set of points" you can use "sorted list of indices of points")

• 20 hours ago, # ^ |

  a line can be defined by its endpoints in the input, using a set you can store all valid lines in pairs of points

• 2 hours ago, # ^ |

  ← Rev. 2 →  

  0

  I think there are significant differences both ways, for Range Count Query I constructed the frequency dictionary of A[0:i] for each i and answered each query offline. But this doesn't work if operations can change A. And I think it's a legitimately different algorithm from yours because the time complexity is O(N) + Q log Q.

  Likewise you can solve Distinct Character Queries with a segment tree for each letter of the alphabet, but it doesn't generalize to large alphabets.

  • 27 minutes ago, # ^ |

    Yes, of course. I didn't mean that the problems are same, I meant that if you've read the editorial of Distinct Character Queries, you'd instantly get the idea for solving Range Count Query (as the former contained the trick of maintaining sorted indices of positions and binary searching).

    RCQ is a subset of DCQ but not the other way round, due to update queries.

• 20 hours ago, # ^ |

  ← Rev. 2 →  

  +9

  Let xx be the gcd of the numbers on the path. We first calculate the sum of kk for all possible xx with only the constraint that all numbers should be a multiple of xx (which means that the gcd might be dx(d>1)dx(d>1) instead of xx, but we will deal with that later).

  We can now mark every node whose number is a multiple of x as passable, which means the path we take can only pass passable nodes. We can calculate the answer of each connected component (it's easy to see that they are trees) seperately because we can never move from one component to another.

  The contribution of two nodes i,ji,j will be depi+depj−2depl+1depi+depj−2depl+1 , where ll is the LCA of ii and jj. We choose a vertex as ll and can calculate the answer with simple math. Then we add the answers together for all connected compnents to get the answer of the current problem.

  Now we get the answer when the gcdgcd is a multiple of xx , but we need the answer when gcd=xgcd=x. Let fxfx be the answer, then we should use the current answer to minus the total ff for all multiples of xx , because those whose gcd=dx(d>1)gcd=dx(d>1) is calculated exactly once in those values.

  Then we get a O(nω(n))O(nω(n)) (ω(n)ω(n) denotes the maximum number of factors for a number below nn , when n=105n=105 , it's about 100100) solution if carefully implemented.

• 20 hours ago, # ^ |

  ← Rev. 2 →  

  +3

  I am not sure,but i think it's only solveable using DP.The reason for this is because it has small constraints so i think it is meant to be solved by DP.Also it is <=K so i think DP is needed.If it was =k then i'd use stars and bars.

  • 19 hours ago, # ^ |

    Cant you apply stars and bars for all 1 <= i <= k?

    • 19 hours ago, # ^ |

      I think you can.The thing is that you should try to make it in a form like 0<=.It is a very common trick i believe.Let's say that you need to make a+b+c=n with 1<=a,b,c<=n.Then,what you need to do is that make it into a+1+b+1+c+1=n so that it'll be something like 0<=a,b,c<=n-1.Then the solvable form is a+b+c=n-3.Please correct me if i am wrong since i am not that good in math.

      • 19 hours ago, # ^ |

        ← Rev. 2 →  

        0

        I actually meant this:

        Since K<=2500, you can apply stars and bars to get the total sum 'X' for all N <= X <= K and add their total sum, right?

        should be something like O(K*(N+K))

        • 19 hours ago, # ^ |

          ← Rev. 2 →  

          0

          Oh,I'm not sure.You see,you need modular inverse to count it right? because we need to take mod and there is a division involved in the stars and bars formula,right? (i haven't tried it myself so i'm not sure whether it's possible or not.But i think it's quite hard don't you think?)

          • 19 hours ago, # ^ |

            Yh, will try this approach. It should be ossible with complementary counting

      • 19 hours ago, # ^ |

        I think you're trying to solve for

        a1 + a2 ... an = k, where ai>=M, but the problem is actually ai<=M(which I guess can be done with complementary counting). Is it possible to do it without complementary counting?

    • 15 hours ago, # ^ |

      ← Rev. 2 →  

      0

      yes we can , with stars and bars + complementary counting . (count number of combinations with at least one variable(box) being >=M>=M) here is submission which uses that technique .

      time complexity is O(nlog(mod))O(nlog(mod)) but can be optimized to O(n)O(n) if we precalculate modular inverses .

      it's strange that they didn't mention this approach in editorial

• 19 hours ago, # ^ |

  Bonus 2 in the editorial uses formal power series in O(k).

• 17 hours ago, # ^ |

  I did not want to use DP, so I wrote the answer using memoized recursion. Submission

• 15 hours ago, # ^ |

  Actually we can uniquely determine a line by checking the first two index of point that is on the line, and to implement it just allocate a 2d bool array. I find it is more easy to code :)

• 1 minute ago, # ^ |

  For a smoother experience, read this gist which has embedded images.

  Solving this problem requires a deep understanding of how Subset Sum DP works. In fact, with a proper abstraction, you can almost convert it to a Subset-Sum DP problem.

  In the subset-sum problem, we have a zero-indexed array of nn elements. To simplify the mathematical notation, for each node xx, define the node vertically below it as x∗x∗. If we capture each xx and x∗x∗ in a rectangular box, we will get an array of nn blocks (let's say, zero-indexed), and we need to perform some operations on these blocks. This is the first level of abstraction which makes the numbers in subset sum DP analogous to blocks in this problem.

  Visual Representation

  Next, to figure out the DP definition, recall that in subset-sum problem, even though we are supposed to find the number of subsets of the entire array with sum exactly equal to kk, we define dp[i][j]dp[i][j] as the number of subsets with sum equal to jj for all j≤kj≤k. Why is this so? It's because j1+j2j1+j2 can become equal to kk. In fact, for each DP problem, all states can be broadly classified into 3 categories,

  • Directly useful
  • Indirectly useful
  • Hopeless

  So, any subset with sum equal to kk is directly useful, subsets with sum less than kk are indirectly useful and subsets with sum greater than kk are hopeless.

  Recall that, in Knapsack problem, we also maintain another dimension of DP capturing the total weights we've already used so far. Since we need to delete some amount of edges from these blocks, let's define dp[i][j]dp[i][j] as the number of ways to delete exactly jj edges from blocks [0,…i][0,…i] such that the remaining graph is connected. Our answer would then be dp[n−1][j]dp[n−1][j] for all jj. This DP definition is incomplete, but in a contest, you're most likely to come up with this definition in the first try.

  So, what's the flaw with this DP definition? It only captures states which are directly useful. Since j1+j2j1+j2 could've become equal to kk, in this case, we could have 2 disconnected graphs which would've combined to created a connected one.

  Now we know that we are missing indirectly useful states in our DP table, but we are not sure which ones exactly. Whenever you face this Dilemma, just start the algorithm from the 0th0th element, and you'll quickly realize what you're missing.

  Notice that each block can contain at most 3 edges. Label them as top, bot and mid edges.

  Visual Representation

  In subset sum DP, the elements are processed in an online fashion. Meaning, we first compute our answer assuming that we only have the prefix [0,…i][0,…i] and we investigate the transitions when we introduce the ithith element. We then make one of 2 choices for the ithith element: Take or Leave. So, let's start with the first block. It only has a mid edge. We can either take it or leave it, which leaves us with 2 possibilities. Notice that our current DP does not handle the leave case, because it makes the graph disconnected. But we can see that it's a valid choice since the adjacent block can make it connected. This is our first hint on the new state that we need to introduce.

  Visual Representation

  Now, consider the second block, it has 3 edges, top, bot and mid. We can take or leave each edge independently, so there are 8 possibilities. Let us list down all 2∗82∗8 possibilities for both blocks combined. (The first column of result assumes that we kept the mid edge of the 0th0th block and the second column assumes that we ignored it).

  Visual Representation

  Can you spot the directly useful, indirectly useful and hopeless states from this graph? All states with one connected component are directly useful, and all the states where at least one connected component is isolated from the the incoming block is indirectly useful. Since that incoming block can only interact with the terminal xx and x∗x∗, we can conclude that any element which is a part of a connected component not containing xx or x∗x∗ is hopeless, because no matter what you do later, you cannot make the entire graph connected. Hence, for a state to be not hopeless, it should have no connected component not containing xx or x∗x∗.

  Visual Representation

  However, the editorial ignores all the hopeless states, which makes you wonder how did they suddenly guess that there can only be 2 states. But let's not do that, let's define 3 states, connected, two_connected, and hopeless, where two_connected represents an indirectly useful state where there are at most 2 connected components containing the terminal vertices. Although we keep saying 2-connected, we actually mean, the graph should have 2 connected components and with at least one of the terminal blocks. With these hints, we are now ready to define the actual DP definition:

  Define dp[i][j][state]dp[i][j][state] to be the number of ways to delete exactly jj vertices from blocks [0,…i][0,…i] such that the resulting graph is in the given state (connected, two_connected, hopeless).

  To perform the transitions, like subset-sum DP, we make 8 choices on the last block and take contribution from the previous states accordingly.

  A hopeless state can only lead to a hopeless state.

  If the last state was connected, and we drop the terminal top and bot edges, it'd become hopeless. If we take at least 2 terminal edges out of top, bot and mid, the graph would remain connected, else it becomes 2 connected.

  If the last state was two-connected, we are not allowed to drop the terminal top and bot edges. If we do, it leads to a hopeless state. Depending on whether we keep the terminal mid edge, it'll either lead us to connected or two_connected graph.

  Since we eventually won't use hopeless states, it does not matter whether we fill the correct values in it. And that's what the editorial does, ignore it altogether, but in my implementation, I do include some parts of it for clarity.

  My Implementation of the above Idea