SummerSky's blog

By SummerSky, 7 years ago, In English

A. Where Are My Flakes?

We can adopt two variables Lb and Rb to denote the range of values that the target can take, i.e., [Lb Rb]. Then, for each input, we update Lb and Rb accordingly to obtain a tighter range. Finally, if Lb<=Rb, it is sufficient to output Lb, Lb+1,...,Rb; otherwise output -1.

B. Serial Time!

It might take time to understand the descriptions, however it is in fact a problem about search on graph. We use P[L][R][C] to denote the character located in the L-th layer, R-th row and C-th column. The answer is just the total number of '.' that we can reach if starting from the initial given location. Thus, we can solve it by adopting BFS and count the number of '.' that we can meet. According to the problem, it is possible to reach at most another six positions from any position, i.e., P[L][R][C+1], P[L][R][C-1], P[L][R+1][C], P[L][R-1][C], P[L+1][R][C], P[L-1][R][C].

C. Mushroom Strife

By using x*y=GCD(x,y)*LCM(x,y), we can determine all the numbers in a connected component if any one of them is assigned with an initial value. Therefore, at first we select an arbitrary number x belonging to some connected component, and find out another number y to which it is connected. As we have been given GCD(x,y) and LCM(x,y), x must be a factor of LCM(x,y) and it must be no less than GCD(x,y). Thus, we can find all the factors of LCM(x,y), and only store those ones which are larger than or equal to GCD(x,y). Next, we enumerate these values, and for each of them, we implement BFS (or DFS) to calculate all the numbers belonging to this connected component. Then, for each connected pair of numbers, we check whether their GCD and LCM are exactly equal to the previously given ones or not. If they are the same during some enumeration, it means that we have found out some reasonable values for all the numbers in this connected component and thus we can move on to the next connected component; otherwise it implies that no reasonable values can be found.

For some given integer N, it takes O(sqrt(N)) complexity to find out all its factors. BFS has complexity O(n^2), and thus the total complexity is about O(sqrt(10^6)*100*100)=O(10^7).

  • Vote: I like it
  • -5
  • Vote: I do not like it