Idea: goncharovmike, prepared: pashka
Tutorial
Tutorial is loading...
Solution
t = int(input())
for _ in range(t):
a = [[int(x) for x in input().split()] for i in range(4)]
x = [p[0] for p in a]
dx = max(x) - min(x)
print(dx * dx)
Idea: pashka, prepared: ikrpprppp
Tutorial
Tutorial is loading...
Solution
t = int(input())
for _ in range(t):
n = int(input())
start = [int(x) for x in input()]
finish = [int(x) for x in input()]
pairs = list(zip(start, finish))
add_amnt = sum(int(a < b) for a, b in pairs)
rmv_amnt = sum(int(a > b) for a, b in pairs)
print(max(add_amnt, rmv_amnt))
Idea: step_by_step, prepared: step_by_step, Vladosiya
Tutorial
Tutorial is loading...
Solution
t = int(input())
for _ in range(t):
n, f, a, b = map(int, input().split())
m = [0] + [int(x) for x in input().split()]
for i in range(1, n + 1):
f -= min(a * (m[i] - m[i - 1]), b)
print('YES' if f > 0 else 'NO')
Idea: Vitaly239239, prepared: pashka
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
struct test {
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<int> b(m);
for (int i = 0; i < m; i++) cin >> b[i];
sort(a.begin(), a.end());
sort(b.rbegin(), b.rend());
vector<int> c(n);
long long s = 0;
for (int i = 0; i < n; i++) {
c[i] = b[m — n + i];
s += abs(c[i] — a[i]);
}
long long res = 0;
for (int k = 0; k <= n; k++) {
res = max(res, s);
if (k < n) {
s -= abs(c[k] — a[k]);
c[k] = b[k];
s += abs(c[k] — a[k]);
}
}
cout << res << "\n";
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
test().solve();
}
return 0;
}
Idea: ikrpprppp, prepared: ikrpprppp
Tutorial
Tutorial is loading...
Solution
def solve():
h, w, xA, yA, xB, yB = map(int, input().split())
if (xA - xB) % 2 == 0:
winner = "Bob"
if xA >= xB:
win = False
elif yA == yB:
win = True
else:
if yA < yB:
n_turns = yB - 1
else:
n_turns = w - yB
win = xB - 2 * n_turns >= xA
else:
winner = "Alice"
xA += 1
yA += 0 if yB - yA == 0 else 1 if yB - yA > 0 else -1
if xA > xB:
win = False
elif yA == yB:
win = True
else:
if yA < yB:
n_turns = w - yA
else:
n_turns = yA - 1
win = xB - 2 * n_turns >= xA
print(winner if win else "Draw")
t = int(input())
for _ in range(t):
solve()
Idea: Vitaly239239, prepared: Vitaly239239
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
long long precalc[322][200322];
long long precalci[322][200322];
void solve() {
int n, q;
cin >> n >> q;
vector<long long> a(n);
int pivot = 1;
while (pivot * pivot < n) {
pivot++;
}
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < pivot; i++) {
for (int j = 0; j <= i; j++) {
precalc[i][j] = 0LL;
precalci[i][j] = 0LL;
}
for (int j = 0; j < n; j++) {
precalci[i][j + i + 1] = precalci[i][j] + a[j] * (j / (i + 1) + 1);
precalc[i][j + i + 1] = precalc[i][j] + a[j];
}
}
while (q--) {
int s, d;
long long k;
long long ans = 0;
cin >> s >> d >> k;
s--;
if (d > pivot) {
for (int i = s; i <= s + (k - 1) * d; i += d) {
ans += a[i] * ((i - s) / d + 1);
}
cout << ans << " ";
continue;
}
long long last = s + d * k - d;
int first = s;
cout << precalci[d - 1][last + d] - precalci[d - 1][first] -
(precalc[d - 1][last + d] - precalc[d - 1][first]) * (first / d) << ' ';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tests;
cin >> tests;
while (tests--) {
solve();
if (tests) cout << "\n";
}
return 0;
}
Idea: Vitaly239239, prepared: goncharovmike
Tutorial
Tutorial is loading...
Solution
//ciao_chill
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, k;
vector<vector<int>> a;
bool prov(int i, int j) {
return 0 <= i && i < n && 0 <= j && j < m;
}
int ans() {
int cnt = 0;
int dp[n][m];
int pref[n][m];
int pref_up[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
pref_up[i][j] = a[i][j];
if (prov(i - 1, j))
pref_up[i][j] += pref_up[i - 1][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = m - 1; j >= 0; j--) {
pref[i][j] = a[i][j];
if (prov(i - 1, j + 1))
pref[i][j] += pref[i - 1][j + 1];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dp[i][j] = pref_up[i][j];
if (prov(i - k, j))
dp[i][j] -= pref_up[i - k][j];
if (prov(i, j - 1))
dp[i][j] += dp[i][j - 1];
if (j < k) {
int i1 = j - k + i;
if (i1 >= 0)
dp[i][j] -= pref[i1][0];
}
else
dp[i][j] -= pref[i][j - k];
if (prov(i - k, j))
dp[i][j] += pref[i - k][j];
cnt = max(cnt, dp[i][j]);
}
}
return cnt;
}
void solve() {
cin >> n >> m >> k;
k++;
char c;
bool st[n][m];
a.resize(n);
for (int i = 0; i < n; i++) {
a[i].resize(m);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
{
cin >> c;
st[i][j] = (c == '#');
a[i][j] = st[i][j];
}
}
int mx = ans();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = st[n - i - 1][j];
}
}
mx = max(mx, ans());
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = st[i][m - j - 1];
}
}
mx = max(mx, ans());
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = st[n - i - 1][m - j - 1];
}
}
mx = max(mx, ans());
cout << mx << '\n';
}
signed main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
int tt;
cin >> tt;
while (tt--)
solve();
return 0;
}
The problems were nice. I solved A-E in-contest and F about 10 hours later.
For some reason I feel like E was easier to figure out than D.
Also my F submission is in-queue even though it got accepted earlier (?)
prefixsum forces
Beautiful problems specially a to f Couldnt figure out g in time I misread a,b both which was abs terrible since the penalty I got from both was almost as twice as usual For A I thought that the squares aren't parallel to the Axis so I wrote a function to validate the squares, the i assumed every possible square and find the max Before I code the last part just reread the ! Question and...
Video solution of F (Chinese)
Why D can use prefix sum without considering absolute value symbols?
I wonder what the intention for the strict limits for F was. The model solution 241944593 runs in approximately 1s, which is around half of the limit, and it consumes almost full memory allowed (1010600 KB).
The very same solution reaches very close at the limit just by swapping the array dimensions that leads to a worse cache hit rate: 241946807, which is what my own solution 241780298 exactly did and barely passed.
It's quite unfriendly with other slower languages, and with only a few trivially inefficient elements it's easy to exceed the time limit as well as the memory limit. It would've made more sense to set a bit more lenient TL and ML as done in problem G.
It's always a tradeoff. The problem here is that the optimized naive solution, written in good C++ works about 2.5 s, so we cannot extend the TL any further.
That's a lot faster than I imagined. Guess you couldn't really do much about the ML as well as Polygon only allows up to 1024 MB ML.
Oh, i checked again and I was wrong, we added more tests with many long sequences, and not it works more than 4s, but still pretty close.
indeed the time limit is too tight.
same code after converting to c++ by gpt works in 900ms whereas it gives tle on test 3 in java
Yes, maps and lists are much slower in Java
But there are a lot of accepted submissions in Java, actually. Here is one for example https://codeforces.me/contest/1921/submission/243773379
It's sad that you cannot use standard java containers in problems with such strict time limits, but I don't think we can do anything about it.
I solved a lot of contests in Java, and at some point I learned how to implement anything using only simple arrays, but it's painful, I agree. That's why I moved to C++ for contests at some point.
Thanks for the reply
Instead of map and arraylists, I used 2d array and the case which was giving TLE now passes in 450ms
Solution for G without prefix sums: 241838352.
The idea is very similar to the author's solution with prefix sums over $$$O(nm)$$$, but in this solution the recalculation is done over $$$O(\text{min}(n, m))$$$. In this solution, I go through all the red squares (from the parsing) and subtract them, and I also go through and add all the green squares.
The total time complexity of this solution is $$$O(nm\ \text{min}(n, m))$$$.
E was doable
Fr but never thought E would be just if elses lol
i also had same intution for D as editorial ,but so much less confidence in contest .can anyone please justify why the greedy approach(same as editorial) will work.
@authors
Always, the difference between minimum and maximum is the max possible to get... Wym
it is maximum diff now ,but by taking out maximum such element,we might be reducing maximum difference for second smallest element. you are saying local optimum decision will lead to global optimum(that is exactly greedy),i am asking why it will always result in optimum answer
Usually proving that swapping any two elements doesn't improve the answer is enough.
See my submission first before reading the proof.
The greedy approach can be neatly summarized as choosing the pair that gives the largest absolute difference and then we can pop the two corresponding elements and then we can continue doing the greedy.
We need to prove two things:
(1) That the largest distance is either
abs(a.front() - b.back())orabs(a.back() - b.front()).Proof. Note that any selected pair
a[i]andb[j]have an associated direction froma[i]tob[j]in the number line (either right or left). If the direction is right, we can make the difference larger if we changea[i]toa.front()andb[j]tob.back(). The case is similar to if the direction is left.(2) Choosing the largest difference is optimal.
Proof. Without loss of generality, assume that
abs(a.front() - b.back())gives the largest difference. Assume that the two pairs are(a.front(), b[j])and(a[i], b.back())(other cases like whena.front()orb.back()is not paired is trivial). Then by swapping, it's easy to visualize that(a.front(), b.back())and(a[i], b[j])is not worse.can u pls elaborate (2) choosing largest difference is optimal "Assume that the two pairs are (a.front(), b[j]) and (a[i], b.back())" what are we assuming
Then by swapping, it's easy to visualize that (a.front(), b.back()) and (a[i], b[j]) is not worse. After swapping what is not worse than what?
In the second part, he's saying 'let's assume that we pair up
a.front()with some other element inbthat is notb.back(), and pairb.back()with something else ina'. Then if we swapb[j]withb.back()to get the pairs(a.front(), b.back())and(a[i], b[j]), the sum of the absolute differences in this case won't be worse than the previous one.The Solution Code of D may meet some display problem?
On my view, there are some
—in the brackets ofabs(), they look like:I don't know if it's an issue with my browser.
actually the &mdash is the minus sign -
Can someone explain why are we taking d=sqrt(q) ?
We want to minimize $$$nd + qn/d$$$, When we increase $$$d$$$, the first part will increase, and the second part will decrease, and the minimal point will be when they become equal: $$$nd = qn/d$$$, from that we can get $$$d=\sqrt{q}$$$.
We can also sort queries by $$$ (d,s \mod d) $$$, and for all queries with same $$$ (d,s \mod d) $$$, we preare the prefix sum using items : $$$ a_{s \mod d}, a_{d+s \mod d},a_{2 \cdot d+s \mod d}, \cdots $$$, which are $$$ \frac{n}{d} $$$ items in total. For some fixed $$$d$$$, $$$d$$$ queries would be needed to make prefix sum calculation cover the whole $$$n$$$ array. Worst case is when $$$ 1+2+3+ \cdots + x=q$$$, get $$$x \approx \sqrt q $$$ , so the total time complexity of prefix sum preparing is $$$n \sqrt q $$$.
Can Problem D be solved with dynamic programming approach? dp[i][j] = maximum diff when a[i] is paired with b[j].
transition: dp[i][j] = abs(a[i]-b[j])+max value from dp[i-1] (other than dp[i-1][j] as jth element is paired with current element.)
return max value from dp[n-1];
is this approach correct?
Editorial is not attached as "Tutorial" in problem statement page yet. May it would be fixed.. UPD: Fixed Now..
Can someone help my find out why my submission to E gives WA?:
expected: 'DRAW', found: 'BOB'why you are doing wins==true in if(w — ya — 1 <= dh /2) and in else aslo ? in else there will be draw
Thank you!
What a silly mistake...
who setted this problem G and why
Sirs teaching Englishs. 😂
set is an irregular verb and isn't followed by "ed" in past tense
After 18 contests, I've finally reached specialist, and so far, the only active specialist in Seattle! :)
I have an alt. sol for F that uses memoization.
Suppose we split the array into $$$d$$$ subsequences of increment $$$d$$$ for every $$$d$$$ from $$$1$$$ to $$$n$$$.
Ex: Original array is $$$[1,2,3,4,5]$$$
$$$d = 1: [1,2,3,4,5]$$$
$$$d = 2: [1,3,5],[2,4]$$$
$$$d = 3: [1,4], [2,5], [3]$$$ (You get the idea)
If we can generate both the prefix sums and the partial sums of the values multiplied by their index (eg $$$[1,3,5]$$$ becomes $$$[1\cdot1, 1\cdot1 + 3\cdot2,1\cdot1 + 3\cdot2 + 5\cdot3] = [1,7,22]$$$.
We can use these two precomputed arrays to evaluate the queries efficiently. However, precomputing all of these will be too slow, instead, we can create them and store them as we process queries since we don't need to precompute every subsequence.
To store them, we would just need something like a map, the key would be a pair $$$(d,s\%d)$$$ where $$$d$$$ is the increment and $$$s\%d$$$ represents the first element's index of the subsequence.
The worst case is that for every query, we have to create both types of prefix sum arrays for the largest, not-yet-computed sequence. It should be clear that given array of size $$$n$$$ and $$$n$$$ queries, the total iterations should be around $$$O(n\sqrt{n})$$$ (or plus a log factor depending on which map).
My code: 241999941 (which uses custom hash + unordered map)
In problem c, doesn't the phone lose charge at 0 moment and also will the phone lose charge after it sends a message or before?
could someone explain?
Can please tell me why is this submission giving a TLE for Problem F? (Time complexity: $$$O((N + Q) * sqrt(N))$$$)
Don't declare vectors(prefix sum) for every test case, make them of fixed size [10^5+1][320]
I have a nice greedy solution to D which just selects the largest possible distance at every iteration until all elements in $$$a$$$ have been paired, but I don't have a proof.
Code: 242031960
Can anyone prove it?
I have also used this method during the contest.
In sorted $$$ a_1, a_2, \cdots a_n $$$ and sorted $$$b_1,b_2, \cdots b_m$$$ , WLOG, let us assume max diff value is $$$ | a_1 - b_i |$$$. Obviously $$$i$$$ could only be $$$1$$$ or $$$m$$$ .
If $$$i=1$$$,
If $$$i=m$$$,
Assume in optimal solution, $$$b_j$$$ paired with $$$a_1$$$ ,
if $$$b_m$$$ is not paired with any value in $$$a$$$, we can move $$$a_1$$$ from pair with $$$b_j$$$ to $$$b_m$$$ to get a better solution.
If $$$b_m$$$ is paired with some $$$a_k$$$ , since $$$a_1<a_k , b_j<b_m , a_1<b_m , |a_1-b_j|<|a_1-b_m|$$$ , it can be shown that $$$|a_1-b_j|+|a_k-b_m| \leq |a_1-b_m|+|a_k-b_j|$$$.
So, pair $$$a_1$$$ with $$$b_m$$$ must be in some optimal solution.
Don't understand the equations in F at all. Feels like editorial has been written for someone who already understands the solution.
"The key idea is that we know how to calculate the sum (i−l+1)⋅ai for l≤i≤r fast – we need to calculate all prefix sums i⋅ai and ai for 1≤i≤k, then take the difference between the r-th and (l−1)-th of i⋅ai and subtract the difference between the r-th and (l−1)-th multiplied by l−1"
This certainly could have been explained in a better way.
Hello everyone. I am having trouble with problem F. I understand that its a standard problem but the part where we need to hop by d steps is making it hard for me to understand.
I have a scenario can someone please explain on this. d = 5, k=6, s=3
Here the sequence required is: a3 + 2a8 + 3a13 ... 6a28
I have 2 series which can be computed in O(1): S1 = a1 + a2 + a3 ... an S2 = a1 + 2*a2 + 3*a3 ... n*an
How can I get the required sum if someone is available to dry run it.
Precomputed prefix sums starting from index 3 with step size 5:
ps1 = a3 + 2a8 + 3a13 + 4a18 + 5a23 + ...
ps2 = a3 + a8 + a13 + a18 + a23 + ...
Let's say you want to compute the sum for 3 elements starting from index 13:
a13 + 2a18 + 3a23 = (3a13 + 4a18 + 5a23) -2*(a13 + a18 + a23)
You can get get these two parts from prefix sums ps1 and ps2.
Maybe putting summed indexes this way helps:
If you need sum from 4 to 6 then you have to subtract triangle 1..3 and rectangle of top 3 lines which is (4+5+6)*3 = (sum without multiplication) * (s/d)
After some optimisations you get answers quite fast.
Problem F can be solved with the idea of Square Decomposition.
there is and issue in G testcases
my O(n*n*m) solution did pass without TL 255464766
Shit problem G