Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
print(''.join(sorted(input())))
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
x = [ord(c) - ord('0') for c in input()]
n = len(x)
for i in range(n - 2, -1, -1):
if x[i] + x[i + 1] >= 10:
x[i + 1] += x[i] - 10
x[i] = 1
break
else:
x[1] += x[0]
x.pop(0)
print(''.join([chr(c + ord('0')) for c in x]))
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n = int(input())
k = list(map(int, input().split()))
h = list(map(int, input().split()))
st = []
for i in range(n):
st.append([k[i] - h[i], k[i]])
st.sort()
l, r = -1, -1
ans = 0
for it in st:
if it[0] >= r:
ans += (r - l) * (r - l + 1) // 2
l, r = it
else:
r = max(r, it[1])
ans += (r - l) * (r - l + 1) // 2
print(ans)
1626D - Турнир боевого искусства
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
calc = 1
nxt = [1, 0]
for _ in range(int(input())):
n = int(input())
a = sorted(list(map(int, input().split())))
while calc <= n:
for i in range(calc):
nxt.append(calc - i - 1)
calc *= 2
left = []
for i in range(n + 1):
if i == 0 or i == n or a[i] != a[i - 1]:
left.append(i)
else:
left.append(left[-1])
mid = 1
ans = n + 2
while mid <= n:
for len1 in range(n + 1):
if left[len1] == len1:
len2 = left[min(n, len1 + mid)] - len1
len3 = n - len1 - len2
ans = min(ans, nxt[len1] + (mid - len2) + nxt[len3])
mid *= 2
print(ans)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
vector<int> g[N];
int cnt[N];
int c[N];
vector<int> g2[N];
int par[N];
int used[N];
void dfs(int x, int p = -1)
{
par[x] = p;
for(auto y : g[x])
if(y != p)
{
dfs(y, x);
cnt[x] += cnt[y];
}
cnt[x] += c[x];
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &c[i]);
for(int i = 1; i < n; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0);
for(int i = 0; i < n; i++)
for(auto j : g[i])
{
if(i == par[j])
{
if(c[i] == 1 || cnt[0] - cnt[j] > 1)
g2[i].push_back(j);
}
else
{
if(c[i] == 1 || cnt[i] > 1)
g2[i].push_back(j);
}
}
queue<int> q;
for(int i = 0; i < n; i++)
{
if(c[i] == 1)
{
q.push(i);
used[i] = 1;
}
}
while(!q.empty())
{
int k = q.front();
q.pop();
for(auto y : g2[k])
if(used[y] == 0)
{
used[y] = 1;
q.push(y);
}
}
for(int i = 0; i < n; i++)
printf("%d ", used[i]);
puts("");
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int L = 720720;
int add(int x, int y, int m = MOD)
{
x += y;
if(x >= m) x -= m;
return x;
}
int mul(int x, int y, int m = MOD)
{
return (x * 1ll * y) % m;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int inv(int x)
{
return binpow(x, MOD - 2);
}
int divide(int x, int y)
{
return mul(x, inv(y));
}
int main()
{
int n, a0, x, y, k, M;
cin >> n >> a0 >> x >> y >> k >> M;
vector<int> arr(n);
arr[0] = a0;
for(int i = 1; i < n; i++)
arr[i] = add(mul(arr[i - 1], x, M), y, M);
int ans = 0;
int total_ways = binpow(n, k);
int coeff = mul(divide(total_ways, n), k);
vector<vector<int>> dp(k, vector<int>(L));
for(int i = 0; i < n; i++)
{
int p = arr[i] / L;
int q = arr[i] % L;
dp[0][q]++;
ans = add(ans, mul(p, mul(L, coeff)));
}
int cur_coeff = divide(total_ways, n);
for(int i = 1; i <= k; i++)
{
for(int j = 0; j < L; j++)
{
int cur = dp[i - 1][j];
if(i < k)
dp[i][j] = add(dp[i][j], mul(n - 1, cur));
ans = add(ans, mul(j, mul(cur, cur_coeff)));
if(i < k)
dp[i][j - (j % i)] = add(dp[i][j - (j % i)], cur);
}
cur_coeff = divide(cur_coeff, n);
}
cout << ans << endl;
}
it was a really cool round! it's a pity that he was unrated :(
For problem C, you don't have to worry about half-intervals. Here is my (badly written) code for C with segments that can be of length 0.
143049989
Can anybody please tell me how this code is working for problem D : 143147171.
Is this logic correct or are the test cases weak?
I suppose the logic is correct. It uses a greedy approach as mentioned in the editorial. The fact that lengths can only be the power of 2 is used to reduce the time complexity of nested loops.
Same solution of B, but with regex (with code pattern): Perl — 143030768, (13+).
Can somebody explain how binary search implemented in problem D?
Can somebody please explain me how Binary search is applied on problem D????
C can be solved in $$$O(n)$$$, walking though array backwards or using stack.
Also using two pointers can achieve %O(n)%
D can be solved in $$$O(n)$$$. the submission.
The steps of the algorithm is:
Calculate if we want to choose at most $$$i$$$ smallest numbers, how many numbers can we choose.
Calculate if we want to choose at most $$$i$$$ largest numbers, how many numbers can we choose.
Go through $$$i,j$$$ in the powers of two. $$$i$$$ means the number of the first division after inviting extra participants. $$$j$$$ means the number in the third division. Then we can know how many original participants will be in the second division. So it's easy to find the number of participants in the second division. For every $$$i,j$$$, we choose the smallest sum of three divivions, and minus it with $$$n$$$. It will be the answer.
what about the case when i smallest numbers and j largest numbers are not disjoint there is some overlap ?
For example: n=2 a={1,2}. Let i=1 and j=1, which means there is one person in the left segment while one person in the right segment. However there is no way to add another person to the middle segment since there is no integer between 1 and 2. In short, your code gives the right answer in a wrong way.
In Problem D,
I am not getting why the length of the middle segment should be power of 2 for the optimal solution.
Can someone help?
I also don't understand this
It's not the middle segment that should be a power of $$$2$$$. We iterate on the size of the middleweight category, which has to be a power of $$$2$$$.
Can anyone please explain C in further depth, I'm unable to understand
E.g. you have:
[_][_][_][_][4][_][_][5]
Go backwards decreasing:
[_][_][_][_][4][_][_][5]
[_][_][_][_][4][_]<4>[5]
[_][_][_][_][4]<3>[4][5]
[_][_][_]<3>[4][3][4][5]
[_][_]<2>[3][4][3][4][5]
[_]<1>[2][3][4][3][4][5]
Go forward to make array increasing:
[_][1][2][3][4]<5>[4][5]
[_][1][2][3][4][5]<6>[5]
[_][1][2][3][4][5][6]<7>
Sum it up.
My Solution for problem D works in O(log(N)^4) It works as followed: Let the goal number of people for each 3 chunks be A=2^x,B=2^y,C=2^z We iterate on x=0..log(N)+1, y=0..log(N)+1, z=0..log(N)+1 We want a[1]+...+a[x] <= A, a[x+1]+...+a[y]<=B, a[y+1]+...+a[N]<=C We also want each of them as close as to their goals. We can then binary search the best x and y. The optimal solution must exists in one of these configurations.
I have a little problem about problem F: Why should we add $$$k\cdot n^{k-1}\cdot x\cdot L$$$ to the answer instead of $$$n^k\cdot x\cdot L$$$?
The multiplier $$$k \cdot n^{k-1}$$$ is the total number of times an element is chosen over all ways to choose elements on the iterations. It can be treated as the number of occurrences of some integer $$$i$$$ in all $$$k$$$-element vectors, where each element is in $$$[1, n]$$$. It is $$$k \cdot n^{k-1}$$$ since the total number of integers in these vectors is $$$k \cdot n^k$$$, and each of $$$n$$$ integers occurs the same number of times.
I see.Thank you.
E was really nice.
Can someone please explain for Problem E, I tried this test case - for the solution mentioned in editorial
input —
the output is —
As per my understanding, according to the problem st. shouldn't it be, only black nodes and the ones adjacent to it, i.e. 1, 13, 9, 2, 12, 8
Can someone explain this?
Upd: Sorry I gave wrong input.
It doesn't have to be only black nodes and the ones adjacent to it. Consider an edge which links two white nodes. If the number of black nodes on the left side of this edge (in the entire tree) are 2 or more, then we can go from right to left along this edge, and similarly for left to right. The adjacent-black-node condition is only needed when the number of black nodes on one side of an edge are less than two.
Example: If your tree is 1-2-3-4-5 and 1,2 are black nodes. Then from 5 you can select 1 and move the chip to 4. Then you can select 2 and move the chip to 3, and so on. So, whenever you have 2 or more black nodes on one side of the edge, you won't get forced back as you move along the edge in that direction.
Got it, thanks for the explanation!
Problem C is a lot simpler using stack, when we introduce a new segment, we pop the stack for the segments that were overlapping, then in the end answer is simply derived from the segments left in stack as they are all non overlapping.
Here is my code for the same 143004113
In Problem D, I ran 3 nested loops i, j, k for the power of 2 the first second and third segment needs to be, and checked if it was possible to divide the array into these groups, if it was possible, simple store the minimum for every iteration of i, j, k. answer in any iteration will be 2^i+2^j+2^k-n.
Here is my code for the same 143024306
got the same idea as you!
it's cool to solve it in $$$O(n + \log^4 n)$$$ instead of $$$O(n \log n)$$$
can even solve in $$$O(n + \log^3 n)$$$ after some optimization
143025919
question statement of problem B says "You are given a decimal representation of an integer x". Initially, I didn't get that the input in problem B is a string or an integer....?
firstly, I have tried my solution with an integer and got runtime error in test case 3 and later have tried with a string as input and my solution got accepted.
Moral: a decimal representation of an integer x is a String.
Correct Moral: read constraints carefully next time.
C has a tag of binary search, can someone please share/explain a binary search based solution if they have implemented it?
E.
Have you played a computer game Desktop Tower Defense?
1 . We cut off all white branches. Later we will need some of them, so we need to have e.g. either 1) a copy of an initial graph, or 2) save these white branches to a new graph, which is more efficient way, or 3) we can color branches instead of cutting. Additionally we need to save a node to which a particular cut branch is adjacent. But if a branch is adjacent to a black node we also can drop it, because we have an obvious answer: from all nodes of that branch we can move to the black node. Cutting a white branch is simple loop: we remove white leafs until there are no white leafs left.
The remaining graph has all of its leafs black.
2 . Now we can check if there are any three black nodes on the same way. If so then we can move to black node from any point of the graph. If not then we need to process further. Simplest way to check that — compare the number of leafs with the number of overall black nodes.
There is also the case when the number of black leafs is more then 2 and one of the black leafs is adjacent to a node which has more than two edges. Answer is 'all 1', because that leaf attracts to itself from any of 2+ branches with the help of another branch.
3 . If we haven't obtained an answer 'all 1', then our graph can be seen as this:
where square brackets mark black nodes, parentheses mark white nodes, $$$m$$$ is a number of black leafs, and all $$$k_i \ge 2$$$.
We can see that it is possible to move to black nodes only from the adjacent nodes: $$$(k_i-1,i), i = 1 \dots m$$$. All these adjacent nodes are unreachable from the rest of the tree because they have only one attractor leaf on their branch ($$$i$$$), and $$$m-1 \ge 1$$$ detractors from other branches.
4 . Now we check for all nodes with zero answer if it is adjacent to previously cut branch (step 1). If so then all that branch has also zero answer. Implementing e.g. with BFS.
After step 2, we can do: for all black leafs we check if adjacent node is white and if so then we paint it black and cut the leaf. Later we check if the number of black leafs is equal to number of overall black nodes. If yes, we obtain similar a graph as in step 3, but all $$$k_i \ge 1$$$, otherwise answer 'all 1'.
Problem E was not that tough, I have solved it with in out dp; Solution link
Problem C can be solved with $$$\mathcal O(n)$$$.
Hi everyone, I want to share my solution for C which is $$$O(n)$$$.
Here is my submission:144945360.
We will consider an extra first monster at second $$$1$$$ with health $$$0$$$.
We might need more than the monster's health to kill it because we have to wind up to kill stronger ones later. More particularly, in order to kill $$$i-th$$$ monster with $$$x$$$ mana, we must kill $$$(i-1)-th$$$ monster with no less than $$$x-(k[i] - k[i - 1])$$$ mana. So it is possible to set $$$h[i]$$$ to $$$max(h[i],h[i+1]+k[i]-k[i+1])$$$, with $$$i=n-1,n-2,\dots , 1,0$$$. Then the following condition holds: "For every $$$0 \leq i \leq n - 1$$$, if we kill $$$i-th$$$ with $$$h[i]$$$ mana, we can also kill $$$(i+1)-th$$$".
Then, we only need to calculate the real mana used to kill $$$(i + 1)-th$$$ monster after killing the $$$i-th$$$ one. Firstly we check if it's possible to start from $$$1$$$ the next step and wind up. We can achieve that by using variable
step
denoting the counts of steps we have before encountering the next monster. Ifstep
is not less than $$$h[i+1]$$$, then we can, otherwise we cannot. If we can't, the only option is to start from the current mana.It’s interesting to notice that in D’s solution the while loop has the condition of “mid <= n” instead of “len1 + mid <= n”. Actually I can prove “len1 + mid / 2 <= n” will not miss cases but cannot prove the other two condition’s correctness.
D can be solved with dp + segment tree in $$$O(nlog^2 n)$$$.
First, sort all numbers and then make a new array $$$b$$$ that stores the frequencies of each unique number.
Let $$$ f(x) = 2^{\lceil log_2x \rceil}, g(x) = f(x) - x, sum_{l,r} = \sum\limits_{i=l}^rb_i$$$
The new array can be partitioned into AT MOST 3 subarrays and in the cases that we use only 2/1 subarrays, we need to make up for it by bringing in 1/2 persons.
$$$dp[i][j] =$$$ answer if we consider the first $$$i$$$ numbers and divide it into $$$j$$$ subarrays
Base case: $$$dp[i][1] = g(sum_{1,i})$$$
It's easy to see that $$$dp[i][k] = min(dp[j][k-1] + g(sum_{j+1,i})), j < i, 2 \leq k \leq 3$$$
This is $$$O(n^2logn)$$$ and is too slow, but it can be sped up.
Notice, $$$sum_{j+1,i} = sum_{1,i}-sum_{1,j}$$$
$$$dp[i][k] = min(dp[j][k-1] + g(sum_{1,i}-sum_{1,j}))$$$
$$$dp[i][k] = min(dp[j][k-1] + f(sum_{1,i}-sum_{1,j})+sum_{1,j})-sum_{1,i}$$$
Actually, $$$f(sum_{1,i}-sum_{1,j})$$$ changes at most $$$logN$$$ times and therefore the array can be grouped into at most $$$logN$$$ groups based on those changes.
Let $$$f(sum_{1,i}-sum_{1,j}) = 2^x $$$ for some $$$0 \leq x \leq logN$$$
Then: $$$ 2^{x-1} < sum_{1,i}-sum_{1,j} \leq 2^x$$$ and with simple math we get:
$$$ sum_{1,i}-2^x \leq sum_{1,j} < sum_{1,i}-2^{x-1}$$$
So we can see that all $$$j$$$ that satisfy this inequality are in the same group $$$x$$$ and also consecutive.
We then brute-force for all $$$x$$$ and for a fixed $$$k$$$, try to get the minimum $$$dp[j][k]$$$ such that $$$sum_{1,j}$$$ is in the desired range. This is clearly RMQ and can be done with segment trees(Note: You need $$$k-1$$$ different segment trees for each $$$k$$$ in the dp transition, in this case $$$k=3$$$ since we are dividing into at most 3 subarrays).
Solution
Dumb rerooting solution for problem E: link .
In problem E if there were 3 black vertices why shouldn't the answer be 1 for all vertices