Идея: BledDest
Разбор
Tutorial is loading...
Решение (Ne0n25)
for i in range(int(input())):
print(len(input()))
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int x; cin >> x;
int steps = 0;
while (steps * (steps + 1) < 2 * x)
steps++;
if (steps * (steps + 1) / 2 == x + 1)
steps++;
cout << steps << endl;
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
void solve() {
int x, y;
cin >> x >> y;
cout << x - 1 << " " << y << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
1455D - Последовательность и обмены
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n, x;
cin >> n >> x;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
if(is_sorted(a.begin(), a.end()))
{
cout << 0 << endl;
continue;
}
vector<vector<int>> dp(n, vector<int>(501, int(1e9)));
for(int i = 0; i < n; i++)
{
if(a[i] > x && (i == 0 || a[i - 1] <= x))
dp[i][x] = 1;
if(i < n - 1 && a[i] > a[i + 1])
break;
}
int ans = int(1e9);
for(int i = 0; i < n; i++)
for(int j = 0; j <= 500; j++)
{
if(dp[i][j] == int(1e9))
continue;
if(i == n || (j <= a[i + 1] && is_sorted(a.begin() + i + 1, a.end())))
ans = min(ans, dp[i][j]);
bool good = true;
for(int k = i + 1; k < n; k++)
{
int pr = k == i + 1 ? j : a[k - 1];
if(good && a[i] >= pr && a[i] < a[k])
dp[k][a[i]] = min(dp[k][a[i]], dp[i][j] + 1);
good &= a[k] >= pr;
}
}
if(ans == int(1e9))
ans = -1;
cout << ans << endl;
}
}
Решение 2 (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n, x;
vector<int> a;
inline bool read() {
if(!(cin >> n >> x))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
inline void solve() {
vector<int> sf(n + 1, 0);
sf[n] = sf[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
if (a[i] <= a[i + 1])
sf[i] = sf[i + 1];
}
int ans = 0;
int uk = 0;
while (true) {
int np = uk;
while (np < n && a[np] <= x)
np++;
fore (i, uk, np) {
if (i == 0) continue;
if (a[i - 1] > a[i]) {
cout << -1 << endl;
return;
}
}
if (sf[np])
break;
assert(a[np] > x);
swap(a[np], x);
ans++;
uk = np;
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while(t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение 1 (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<li, li> pt;
const li INF64 = li(1e18);
pt p[4];
inline bool read() {
fore (i, 0, 4) {
if(!(cin >> p[i].x >> p[i].y))
return false;
}
return true;
}
inline void solve() {
li ans = INF64;
fore (st, 0, 2) {
fore (idx1, 0, 4) fore (idx2, 0, 4) fore (idy1, 0, 4) {
li x1 = p[idx1].x;
li x2 = p[idx2].x;
li y1 = p[idy1].y;
if (x1 > x2)
continue;
for (int k = -1; k <= 1; k += 2) {
li y2 = y1 + k * abs(x1 - x2);
vector<pt> fp = { {x1, y1}, {x2, y1}, {x2, y2}, {x1, y2} };
sort(fp.begin(), fp.end());
do {
li cur = 0;
fore (i, 0, 4)
cur += abs(fp[i].x - p[i].x) + abs(fp[i].y - p[i].y);
ans = min(ans, cur);
} while(next_permutation(fp.begin(), fp.end()));
}
}
fore (i, 0, 4)
swap(p[i].x, p[i].y);
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t;
cin >> t;
while(t--) {
assert(read());
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Решение 2 (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<li, li> pt;
const li INF64 = li(1e18);
pt p[4];
inline bool read() {
fore (i, 0, 4) {
if(!(cin >> p[i].x >> p[i].y))
return false;
}
return true;
}
li len(const pt &a) {
assert(a.y >= a.x);
return a.y - a.x;
}
pt getSeg(li a, li b) {
return { min(a, b), max(a, b) };
}
pt getOpt(const pt &a, const pt &b) {
return {
max({ a.x - b.y, b.x - a.y, 0LL }),
max({ b.y - a.x, a.y - b.x, 0LL })
};
}
inline void solve() {
li ans = INF64;
vector<int> id = { 0, 1, 2, 3 };
do {
li cur = 0;
auto x1 = getSeg(p[id[0]].x, p[id[3]].x);
auto x2 = getSeg(p[id[1]].x, p[id[2]].x);
cur += len(x1) + len(x2);
pt xSeg = getOpt(x1, x2);
auto y1 = getSeg(p[id[0]].y, p[id[1]].y);
auto y2 = getSeg(p[id[2]].y, p[id[3]].y);
cur += len(y1) + len(y2);
pt ySeg = getOpt(y1, y2);
li is = min(xSeg.y, ySeg.y) - max(xSeg.x, ySeg.x);
cur += 2 * max(0LL, -is);
ans = min(ans, cur);
}
while (next_permutation(id.begin(), id.end()));
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t;
cin >> t;
while(t--) {
assert(read());
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, k;
string s;
string dp[N];
void solve() {
cin >> n >> k >> s;
for (int i = 1; i <= n; i++)
dp[i] = char('z' + 1);
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
int nc = min({c, (c + 1) % k, (c + k - 1) % k});
dp[i + 1] = min(dp[i + 1], dp[i] + char('a' + nc));
if (i > 0) {
dp[i + 1] = min(dp[i + 1], dp[i - 1] + char('a' + nc) + s[i - 1]);
dp[i + 1] = min(dp[i + 1], dp[i].substr(0, i - 1) + s[i] + dp[i].back());
}
if (i > 1) {
dp[i + 1] = min(dp[i + 1], dp[i - 1].substr(0, i - 2) + s[i] + dp[i - 1].back() + s[i - 1]);
}
}
cout << dp[n] << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Идея: MrPaul_TUser и BledDest
Разбор
Tutorial is loading...
Решение (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
const long long INF = 1e18;
struct op{
string tp;
int y, v, to;
};
struct addmap{
long long add;
map<int, long long> val;
multiset<long long> mn;
};
void reset(addmap &a, int x, long long val){
if (a.val.count(x))
a.mn.erase(a.mn.find(a.val[x]));
a.val[x] = val - a.add;
a.mn.insert(val - a.add);
}
int main() {
int n, s;
scanf("%d%d", &n, &s);
static char buf[10];
op a;
vector<addmap> st;
st.push_back({});
st.back().val[0] = 0;
st.back().add = 0;
st.back().mn.insert(0);
forn(i, n){
scanf("%s", buf);
a.tp = buf;
if (a.tp == "set"){
scanf("%d%d", &a.y, &a.v);
assert(!st.back().mn.empty());
long long mn = st.back().add + *st.back().mn.begin();
st.back().add += a.v;
if (a.y != s) reset(st.back(), a.y, mn);
}
else if (a.tp == "if"){
scanf("%d", &a.y);
long long val = INF;
if (st.back().val.count(a.y)){
val = st.back().val[a.y] + st.back().add;
st.back().mn.erase(st.back().mn.find(st.back().val[a.y]));
st.back().val.erase(a.y);
}
st.push_back({});
reset(st.back(), a.y, val);
st.back().add = 0;
}
else{
if (st[int(st.size()) - 1].val.size() > st[int(st.size()) - 2].val.size())
swap(st[int(st.size()) - 1], st[int(st.size()) - 2]);
addmap& v = st[int(st.size()) - 2];
for (auto it : st.back().val){
if (!v.val.count(it.x) || v.val[it.x] + v.add > it.y + st.back().add){
if (v.val.count(it.x))
v.mn.erase(v.mn.find(v.val[it.x]));
v.val[it.x] = it.y + st.back().add - v.add;
v.mn.insert(it.y + st.back().add - v.add);
}
}
st.pop_back();
}
}
printf("%lld\n", *st.back().mn.begin() + st.back().add);
return 0;
}
When was the last time problem ratings were updated ?
Can someone explain those function proof in a simple way in C ques.
It looks too complicated. My thinking was slightly different. Since A has to start and make the first turn, she doesn't have options. B decides in this case if he wants to hit or miss. And since B wants to maximize his score, the maximum what he could get is if he misses everything from A and then with A having 0, he would able to get y points (it's impossible to get more) and A will have x points. But also as they want to minimize their enemy's scope as a second parameter, there is no need for B to miss everything, he could hit the last ball from A (A will have 0 energy already) so she will waste this point and B will get it. And in this case A will have (x — 1) and B will have y points. There is no better option for B because if he hits any ball except the last one A should respond not to loose her point. In this case B won't have maximum possible score.
I have an interesting solution (100067011) to problem E, involving minimum cost circulation. It might not be the best solution, but it involves no casework or geometric insight, and it might be educational in helping you approach other problems.
First, I iterate over all permutations of the points, so let's assume $$$p_1$$$ will end up as the bottom left point of the square, $$$p_2$$$ the bottom right, $$$p_3$$$ the top left, $$$p_4$$$ the top right.
For each point, let's create two variables $$$dx_i$$$ and $$$dy_i$$$, so that point $$$i$$$ should end up at position $$$(x_i+dx_i, y_i+dy_i)$$$. Then the objective is to minimize $$$\sum_i |dx_i|+|dy_i|$$$.
Now, we need to set up the constraints so that the points will make a square. To make sure it's a rectangle, we need
To make sure it's a square, we need the side lengths to be equal. That is,
At this point, I noticed that each variable appears in at most 2 constraints, which reminds me of the constraints of a flow problem. I also notice that we can add a new (redundant) constraint to make each variable appear in exactly two constraints:
The equations can be interpreted as
$where our variables $$$dx_i$$$ and $$$dy_i$$$ are undirected edges. And the cost of this flow is exactly what we seek to minimize.
I really want to understand this solution to the full extent. I understood up to (F) but am not sure 1) why two constraints should remind someone of a flow problem, 2) how to go from the equations to the flow graph, and 3) (the hardest/crucial part) why this graph solves the problem correctly. I am not the strongest in flow problems so understanding this unique solution in detail may prove very beneficial to me and hopefully others!
The constraints of a flow problem are that for each node, the incoming flow equals the outgoing flow. So each edge $$$(u, v)$$$ is involved in $$$u$$$'s constraint as the outgoing flow, and in $$$v$$$'s constraint as the incoming flow. So if each variable appears in at most two constraints, it's a strong indicator of a flow problem.
The nodes represent the constraints, so $$$A,\ldots, F$$$ are the nodes. To force it into the $$$\mathrm{flow\_in}_u=\mathrm{flow\_out}_u+\mathrm{demand}_u$$$ framing, we need the following:
So I will rewrite the equations like this.
From here, the graph and demand values follow. An edge connects the two letters that involve it in the constraints. Now, $$$dx_i$$$ and $$$dy_i$$$ can be positive or negative, so they are actually undirected edges in the flow graph, but we still needed to set the equations up as incoming/outgoing flows. This ensures the sign of the demands are correct, and that the constraints really do correspond exactly to a flow graph.
Thanks for such a detailed explanation! After doing some research does this problem relate to linear programming at all? Because the way I understand flow problems (max flow min cut) is that you have a source and sink node with predetermined constant capacities on each edge. Maybe I am misunderstanding the graph that you created but I do not see any source/sink or how one could use flows to support unknown capacity on each edge? Or how a node represents an equation?
If you/anyone has resources for problems very similar to this with solutions (I could not find any but maybe I am searching the wrong thing) that would also be helpful. Thanks!
It relates to linear programming in that I approached the problem by setting it up as LP, then noticed it's a special case and can be solved with flow.
You're right that I didn't mention a source or sink. That's because it's a circulation graph. You should read about circulation and how it reduces easily to min cost max flow, with an added source and sink.
I can understand your solution. However, I use Dinic instead of MCMF and still get correct answer(see my 167564314), which means that I even not take care of cost! I don't know why it is correct, it is amazing!
Dinic's algorithm works by always selecting the augmenting path with the fewest edges. It turns out that a path of min number of edges happens to be equivalent to min sum of weights for this particular example, so Dinic's will work here.
(You can see that all edges are weight $$$1$$$ except the edges from source and to sink, but we have to take exactly $$$2$$$ of those anyway. That's why min edges = min cost here.)
I thought that $$$O(tn^2)$$$ would not pass for problem F so I have a $$$O(tnk)$$$ solution. It is basically the editorial solution except we only keep the last 3 characters of our string, ensuring that all characters before that is of the optimal solution.
code (very ugly): 100144988
I think this can possibly be improved to $$$O(tn)$$$.
Edit: 100146367. Yea there is a $$$O(tn)$$$ solution.
On Problem E
WHY??????
The way I came to that conclusion is the following. First, we have to fix something. Let's start by proving there is some $$$x$$$ in the input such that it's one of the optimal lines. For the simplicity, let's fix the permutation of points beforehand and prove for it.
Let the square side be some length $$$a$$$. So we have found some optimal square such that neither of the original $$$x$$$ are in there. If it is entirely to the left or to the right of all points then you surely can move it closer and the cost decreases. Otherwise, what's the cost of moving the square one to the left or one to the right? It's basically some linear function on (number of points to the left of each $$$x$$$) and (number of points to the right of each $$$x$$$). Also, that cost is constant until we reach any of the original points while we move it. Moreover, moving to the left costs exactly the same as moving to the right but negated. So if the cost is non-zero, then we can at least move the square to the side where the function is negative and obtain a smaller cost. If it's zero then you can still move to any side and the cost won't change. So move until you hit some $$$x$$$. Thus, there always exists a square of side length $$$a$$$ such that it costs less than or equal than our assumed answer.
Same proof goes for some $$$y$$$. You can notice that this proof relies only on one coordinate, so you can move any square of any side length independently on each coordinate. Thus, we've proven that there is some $$$x$$$ and some $$$y$$$ in the original input that is optimal for any side $$$a$$$.
Now, let's fix some $$$x$$$, some $$$y$$$ and some permutation of points. Let $$$(x, y)$$$ be the lower left corner of the square. Cut the grid by all $$$x$$$-s of the input and all $$$y$$$-s of the input. Let the upper right corner of the square be between some $$$x_1$$$ and $$$x_2$$$ and between some $$$y_1$$$ and $$$y_2$$$. Notice that the cost to move the upper right corner by one by both $$$x$$$ and $$$y$$$ simultaneously is constant inside the entire rectangle between $$$x_1$$$ and $$$x_2$$$ and between $$$y_1$$$ and $$$y_2$$$ (basically, the same as in the first proof). Shrinking the square costs a negated price of expanding it. Thus, we can keep shrinking or expanding (choose the one that's non-positive) until we hit a border of the rectangle $$$x_1$$$/$$$x_2$$$, $$$y_1$$$/$$$y_2$$$. So we hit it and the cost has been decreasing (or staying the same) all the way to some $$$x$$$ or $$$y$$$ on the border of the rectangle. Thus, we came up to the conclusion that there's also some $$$x$$$ or $$$y$$$ besides the original $$$x$$$ and $$$y$$$ we fixed that is optimal. Apply the same proof to $$$(x, y)$$$ being any corner of the square and you got yourself a full proof.
hujc, Whistleroosh, here you go.
I understand this explanation!!
Thank you very mach!!!
Thank you for explanation
wow, that's a really nice proof.
I really like how this proof is similar to the proof of the fact that the cost of moving all points (in one dimension) to a common point is minimum when the common point is the median of all the points. But this is of course in two dimensions. Cool!
thank you so much, nice explanation!!
My solution for Problem D is simpler, check it out: 100115447
can you explain it a bit here? I am not able to understand the editorial completely.
My solution for problem D is next: First because you only have n numbers and 1 x variable if you add them all to one array and sort it you will have n+1-element sorted array. And you know that if a solution exists for the problem when you do it you will get a n-element sorted array(if you have 1 2 3 5 4 and x = 0 you know that when you do the least possible switches you will get one of the following: 0 1 2 3 4, 0 1 2 3 5, 0 1 2 4 5, 0 1 3 4 5, 0 2 3 4 5, 1 2 3 4 5, and you can see that our n+1-element sorted array is 0 1 2 3 4 5 so those possible answers are nothing more than this array without one of its elements).So we can try to match the starting array 1 2 3 5 4 to any of those arrays created from our n+1-element array and save the minimum switches you needed to make for each try.So how to calculate the number of switches for each try? just look at each one of the elements from left to right and if they dont match then you need to switch your current x with that element(if you dont you wont be able to do it later because all the other numbers are bigger or equal to that one) so if x < current number that needs to be switched with x we switch them and we do that until we end with iteration(that means we equalised the arrays so we found number of switches for that array) or until we need to switch the number that is greater than x(that means, in this iteration, we cant sort it in which case the answer is -1).Here is a solution if you dont get what im saying 100264317
100264317
Your solution is great, it's also memory-wise efficient than mine.
Thanks man, really appriciate it.
Isn't your solution O(n^2)?
The proof of C is really interesting but I just can't accept the fact that the solution is one line.
I thought of it this way. Since Bob can atmost hit y shots, the maximum score he can have is y. Then I formulated the strategy for how Bob can always achieve that maximum score. I too was really surprised on finding a O(1) solution.
Nice way to look at it. I saw that Bob can always score y but at first I thought that Alice can also always get x until I saw the samples.
Oh, and I it was crucial that they don't want to win but to maximize their score and after that minimize the opponent's score.
I have a question...!
in problem E. Four Points,
it is noted that a square with side 0 is allowed
so for the 2nd test case in the example, why not making four points as (2,0), (2,0), (4,0), (4,0), which makes the output 3 ?
This is a line segment with length 2, not a square.
I thought a square with side 0 means the side with the length 0, so then what's the difference between a square with side 0 and a line ?
The length of the line from a square must be the same. So we can assume that a square with side 0 has four line whose length is 0, which actually is just a single point.
However, we can assume that a segment with length 2 not only has side 2, but also has side 0.So it isn't a square.
According to Wiki (and all dictionaries I saw), a square "has four equal sides". If a square has a side equal to 0 then all his sides are equal to 0, i. e. it's a point — not a segment.
In fact, (2,0),(2,0),(4,0),(4,0) cannot form a square with side 0.
Four points which can form a square with side 0 must be the same with each other completely.
For example, (2,0),(2,0),(2,0),(2,0) can form a square with side 0.
Hopefully, my answer will help you.(Sorry for my poor English.)
can someone elaborate the DP solution for problem D??
Because of the observations mentioned in the editorial, we can go in increasing order of indices, and keep taking decisions on whether to make the switch or not.
Let $$$dp(i, prev, cx)$$$ represent answer for $$$a[1...i]$$$ sorted prefix where number put on the $$$i^{th}$$$ index was $$$prev$$$ and now we are deciding what to do on the next index with value of $$$x$$$ equals $$$cx$$$.
Now we can either let the value of $$$a[i+1]$$$ stay the same (possible only when $$$prev <= a[i+1]$$$ ): $$$dp(i+1, a[i+1], cx) := min(self, dp(i, prev, cx))$$$
Or we can actually swap $$$a[i+1]$$$ with $$$cx$$$ (when $$$prev <= cx$$$ and $$$cx < a[i+1]$$$ ) with the following transition: $$$dp(i+1, cx, a[i+1]) := min(self, dp(i, prev, self) + 1)$$$
To optimise space complexity, dont store dp table for all the indices. Store them only for the current and the immediate-next index.
My Code: 100219452
100731689 Here is a simpler version of code. Thanks iprakhar22, for idea.
can you please explain your approach, i didnt get it..
In E what is the proof for the statement that:
- either both x1 and x2 coincide with some (pi.x)-s and y1 coincide with one of (pi.y)
- or both y1 and y2 coincide with some (pi.y)-s and x1 coincide with one (pi.x)?
How to solve D with $$$O(n^2)$$$ DP?
Can anyone tell me why am i wrong ? :'< https://mirror.codeforces.com/contest/1455/submission/100029658
Yeah i had same problem, consider the following portion of test 4 for which you have done computation for previous input and while iterating through 42 42 43 46 44 45 46 48 48 48 62 51 51 you will have x=46 while iterating you are counting 48 three times while you require only one swap so that accounts for 2 extra moves in your answer.You can refer to my code on same logic in O(n) https://mirror.codeforces.com/contest/1455/submission/100248902
Omg thank you so much, i get it! >.<, I hope u can reach high rate in next contest, people like you deserve it ^^
For 1455E - Four Points I want to describe other solutions. In my opinion they are easier to understand.
First one, which I came up during round but didn't polish enough is following.
Trying to find out where square should be is mess if you know nothing. So, lets assume we know which point goes where. I'll use word "go" and think about points as walking. Now it's easy to calculate total distance traveled by each point. Let's say $$$x,y$$$ are coordinates of one corner and $$$w$$$ is width of square, so all coordinates of points is simply $$$(x,y),(x,y-w),(x-w,y),(x-w,y-w)$$$. Then, separate coordinates, and total distance by x coordinate is: $$$|x_1-x|+|x_2-x|+|x_3-(x-w)|+|x_4-(x-w)|$$$. Similarly, total distance by y coordinate is: $$$|y_1-x|+|y_2-(y-w)|+|y_3-y|+|y_4-(y-w)|$$$. With this two formulas we can start analyze.
First, we see that both formulas are sums of abs functions. Second: we see three unknowns. Third: for fixed $$$w$$$ you can minimize both separately. Suppose you know $$$w$$$, then how to find out best $$$x$$$ and best $$$y$$$? Hypothesis: best x is among $$$x_1,x_2,x_3,x_4$$$, similarly for $$$y$$$. Looks promising. What about $$$w$$$? Well... I need to argue why hypothesis about best $$$x$$$ and $$$y$$$ is like this. This is because $$$|x_1-x|$$$ reach minimum when $$$x = x_1$$$, because $$$|x_1-x_1|=0$$$. Similarly $$$|x_2-x|$$$ reach minimum when $$$x=x_2$$$, so intuitive candidates for minimum sum is when some of operands is minimum. Applying same argument regarding $$$x$$$ we wee that $$$|x_3-(x-w)|$$$ should turn into zero, and it's when $$$x_3-x+w=0$$$ or $$$w = x-x_3$$$. But by our previous hypothesis $$$x$$$ should be among $$$x_1,x_2,x_3,x_4$$$, so this makes us think that $$$w$$$ should be some difference between coordinates.
Trying to submit solution like following: try all permutations of which point goes where, then for each permutation try to make points $$$(x,y),(x,y-w),(x-w,y),(x-w,y-w)$$$ using all four $$$x$$$, and all four $$$y$$$, and try $$$w$$$ to be every difference between x coordinates or y coordinates. WA2. Why? Well... Just because of little ignorance. We should notice that $$$|x_3-(x-w)|$$$ becomes zero when $$$x = (x_3+w)$$$, so among candidates for best $$$x$$$ we should also try $$$x_1+w, x_2+w, x_3+w, x_4+w$$$. Similarly for $$$y$$$. AC! 100123201
Proof! Again we fix which point goes where. And again we analyze formulas: $$$|x_1-x|+|x_2-x|+|x_3-(x-w)|+|x_4-(x-w)|$$$ and $$$|y_1-x|+|y_2-(y-w)|+|y_3-y|+|y_4-(y-w)|$$$. Second formula is similar, so focus on first one. Imagine plot of function $$$|x|$$$, it's just two infinite line segments meeting at point zero. How about $$$|x+C|$$$ where C is some constant: it is again two line segments meeting this time at coordinate $$$(-C)$$$. What if we add two functions like that? We get at most three segments. But main point here is: we still get line segments! Thus, any sum of functions like that is set of line segments with points located at corresponding $$$(-constants)$$$. Where minimum of function like this can be achieved? only at one of points. Our function for fixed $$$w$$$ has this kind of plot. So minimum of it for fixed $$$w$$$ is determined by constants. Similarly, our function for fixed $$$x$$$ has this kind of plot, and best $$$w$$$ determined by constants.
Now, most tricky part. We can't say that "we have just sum of functions, so we need pick best candidates for each variable", or may be you can but I don't know why. So, instead we prove by contradiction. Suppose best solution is $$$(x,y,w)$$$, then look at formula of travel distance by coordinate $$$x$$$. For fixed $$$w$$$ we know candidates for which it may take minimum. If one of points is better, then take it and we have better answer and we have contradiction. Otherwise we can change $$$x$$$ to one of candidates and total cost will be same. Similarly for $$$y$$$. Now we have $$$x,y$$$ from our candidates. All we have to show now is that $$$w$$$ is also from our set. Candidates for $$$x$$$ is $$$x_1, x_2, x_3+w, x_4+w$$$, for $$$y$$$ is $$$y_1, y_2+w, y_3, y_4+w$$$. I won't describe each case, they are similar. Suppose that candidates we get is $$$x_1,y_2+w$$$. For $$$x$$$ coordinate candidates for $$$w$$$ are $$$x_1-x_3$$$ and $$$x_1-x_4$$$. For $$$y$$$ coordinate candidates for $$$w$$$ are $$$y_1-y_2,y_3-y_2$$$. Most difficult right now to realize, that sum of both formulas for coordinates for fixed kind of (x,y): in this case it is $$$(x_1,y_2+w)$$$ resulting formula still line segments with points with $$$w$$$ at positions $$$x_1-x_3,x_1-x_4,y_1-y_2,y_3-y_2$$$ and for any $$$(x,y)$$$ of form $$$(x_1,y_2+w)$$$, best $$$w$$$ is among $$$x_1-x_3,x_1-x_4,y_1-y_2,y_3-y_2$$$, or at least not worse. Similarly any other case.
And, as you can see from proof, for each permutation you can pick crafted shorter list of candidates: only those values which can take best for this permutation. It is not dramatically better. For each $$$x$$$ candidate there is two $$$w$$$ candidate, same for $$$y$$$, then candidates unite, so for each $$$(x,y)$$$ candidate there are four $$$w$$$ candidate. 4*4*4 variants for each permutation. 100217389
Now, second solution. Take a look at formula for one coordinate. If we open brackets we will get $$$|x_1-x|+|x_2-x|+|x_3-x+w|+|x_4-x+w|$$$. You can rephrase this formula as: what if there four people standing at coordinates $$$x_1,x_2,x_3+w,x_4+w$$$. It's classic problem, and solution is to take median. Why? imagine they meet at some point $$$x$$$, then if we move meeting point x to the right, each one from the right should move 1 less, and each from the left should move 1 more, so you can do better if from the right is more people than from the left. Also you can do better by moving meeting point to the left if from the left there are more people than from the right. So, the best is when number of people from the left is equal to number of people from the right. It's achieved if you're at median. Or, if there are even number of people: at any of "two medians".
Now, suppose we have people at $$$x_1,x_2,x_3+w,x_4+w$$$ and $$$w$$$ is initially equal to zero. Then, repeatedly pick median and increase $$$w$$$ each time. Median can only change when one point goes over other point. It happens when $$$x_3+w = x_1$$$ or at $$$x_3+w=x_2$$$ and so on. First equation is when $$$w = x_1-x_3$$$ — again, difference between two of $$$x$$$. Thus, medians can change only at those $$$w$$$. Hypothesis: only those $$$w$$$ are candidates for best $$$w$$$. How to prove without proof above? I don't know. At least I show how we can get this intuition. Anyway, for each permutation we can try each $$$w$$$ and use median to find $$$x,y$$$. 100106479
Hello everyone, I meet a very very strange problem when i am trying to solve 'Problem G'. At first, I commited this code 100780041, and the result was 'Wrong answer on test 11'. The reason to lead the WA is I used the erase(x) method of multiset to delete one item, but obviously I deleted all the items valued x. So I replaced this wrong applying with multiset.erase(multiset.find(x)) which only will delete one item valued x. But I got the TLE!!! on test 5!!! 100780082 In theory, these two ways have the same time complexity. So I am so confused that having to ask someone else to help me have a look. Thanks. The differents of two code:
And because the contest is finished for a little long time, I probably knows maybe little people focus on this. So, may I please ask you for help? awoo
OK，I got it! In line 113
costset[rt[End[i]]].remove(y[i]);, I will erase a item valued x that can not exist. So when I use multiset.erase(multiset.find(x)), the inner return of find method will return multiset.end() that can cause the TLE when I erase it.Problem B can be solved in $$$O(t)$$$ time. (100963724)
(Editorial solution is $$$O(\sqrt{x}\cdot t)$$$ I believe)
For each test case, we can calculate the lower bound of $$$n$$$ as
You arrive to this by solving for $$$n$$$ in Baby Gauss' formula.
The code is a little different, in that I multiply and divide the square root by 4 in order to deal with integers and not worry about floating point errors. And of course we take the floor to get the lower bound.
This implies that our input $x$ is between $$$x_1$$$ and $$$x_2$$$.
Finally, by the same logic as explained in the editorial.
If our $$$x$$$ is the lower bound, we output the $$$n$$$ of the lower bound.
In all the other cases, we can account for the difference between the lower bound and our input by taking one more number and changing another one for $$$-1$$$.
The only exception being when the difference is $$$1$$$, in which case we have to take 2 more numbers, subtract one of them and add the other.
I hope it's clear enough. It's my first time commenting. The only difference is that we remove the inner
whileloop.Hello everybody, this is my first question here so wish me luck xD
I submitted code for D problem here https://mirror.codeforces.com/contest/1455/submission/100985682 and the result was "Wrong answer on test 3". When i test with the same test case i get 3 as output, but when i submit it gives the 74 as output! Can anyone explain me how did it come about throwing out 74 or any other number greater than 3 instead of 3?
I also wrote the same wrong code as yours.
In fact, in this method you need to check everytime if the suffix array is already sorted. It is only when the array is still not sorted that you need to do the swapping. (checking everytime can be done in O(1) or O(n), both will pass)
I can't understand asymptotics of my D solution. It has passed and it is none of authors solutions. https://mirror.codeforces.com/contest/1455/submission/102979769
If someone can hack it or prove some good asymptotics, you're welcome.
When I saw this blog in Recent Actions, I initially thought "Who the hell is this awoo guy and why does he copy-paste our editorial blogs?"
for the problem D,
if all elements before it are smaller and elements after it are greater then the element is in sorted position.
if an array is unsorted then x has to be there in the array. this observation will be used.
cnt =0.
for i from 1 to n,
check every element a[i] for the following criteria:
1) if array is now sorted then return cnt.
2) if a[i] and x are candidate for position i then we have conditions:
(swap is done because subarray after i is not sorted and if greater element is assigned this position( which is arr[i] ) then x will be there in the subarray after i(the fact stated above) which will make array unsorted as a whole.)
3) if a[i] is candidate for the position but x is not the candidate for the position: then just move to the next element.
4) if a[i] is not the candidate for the position but x is the candidate for the position: we have only one choice to swap them and add 1 to cnt and move to next element. if any other situation is encountered then say it is impossible.
print cnt
(BEING A CANDIDATE FOR A POSITION means all elements before it are smaller and all elements after it are greater.)