In problem H, was it known during testing that the most straightforward way of writing a brute force works? Just consider values from $$$1,2,\cdots,n$$$ in order, and decide whether to put each element on the left or right, write a dfs (with minimal pruning) and it passes.
It occured to me after I had submitted that it works because of the intended construction, the first branch tried will be $$$1,?,?,\cdots,?$$$, and the next branch will be $$$2,3,4,?,?,\cdots,?,1$$$.
I tried switching Left->Right to Right->Left and the code immediately gets TLE (xd), maybe it would be better to ask for anti-bitonic permutations after all?
Why is splitting by dividing by 100 the best solution
Like shouldn't dividing by 2 the best solution
I thought about converting all number Divisible by 2 Than divisible by 4 And so on till 1024
After that from lowest to biggest (1024,1024) , (2048. 1024), each will cost 1024 + 1000
But was able to get a solution of 2e6 coins
The statement of E is really terrible.
This will be one amazing contest
Considering enumerating all the layers from the bottom to the top, you'll find that different columns merges in a decreasing order of height of the walls, and tiles disappears in an increasing order of height of the columns. In all connected components, all the existing tiles are aligned to the right.
When at some column, a tile exists from the $$$i$$$-th second to the $$$j$$$-th second (inclusive), then if you only consider the total sum, it's equivalent to subtract $$$i$$$ and add $$$(j+1)$$$ at this column. Use prefix sum to optimize this procedure.
a $$$O(n)$$$ solution for E
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n+1), b(n*2+10);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) b[a[i]] ++;
int r = 0, l = 0, ans = 0;
for(int i=1;i<=n*2;i++) {
if(i <= r) {
r += b[i];
} else if(b[i] > k) {
ans = max(ans, r-l);
r = i + (b[i]-k);
l = i;
}
}
ans = max(ans, r-l);
cout << ans << '\n';
}
Don't cheat using GPT.
Like, what is the point of you cheating?
Corner case :)
I thought I'd misunderstood the problem...In one operation multiple energy level can be adjusted,right?
why my solution got a WA? I think I share the same thinking with you. ~~~~~ from collections import defaultdict def sol(): n,k=map(int,input().split()) li=list(map(int,input().split())) di=defaultdict(int) for i in li: di[i]+=1 cou=0 for i in range(1,4*n+1): if di[i]>k: di[i+1]+=di[i]-1 cou+=1
return cou
for _ in range(int(input())): print(sol()) ~~~~~ [https://codeforces.com/contest/2157/submission/350321034]
Don't have an account? Sign up