1624A - Plus One on the Subset
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
void solve() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int MIN = INT_MAX;
int MAX = INT_MIN;
for (int i = 0; i < n; ++i) {
MIN = min(MIN, a[i]);
MAX = max(MAX, a[i]);
}
cout << MAX - MIN << '\n';
}
int main() {
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
void solveTest() {
int a, b, c;
cin >> a >> b >> c;
int new_a = b - (c - b);
if(new_a >= a && new_a % a == 0 && new_a != 0) {
cout << "YES\n";
return;
}
int new_b = a + (c - a)/2;
if(new_b >= b && (c-a)%2 == 0 && new_b % b == 0 && new_b != 0) {
cout << "YES\n";
return;
}
int new_c = a + 2*(b - a);
if(new_c >= c && new_c % c == 0 && new_c != 0) {
cout << "YES\n";
return;
}
cout << "NO\n";
return;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt;
cin >> tt;
while(tt--)
solveTest();
return 0;
}
1624C - Division by Two and Permutation
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int>a(n), used(n + 1, false);
for(auto &i : a) cin >> i;
sort(a.begin(), a.end(), [] (int a, int b) {
return a > b;
});
bool ok = true;
for(auto &i : a){
int x = i;
while(x > n or used[x]) x /= 2;
if(x > 0) used[x] = true;
else ok = false;
}
cout << (ok ? "YES" : "NO") << '\n';
}
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_N = 2e5;
int main(int argc, char* argv[]) {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
int n, k;
string s;
cin >> n >> k >> s;
vector<int> cnt(26);
for (char c : s) {
cnt[c - 'a']++;
}
int cntPairs = 0, cntOdd = 0;
for (int c : cnt) {
cntPairs += c / 2;
cntOdd += c % 2;
}
int ans = 2 * (cntPairs / k);
cntOdd += 2 * (cntPairs % k);
if (cntOdd >= k) {
ans++;
}
cout << ans << '\n';
}
}
Idea: Aris
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
const int N = 1e4;
map<string, bool> have;
map<string, tuple<int,int,int>> pos;
void solve() {
int n, m; cin >> n >> m;
vector<bool> dp(m+1, false);
vector<int> pr(m+1);
vector<string> cache;
dp[0] = true;
forn(i, n) {
string s; cin >> s;
forn(j, m) {
string t;
t += s[j];
for(int k = 1; k <= 2; k++) {
if (k + j >= m) break;
t += s[j+k];
if (!have[t]) {
have[t] = true;
pos[t] = make_tuple(j, j+k, i);
cache.push_back(t);
}
}
}
}
string s; cin >> s;
forn(i, m) {
string t;
t += s[i];
for (int k = 1; k <= 2; k++) {
if (i - k < 0) break;
t = s[i-k] + t;
if (have[t] && dp[i-k]) {
dp[i+1] = true;
pr[i+1] = i-k;
}
if (dp[i+1]) break;
}
}
for (string t : cache) {
have[t] = false;
}
if (!dp[m]) {
cout << "-1\n";
return;
}
vector<tuple<int,int,int>> ans;
for (int k = m; k > 0; ) {
int p = pr[k];
string t = s.substr(p, k - p);
ans.emplace_back(pos[t]);
k = p;
}
cout << sz(ans) << '\n';
reverse(ans.begin(), ans.end());
for (auto [l,r,i] : ans) cout << l+1 << ' ' << r+1 << ' ' << i+1 << '\n';
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const int inf = 1e10;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
signed main(){
int n;
cin >> n;
int l = 1, r = n;
int div = 0;
while(r - l > 1){
int mid = (r + l) / 2;
cout << "+ "<< n - mid << endl;
int d;
cin >> d;
if(d > div)l = mid;
else r = mid;
l = (l + n - mid) % n;
r = (r + n - mid) % n;
if(r == 0) r = n;
div = d;
}
cout << "! " << div * n + l;
return 0;
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const int inf = 1e9;
const int M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
int n, cur;
vector<vector<pair<int, int>>> sl;
void dfs(int v, vector<bool> &used){
used[v] = true;
for(auto e: sl[v]){
int u = e.x, w = e.y;
if(!used[u] && (cur | w) == cur){
dfs(u, used);
}
}
}
void cnt(int pw){
if(pw < 0) return;
int d = (ll) 1 << pw;
cur -= d;
vector<bool> used(n);
dfs(0, used);
for(bool b: used){
if(!b) {
cur += d;
break;
}
}
cnt(pw - 1);
}
void solve() {
int m;
cin >> n >> m;
sl.assign(n, vector<pair<int, int>>(0));
for(int i = 0; i < m; ++i){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
sl[u].emplace_back(v, w);
sl[v].emplace_back(u, w);
}
cur = 1;
int bit = 0;
for(; cur < inf; bit++){
cur = 2 * cur + 1;
}
cnt(bit);
cout << cur;
}
bool multi = true;
signed main() {
int t = 1;
if (multi) {
cin >> t;
}
for (; t != 0; --t) {
solve();
cout << "\n";
}
return 0;
}
How is problem G only of 1900 difficulty? It's a really nice problem, but in my opinion it is way harder than problem F.
More people solved G, difficulties are calculated dynamically from the number and ratings of the people who solved it in-contest.
I think it's because G is a bit easier if you have a DSU implementation and have solved similar problems before (Kruskal's algorithm), while you have to be very careful when implementing F to ensure the modified binary search is correct, especially as it's harder to locally test interactive problems, generally speaking.
Of course, there is some variation/subjectivity in which problems individuals may consider easier or harder.
Spheniscine Can you explain why we start with the highest bit first rather than the lowest and then choose the next higher bit to check for it's feasibility in the final answer?
Comparing two numbers is like comparing their bitreps in lexicographic order, higher bits take priority
Thanks for the reply, I understood the thing you said about the higher bit taking the priority. Since if one number has a bit ON and the some other has that very bit OFF than we don't really care about the bits on the right side. But I am not able to understand that why in this very particular problem we can't go from bit 0 to bit 30. Is it not consistent with the submasking procedure. Or is there something else? Am I missing some fundamental theory knowledge for submasking?
Because there is a step where you keep only the edges with $$$k$$$-th bit $$$0$$$ if it won't disconnect the graph. Trying to do that the other way won't work, as then you'd give the lower bits priority over higher ones.
I'll try to explain why we cannot go from 0 to 30.
Let's say you are going from 0 to 30. Since you need to minimise the ans you try to make the current bit 0. So, let's say you reach a point ??000 where the last 3 bits have been assigned greedily to minimise ans. But, now there can be a possibility that the answer will be 11000. Whereas there is also a possibility that if you choose ??011 when going from 0 to 30, you end up with 00011. So, greedy won't work if we go from 0 to 30.
But, let's say that we go from 30 to 0. Now, if greedily, we take 000??, then it doesn't matter what next bits we get. By taking any option other than greedy will never give you better answer.
if this is still not clear, let's do some calculations.
We took 000?? which means that the first 3 bits are 0. This we took greedily. In worst case, next two digits will be 1. So, answer is 00011.
Now, for first three bits, what other choices we had? 001??, 010??, 011??, 100??, 101??, 110??, 111??. Even if you replace all ? with 0 now, they will all be greater than 00011. Hence, greedy works.
Note that 2^x > 2^(x-1) + 2^(x-2) + ... 2^1 + 2^0.
The problem G was much easier for those, who tried to solve it. It even required some observation or luck to skip E and F during the contest to go for it! I think that if the problem G was swapped with E, then it would have had even more successful submissions and even lower estimated difficulty.
It is also not the first obvious and easily solvable DSU library problem on Codeforces. We already had a similar D. Social Network problem (rated as 1600) during the recent Deltix round.
Has anyone done C with graph matchings like the tag mentioned, if yes, kindly share your code
enjoy 142236492
...
...
Would D be solveable if I binary searched on the answer and tried to construct k palindromes using the counts for each character?
its okay, i did it in this way
nice, didn't solve in contest mostly b/c of time but partially b/c of the way the problem statement was written.
Edit: Solved it!
omg i thought G is xor and got stucked... so any idea if we need to minimize the xor sum?
What does interacdive (problem f) mean?
https://codeforces.net/blog/entry/98759?#comment-876862
(FYI, it's "interac-div-e", for the division operation)
A greedy solution for C works as well.
There is no need to sort the array.
yeah it's just for convenience of implementation. You could simply find the largest unvisited element and do the same.
For every a[i] (1<= i <=n),you can find largest number that is not yet formed and can be formed by a[i]. You no need to find largest unvisited element . 142229284
Can somebody please give proof of the problem C solution?
Complete overkill solution of C using maximum bipartite matching:
Create a graph with $$$2n$$$ vertices. First $$$n$$$ of these vertices represent the permutation points and the next $$$n$$$ represent the array elements. Draw an edge to all permutation points reachable from all elements of the array ($$$O(n \log A)$$$ such edges). Now run maximum matching on this graph. Answer is yes if the number of edges in the matching is $$$n$$$ and no otherwise.
Submission : https://codeforces.net/contest/1624/submission/142329187
After a long, long time, the editorial of this round was published!
Can somebody help me with F please. I tried to bruteforce all the numbers in the range [1,n] in O(n). I added the same number to the array elements that I queried the judge. After receiving the query, I just marked all the numbers which didn't match the query value. I agree the approach isn't good because I ended up with more than one number in some cases. I still think it isn't totally wrong. Can somebody help me in either correcting my solution or proving that I cannot get an AC with this approach? 142283459 As always, I will be grateful. Thanks in advance.
Jury printed n as: 10
Jury has picked x as: 9
Participant asked to add: 5, x has now become: 14 Jury responded with 1
Participant asked to add: 7, x has now become: 21 Jury responded with 2
Participant asked to add: 8, x has now become: 29 Jury responded with 2
Participant asked to add: 9, x has now become: 38 Jury responded with 3
Participant asked to add: 9, x has now become: 47 Jury responded with 4
Participant asked to add: 9, x has now become: 56 Jury responded with 5
Participant asked to add: 9, x has now become: 65 Jury responded with 6
Participant asked to add: 9, x has now become: 74 Jury responded with 7
Participant asked to add: 9, x has now become: 83 Jury responded with 8
Participant asked to add: 9, x has now become: 92 Jury responded with 9
Participant has guessed the current x as: 91 The guess was incorrect.
Thanks. Did you find the code segment that was causing the error? Or is the answer wrong as a whole?
1624G — MinOr Tree https://codeforces.net/contest/1624/submission/142429144 Why it is giving TLE?
Your solution works in O(m * 100 * 49), which is quite slow for m <= 2e5. I don't know why you check so many bits (the numbers in the input have up to 30 bits), so changing that would probably make it barely pass, also your check function can be written in O(1) by changing the bit array to a single integer which has 1 bits on positions where edges should have 0. Now, an edge is valid if weight & bits == 0 (all necessary bits are off in the weight). Just remember to flip the bits in the end.
ohhhkk, Done Thank you
can you tell me why I get TLE https://codeforces.net/contest/1624/submission/160756528
Can someone explain why the greedy solution for problem C always works?
Can u please describe what exactly the greedy solution that you are talking about?.
I think it is forming larger numbers in permutation first then looking for smaller numbers.
It is mainly because, if you are able to get a number i from x indices and number j from y indices where 1 <= i < j <= n and you get i in the sequence when you are continuously dividing j by 2. Then you can say that x >= y because every index that can produce j can also produce i and some extra indices can produce i but not j. If you use indexes that are able to produce i first then you might left out with indexes that can produce i but not j. then you may not produce j . So it is better to produce j first then i next.
If you are looking for video solutions, you can find them Here (All Problems)
Pls can somebody tell why this solution 142368820 for problem E is
not giving TLE
andwhat is its correct time complexity
. I think its time complexity is greater than O(n*m*m) (not sure). Any suggestion will be helpful. Thanks.I think your code luckily passed testcases . The complexity of your code is o(m *n * m). You have to do some precomputation of storing all possible 2 length or 3 lengths sub-strings possible from given n strings but instead of that you are iterating all the n strings when ever you want to know whether t is possible to make or not , which is adding a factor of o(n*m) which is actually can be done in o(1).
Problem G. MinOr Tree https://codeforces.net/contest/1624/submission/142442799 . Why this java solution is giving TLE?
i am also stuck with this, java solution is giving tle whereas the same logic runs in cpp
Problem C Can anybody tell me where i'am doing wrong (Getting WA at 4628th token) 142461170
We already have $$$[3, 4, 5, 6, 7]$$$, we just need to create $$$[1, 2]$$$ from $$$[4, 7]$$$ which can obviously be done.
My code is giving the right output..i:e YES.. can u please look it again
Sorry, my bad. Try this simple test case.
We already have $$$[2, 3]$$$ and we can convert $$$2$$$ to $$$1$$$. However, your code would produce NO.
1624G — MinOr Tree https://codeforces.net/contest/1624/submission/142528765 Why it is giving TLE?
can someone pls explain the sort fn problem c soloution "sort(a.begin(), a.end(), [] (int a, int b) { return a > b; });"
std::sort accepts a starting pointer, end pointer and a function according to which it will sort it. This function should take two inputs (for example a and b) and return true if a should come before b. [](int a, int b) {return a > b;} is short form for a function(also known as lambda). So basically all the statement does is sort a in descending order
Can anyone tell me why this solution 142543258 for E is giving TLE where this one 142542275 that I came across not giving tle.
Can someone please explain the approach of problem B !
We can either multiply a by m, multiply b by m or multiply c by m.
Case 1: We multiply a by m since am, b and c are in A.P., b = (am + c)/2
now do some algebra to find the value of m. If m is a positive integer, the answer is yes. if not, we need to consider the other cases. Now do a similiar process with the other 2 cases
Here ,according to your explanation of the case 1 , m will be = (2b — c)/a . Am I right ? And also if I do multiplication of m with each 3 element , I got case 1 : a*m , m = (2b — c)/a ;
case 2 : b*m , m = (a + c)/2b;
case 3 : c*m , m = (2b — a)/c
Now for example a = 10 ,b = 5 ,c = 30 , m values gets as -2 , 4 , 0 So what will be the answer , yes or no ?
You showed that we can make it an A.P. by multiplying b by 4 so the will be yes
I checked whether the m is positive or not for all the given test cases but 3 test cases are giving YES as an answer ,instead of No !
Show your code?
include <bits/stdc++.h>
// #include using namespace std; typedef long long int lli;
int main(){ lli t,a,b,c;
return 0; }
Read the question again, it says m should be a positive INTEGER. you have to also check if m is an integer
Amazing round! Any tips on how to get better?
Why am I getting Memory Limit Exceeded in this ?: (problem E)
Can somebody please give proof or more detailed explain of the problem D solution?
Whole problem statement story is unnecessary. What it is saying is: you can order characters into words that are pailindromes HOWEVER you want. You just need to follow rule to split word to k palindromes.
Can some one help me with this G-MinOr Tree?
For Problem G, why is it TLEing on test 42? Submission: 240490794
those who are getting WA on test case 2(test case 3648), try this test case