Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
print(eval(input()))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int _ = 0; _ < t; _++)
{
vector<int> a(4);
for(int i = 0; i < 4; i++)
cin >> a[i];
int maxpos = max_element(a.begin(), a.end()) - a.begin();
int minpos = min_element(a.begin(), a.end()) - a.begin();
if(maxpos + minpos == 3)
puts("YES");
else
puts("NO");
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
def construct(f, k):
return [(i + 2 if i < f - 1 else 1) for i in range(k)]
t = int(input())
for i in range(t):
k, n = map(int, input().split())
ans = 1
for f in range(1, k):
d = construct(f, k - 1)
if sum(d) <= n - 1:
ans = f
res = [1]
d = construct(ans, k - 1)
for x in d:
res.append(res[-1] + x)
print(*res)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
vector<int> a(n);
for(int j = 0; j < n; j++)
cin >> a[j];
int mn = 0, mx = int(1e9);
for(int j = 0; j + 1 < n; j++)
{
int x = a[j];
int y = a[j + 1];
int midL = (x + y) / 2;
int midR = (x + y + 1) / 2;
if(x < y)
mx = min(mx, midL);
if(x > y)
mn = max(mn, midR);
}
if(mn <= mx) cout << mn << endl;
else cout << -1 << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
for tc in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
a, b, c = 0, 0, 0
for i in range(n):
if p[i] != i + 1 and p[i] != n - i:
c += 1
elif p[i] != i + 1:
a += 1
elif p[i] != n - i:
b += 1
if a + c <= b:
print("First")
elif b + c < a:
print("Second")
else:
print("Tie")
1772F - Copy of a Copy of a Copy
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
struct op{
int t, x, y, i;
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int main(){
int n, m, k;
cin >> n >> m >> k;
vector<vector<string>> a(k + 1, vector<string>(n));
forn(z, k + 1) forn(i, n)
cin >> a[z][i];
vector<int> cnt(k + 1);
forn(z, k + 1){
for (int i = 1; i < n - 1; ++i){
for (int j = 1; j < m - 1; ++j){
bool ok = true;
forn(t, 4)
ok &= a[z][i][j] != a[z][i + dx[t]][j + dy[t]];
cnt[z] += ok;
}
}
}
vector<int> ord(k + 1);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&cnt](int x, int y){
return cnt[x] > cnt[y];
});
vector<op> ops;
forn(z, k){
forn(i, n) forn(j, m) if (a[ord[z]][i][j] != a[ord[z + 1]][i][j]){
a[ord[z]][i][j] ^= '0' ^ '1';
ops.push_back({1, i + 1, j + 1, -1});
}
ops.push_back({2, -1, -1, ord[z + 1] + 1});
}
cout << ord[0] + 1 << '\n';
cout << ops.size() << '\n';
for (auto it : ops){
cout << it.t << " ";
if (it.t == 1)
cout << it.x << " " << it.y << '\n';
else
cout << it.i << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (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())
typedef long long li;
int n;
li x, y;
vector<li> a;
inline bool read() {
if(!(cin >> n >> x >> y))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
li ceil(li a, li b) {
assert(a >= 0 && b >= 0);
return (a + b - 1) / b;
}
inline void solve() {
sort(a.begin(), a.end());
vector<li> t(n), b(n);
fore (i, 0, n) {
if (i > 0 && b[i - 1] >= a[i]) {
t[i] = t[i - 1];
b[i] = b[i - 1] + 1;
} else {
t[i] = a[i] - i;
b[i] = a[i] + 1;
}
}
li ans = 0;
while (x < y) {
int pos = int(upper_bound(t.begin(), t.end(), x) - t.begin());
li p = pos, m = n - pos;
if (x + p >= y) {
cout << ans + (y - x) << endl;
return;
}
if (p <= m) {
cout << -1 << endl;
return;
}
//1. x + k(p - m) + p >= y
li k = ceil(y - x - p, p - m);
if (pos < n) {
//2. x + k(p - m) >= t[pos]
k = min(k, ceil(t[pos] - x, p - m));
}
ans += k * n;
//x + k(p - m) < y, since 1. and p >= p - m
x += k * (p - m);
}
assert(false);
}
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;
}
Can anyone help me with question D Absolute Sorting 185861518 where did i gone wrong?
try these may be you will find your bug.
Expected output: 0
By the way, a more "natural" way to deduce the relations for D (without doing a lot of casework) is to square both sides of the inequality, because if $$$|x| \leqslant |y| \Rightarrow x^2 \leqslant y^2$$$. This gives $$$(a_i - x)^2 \leqslant (a_{i + 1} - x)^2$$$ for all valid $$$i$$$. This implies that $$$a_i^2 - 2a_ix + x^2 \leqslant a_{i + 1}^2 - 2a_{i + 1}x + x^2 \Rightarrow (a_i^2 - a_{i + 1}^2) - 2(a_i - a_{i + 1})x \leqslant 0 \Rightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \leqslant 0$$$, and then we can continue in the same way as editorial.
Thank you, this is also good
It's more natural to just binary search the answer 185850639 (I suppose)
interesting, could you explain your approach a bit in detail?
First, let's denote min(a) as L, max(a) as H and M as (L + H) / 2, it's pointless to look for a solution where x > H or x < L because they will give array of the same (sortness) as H and L. try x = 5, 6 and x = 3, 2 on a = [5, 3, 5] for example, it'll give [0, 2, 0], [1, 3, 1] and [2, 0, 2], [3, 1, 3], respectively. every binary search loop iteration you loop through the array and check for any abs(M — a[i]) < abs(M — a[i — 1]) (which makes the result unsorted obviously), in case we found it we need to prolong the distance between M, a[i] and shorten it between M, a[i — 1] so we updaet H = M — 1 in case a[i] > a[i — 1] or L = M + 1 in case a[i] < a[i — 1]
how do we know when to do h=m-1 or l=m+1
absolute value means distance so if abs(m-a[i]) < abs(m-a[i-1]) that means m was closer to a[i] than a[i — 1] when it should have been further or equal, so we we make it closer to a[i-1]. if a[i] > a[i — 1] we need to make m smaller by doing h=m-1 and vice versa
Aight . Got it , Thanks. I actually tried doing it by taking l=0 and h=1e9 and it worked , idk why or how but it got accepted.
Damnn , thanks for thisss!
Thanks a lot,I got it!
If you want to do it more natural, you can apply difference of squares identity: $$$a^2 - b^2 = (a - b)(a + b)$$$ i.e. $$$(a_i−x)^2\le(a_{i+1}−x)^2 \Leftrightarrow (a_i−x)^2 - (a_{i+1}−x)^2 \le 0 \Leftrightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \le 0$$$
could not understand if(mn <= mx) cout << mn << endl; this part why we are taking mn<=mx
So to check if the obtained range is a "possible" range example, if two numbers are 3 and 6, then >=3 and <=6 is a possible range, but >=6 and <=3 is not a possible range. We are checking if 3 < 6
I still don't understand the strategy used in Permutation Game. For me at least, the only possible outcome was a tie, because the other player can mess with the correct ordered ones. For example: 1 2 3 5 4 The first one colors 5 1 2 3 B5 4 The second colors any other to not let the first payer win B1 2 3 B5 4 The first color the last element B1 2 3 B5 B4 The second starts to mess the order of elements B5 2 3 B1 B4 And we have at least two elements out of order for player one, and it will require at least two first movements, but for any of them the other player will undo that movement. So what's the strategy?
You can swap more than two blue elements in one turn. You can reorder them as you want, the only condition is that all red elements stay on their positions.
I thought the swap was meant for only two elements, thanks.
Why cant 2nd player win in [2,3,1] . Why the answer is Tie.
first player [2B,3,1]
2nd player[2B,3B,1]
1st player skips
2nd player exchanges [3B,2B,1]
If the starting configuration is [2,3,1], 1st player wouldn't start by making the 2 blue. The game would go like this:
1st player [2,3,1B]
2nd player [2B,3,1B]
1st player skips
2nd player skips
1st player skips
2nd player skips . . .
Neither player can arramge the numbers in their goal orders, and making the 3 blue would allow the opponent to win, so bot players just skip turns and it's a tie.
For Problem G, why can we assume that we require a whole cycle in the reasoning for $$$x+k(p-m) \geq t_p$$$? What if $$$x$$$ exceeds $$$t_p$$$ mid-cycle? Then the number of wins in this particular cycle iteration would be $$$p+1$$$ and not $$$p$$$.
The $$$t_p$$$ is the rating you need at the start of the cycle to be able to win the $$$p$$$-th opponent (i.e. first $$$p+1$$$ opponents). If your $$$x < t_p$$$ at the start of the cycle — you can't win against the $$$p$$$-opponent.
Nope, suppose array $$$a = [5, 5, 5, 6]$$$. Arrays $$$t = [5, 4, 3, 3]$$$ and $$$b = [6, 6, 6, 7]$$$ don't make any sense.
please also post c++ codes
i'm new here,anyone could help me in C?,i don't understand what its mean.
Uh,the meaning of the C question is that two integers marked k and n are given,and you are requested to choose k integers from these integers ranging from 1 to n,then,sort these k integers in ascending order,Thus,an asending array has come into being. Postulate the array is{a1,a2,a3....ak},(a1<a2<a3<...<ak),we can get k-1 integer such that a2-a1,a3-a2,....ak-a(k-1),((k-1) is just a subscript :)),make up a set(mark the set with A) with the k-1 integers.(You should notice that the k-1 integers don't distincted to each other,so the number of the elements in the set(mark the number with g) doesn't necessarily be k-1.)You have different methods to choose k intergers,which corrospond the diffrent values of g.You should print the choice method that could let the g be maxminum. (I suggest you read the text carefully again and learn to guess what the meaning of the question is ,After all,my English is poor....It's my pleasure if my reply can offer you some help:)
thanks ! i got a aot from your reply :D
My solution for D using Binary Search:
I got the idea from this line in the problem:
It can be shown that if such an integer x exists, there is at least one such integer between 0 and 10^9.
Initially, left = 0, right = 10^9 and x will be our mid, for any x the array should satisfy |a[i]-x| > |a[i-1]-x| for all i (0 <= i < n), if it doesn't, note that |a[i]-x| > |a[i-1]-x| means that x should be closer to a[i-1] than to a[i], so for any x that does not satisfy |a[i]-x| > |a[i-1]-x| we have 2 cases:
a[i-1] > a[i] then to move x closer to a[i-1] we should increase x i.e. left = x+1
a[i-1] < a[i] then we should decrease x i.e. right = x-1
My Submission, complexity: O(nlog(10^9)) per testcase
Nice observations. If we took x closer to a[i-1] in the case of a[i-1] < a[i] then it goes away from a[i] and maximizes the value of |a[i]-x|.
Can you say how to observe these types of questions During the contest, I was trying to observe some kind of pattern and failed . Thanks :)
Here are some testcases for G
variety-jonas
can you add test case suite to problem G ?
The checker got me wrong answer to have the array which is not in ascending order in question C. Is this a bug? 186207153
Here, fixed it for you.
https://codeforces.com/contest/1772/submission/186978335
The logic was pretty much spot on. The only problem was in your 2nd while loop. In case the calculated
cntis bigger thana, your code would simply print more numbers than are asked for. So, I just added a check there.In problem D "Thus, take the minimum over the pairs of one type. Take the maximum over the pairs of another type. If two resulting values are contradictory, then there is no answer. Otherwise, any value inside the resulting range of x works." Why should that satisfied ?
For problem F, Shouldn't it pass in O(k^2*n*m) time complexity in 2 seconds, as it is O(10^7) operation? My solution 186467598. Can anyone help with this?
can someone confirm How many operations can we make in one second in codeforces ?
I have tested cf servers once and it was approximately $$$3*10^9$$$ per second for simple operations like memset which is actually enormously fast (blog with the same question)
Different Differences
can someone explain me what does it mean to be "We need to find an array [d1,d2,…,dk−1] so that the sum of elements in it is not greater than n−1"?
Let's do some cases and math to understand it.
Let $$$k=n=4$$$. So $$$a$$$ will be $$$[a_1, a_2, a_3, a_4]$$$ and $$$d$$$ as $$$[d_1, d_2, d_3]$$$ or, specifically, $$$[a_2-a_1, a_3 - a_2, a_4-a_3]$$$. Start all elements of $$$d$$$ in $$$1$$$ (which is the minimum possible, since $$$a_{i+1}> a_{i})$$$, so $$$d=[1,1,1]$$$. Note the sum of $$$d$$$ is $$$3$$$ which is not greater than $$$n-1 = 3$$$. If you were to change $$$d$$$ for $$$d=[2,1,1]\Rightarrow a = [1, 3, 4, 5]$$$, note that this violates the statement "Construct an increasing array of k integers from 1 to n" because $$$a_4=5>n$$$ . Therefore, you can increment elements of an initialized $$$d = [1, 1, 1]$$$ such that the sum of it is not greater than $$$n-1$$$.
Let's do other example with $$$k=3, n=4$$$. Now, $$$a = [a_1, a_2, a_3]$$$ and $$$d=[d_1, d_2] = [a_2-a_1, a_3-a_2]$$$ Initialize $$$d = [1,1]$$$ (you know an array $$$d$$$ of size $$$k$$$ full of 1s is always the minimum possible solution because $$$a_{i+1} > a_i$$$ and $$$ k \leq n $$$). The sum of $$$d$$$ is $$$2$$$ which is not greater than $$$n-1=3$$$, Note this time if you increase one of his elements, i.e., $$$d=[2,1]$$$ it actually maintains the condition of the sum ($$$3$$$) not being greater that $$$n-1 = 3$$$. Between these two possibilities the second one has the maximum possible characteristic which is 2 different elements, while the first one only has 1. So using the second $$$d\Rightarrow a = [1, 3, 4] $$$, which is one plausible solution. I hope this was helpful.
PD: Math part for deep understanding
¿where is coming from this "weird" condition of the sum of $$$d$$$ not greater than $$$n -1$$$? Well, you can actually take any strict increasing finite sequence such as $$$a = 1,2,3,4$$$ or $$$a = 7,23, 50, 51$$$ and take the first difference $$$d$$$ and see that the last element of the sequence is always greater that the sum of $$$d$$$. For the first sequence, $$$d=1,1,1$$$ and the sum of it (3) is less than the last element of the sequence (4). For the second one, $$$d=16,27,1$$$. Taking the sum (44), it is still less than its last element of (51). Even though you can see this apparently works, you must prove it for all $$$k\geq 2$$$
Take a finite strict-increasing sequence of $$$k$$$ elements $$$a=[a_1, a_2, a_3, ..., a_k]$$$. The sum of $$$d=[a_2-a_1, ..., a_k - a_{k-1}]$$$ is $$$\sum_{i=2}^k (a_i - a_{i-1}) = (a_2-a_1) + (a_3-a_2) + \dots + (a_k-a_{k-1})$$$.
Then the statement you want to prove is simply $$$\sum_{i=2}^k (a_i - a_{i-1}) < a_k$$$ and this can be proved easily by induction (left to the reader).
Therefore, if the sum of $$$d$$$ is greater or equal to $$$a_k$$$ (or following the tutorial, simply greater than $$$a_k -1$$$) there is no finite strict-increasing sequence $$$a=a_1, ..., a_k$$$. So, when you are checking for all the possible $$$d$$$'s, if the condition is not satisfied then the $$$d$$$ that does not satisfy cannot lead to a finite strict-increasing $$$a = a_1, ..., a_k$$$, which was exactly what happened in the very first example $$$k=n=4$$$ when we tried with $$$d=[2,1,1]$$$.
Thank you for that brief explanation. I really appreciate your effort in this.
Can anyone help me understand the solution for C? It really looks like there are two magic observations, which are key to unlock the solution
For Problem C, why these outputs are not accepted?
1 2 4 7 9
1 2 4 7 11
1 2 3
1 2 4
1 2 3 4
1 2 4 6
1 2 4 7 8 9 10 11
Edit: Got accepted, no worries!
What's wrong with problem E? For Arrangement of "1 2 4 3" How First Can Win?
Optimal Steps — for initial state of 1(R) 2(R) 4(R) 3(R) moves - First Player — R to B for 3, current state 1(R) 2(R) 4(R) 3(B) Second Player — R to B for 1, current state 1(B) 2(R) 4(R) 3(B) First Player — R to B for 4, current state 1(B) 2(R) 4(B) 3(B) Second Player — swap (1, 4), current state 4(B) 2(R) 1(B) 3(B) and keeps going on.
The Optimal steps can lead to a tie. Because of we can skip our moves. Am I getting the problem in the wrong way? Can anyone guide me?
*NOTE — Many have come to the conclusion that 1st operation of rearranging should be done only if there is an instant win. But Is it really? We can use that operation to let the opponent suffer from winning too right? like I won't win but you won't too.
First Player -- rearrange: 1 2 3 4, win. Players do not just swap the two elements. Each turn, a new permutation is produced. In other words, they are free to change the order of all the blue elements at the same time.
Oh! Thanks, man, I misread :3
what's wrong with this solution for part C? I'm getting wrong answer in test 2
197560571 whats wrong with this can anyone help