Problem Statement:
Codeforces Round #356 (Div. 2) D. Bear and Tower of Cubes
Summary:
Given m < 10^15, find the largest (k, X) such that a[1]+a[2]+...+a[k] = X <= m, each a[i] is a perfect cube, and for a given X, a[i] is the largest cube such that a[1] + ... + a[i] <= X.
Showing posts with label Constructive Algorithm. Show all posts
Showing posts with label Constructive Algorithm. Show all posts
Sunday, June 12, 2016
Saturday, January 31, 2015
Codeforces 441D - Valera and Swaps
Problem Statement:
441D - Valera and Swaps
Solution:
This problem is somewhat tedious in a sense that we need accuracy in swapping indexes and content of arrays.
The idea to solve this problem is from the (might be routine, but not so obvious on first try) observation that the minimum number of swaps required to place every element to its correct position is equal to the total number of elements in the "misplaced chain" minus one. What I mean by the misplaced chain is: Let a[i] be the elements in the sequence, and p[i] be the index of element i in array a[i]. If we start from position cur = i, and trace down all elements cur = p[cur], we will get a chain of misplaced elements. There will be several disjoint chains, and hence we can total up the total minimum number of swaps necessary to restore each element in each chain to its correct position, call this sum S. We can compare S and m, which leads us to three cases:
441D - Valera and Swaps
Solution:
This problem is somewhat tedious in a sense that we need accuracy in swapping indexes and content of arrays.
The idea to solve this problem is from the (might be routine, but not so obvious on first try) observation that the minimum number of swaps required to place every element to its correct position is equal to the total number of elements in the "misplaced chain" minus one. What I mean by the misplaced chain is: Let a[i] be the elements in the sequence, and p[i] be the index of element i in array a[i]. If we start from position cur = i, and trace down all elements cur = p[cur], we will get a chain of misplaced elements. There will be several disjoint chains, and hence we can total up the total minimum number of swaps necessary to restore each element in each chain to its correct position, call this sum S. We can compare S and m, which leads us to three cases:
Friday, January 9, 2015
Codeforces 453C - Little Pony and Summer Sun Celebration
Problem Statement:
453C - Little Pony and Summer Sun Celebration
Solution:
(How did they come up with such a cute name for a problem statement, I wonder)
A pretty interesting graph problem, which is more of a test on structure construction. The official editorial to this problem is already perfectly clear, I'm writing this purely for my future references.
To solve the problem the brute force way, one can choose any node as a root, and run a DFS on this root, in the following manner: From root, visit the next available odd-parity node, and come back. This works because every nodes in between the path between root and the odd-parity node will be visited twice as the person go forth and back to root. Hence each time we will be eliminating one odd-parity node from consideration, which is nice. Finally, we check how many times we visited root, and if the parity does not match, we simply remove a root node on the tail of the path (i.e., the person did not come back to the root eventually). However, this approach does not guarantee the final path to be within 4n limit.
453C - Little Pony and Summer Sun Celebration
Solution:
(How did they come up with such a cute name for a problem statement, I wonder)
A pretty interesting graph problem, which is more of a test on structure construction. The official editorial to this problem is already perfectly clear, I'm writing this purely for my future references.
To solve the problem the brute force way, one can choose any node as a root, and run a DFS on this root, in the following manner: From root, visit the next available odd-parity node, and come back. This works because every nodes in between the path between root and the odd-parity node will be visited twice as the person go forth and back to root. Hence each time we will be eliminating one odd-parity node from consideration, which is nice. Finally, we check how many times we visited root, and if the parity does not match, we simply remove a root node on the tail of the path (i.e., the person did not come back to the root eventually). However, this approach does not guarantee the final path to be within 4n limit.
Subscribe to:
Posts (Atom)