Мы надеемся вам понравились задачи.
Задача 1977A - Маленький Никита была придумана Stefan2417 и подготовлена alexchist
Задача 1977B - Бинарная покраска была придумана alexchist и подготовлена Stefan2417.
Задача 1977C - Никита и ТЧ была придумана и подготовлена Stefan2417.
Задача 1977D - XORофикатор была придумана и подготовлена alexchist
Задача 1977E - Тензор была придумана и подготовлена Stefan2417
Заметим, что одно действие с кубиком меняет четность количества кубиков в башне. Тогда если четности $$$n$$$ и $$$m$$$ не совпадают, то нельзя построить башню. Также если $$$n < m$$$ то башню тоже нельзя построить. В остальных случаях можно построить башню высоты $$$m$$$ за $$$m$$$ операций, а потом добавлять и удалять кубик, пока операции не закончатся.
#include <bits/stdc++.h>
using namespace std;
int main () {
ios_base::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
cout << (n >= m && (n%2) == (m%2) ? "Yes" : "No") << '\n';
}
}
Будем перебирать префикс из $$$i$$$ бит и строить корректный ответ для числа образованного префиксом бит числа $$$x$$$. Нам интересно рассматривать только единичные биты, так как только они влияют на значение числа $$$x$$$.
Если в ответе мы уже поставили на место $$$i$$$ единицу, то нам нужно еще как-то получить к числу + $$$2^i$$$. Тогда просто обнулим $$$i$$$ бит в ответе и поставим его в $$$i + 1$$$ — как раз прибавится $$$2 \cdot 2^i = 2^{i+1}$$$.
Теперь на $$$i$$$ месте в ответе стоит $$$0$$$.
Рассмотрим что мы ставили в ответе на месте $$$i-1$$$. Если 0, то все хорошо, просто поставим $$$1$$$ на позицию $$$i$$$. Если стоит $$$1$$$, то возникла ситуация [1 1], исправим ее, сделав [-1 0 1] — на место $$$i-1$$$ поставим $$$-1$$$, на $$$i$$$ оставим 0, на $$$i+1$$$ поставим 1. К сумме прибавится $$$2^i$$$ так как $$$2^i + 2^{i-1}= 2^{i+1} - 2^{i-1}$$$ Теперь осталось разобрать случай когда на $$$i-1$$$ месте стоит $$$-1$$$. Но он невозможен, так как нашими операциями вперед мы ставим только единицы, а $$$-1$$$ ставятся позади.
Итоговая асимптотика $$$O( \log(x) )$$$ на 1 тестовый случай.
#include "bits/stdc++.h"
#define all(a) a.begin(), a.end()
#define pb push_back
typedef long long ll;
using namespace std;
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
/// Actual code starts here
const int N = 100005;
void solve() {
ll x;
cin >> x;
vector<int> res(31, 0);
for (int i = 0; i < 30; i++) {
if (1ll & (x >> i)) {
if (res[i]) {
res[i + 1] = 1;
res[i] = 0;
} else if (i > 0) {
if (res[i - 1] == 1) {
res[i + 1] = 1;
res[i - 1] = -1;
} else {
res[i] = 1;
}
} else if (i == 0) {
res[i] = 1;
}
}
}
cout << 31 << '\n';
for (int i = 0; i <= 30; i++) {
cout << res[i] << ' ';
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--)
solve();
}
Попробуйте проверить, подходит ли весь массив $$$a$$$ в качестве ответа.
Сначала поймем, можно ли взять в качестве особенной подпоследовательности весь массив $$$a$$$.
Для этого найдем LCM($$$a_1, a_2, \dots, a_n$$$). Если он больше, чем max($$$a_1, a_2, \dots, a_n$$$), то очевидно такого числа нет в подпоследовательности, так как $$$LCM \geq max$$$.
После этой проверки про массив $$$a$$$ становится известно, что каждый $$$a_i \ | \ max(a_1, a_2, \dots, a_n)$$$.
Тогда переберем делители максимума и жадно проверим наличие подпоследовательности с таким LCM.
Если делать это наивно, то будет $$$O(\sqrt{C} + n \cdot d(C) \cdot \log(C))$$$, но этого уже было достаточно.
Заметим, что можно подсчитать вхождение каждого числа и проверять только различные числа. Тогда асимптотика будет $$$O(\sqrt{C} + d(C)^2 \cdot log(C))$$$.
#include "bits/stdc++.h"
#define err(x) cerr << "["#x"] " << (x) << "\n"
#define errv(x) {cerr << "["#x"] ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
#define errvn(x, n) {cerr << "["#x"] ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
#define all(a) a.begin(), a.end()
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1000000007;
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T1, typename T2>
inline bool relaxmi(T1 &a, const T2 &b) {
return a > b ? a = b, true : false;
}
template<typename T1, typename T2>
inline bool relaxma(T1 &a, const T2 &b) {
return a < b ? a = b, true : false;
}
double GetTime() { return clock() / (double) CLOCKS_PER_SEC; }
/// Actual code starts here
const int N = 100005;
int calc(vector<pair<int, int>> &t, int d) {
int LCM = 0, cnt = 0;
for (auto [j, c]: t) {
if (d % j == 0) {
if (LCM == 0) LCM = j;
else LCM = lcm(LCM, j);
cnt += c;
}
}
if (LCM != d) cnt = 0;
return cnt;
}
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (auto &i: v) cin >> i;
ll LCM = 1;
int mx = *max_element(all(v));
for (auto i: v) {
LCM = lcm(LCM, i);
if (LCM > mx) {
cout << n << '\n';
return;
}
}
map<int, int> cnt;
for (auto i: v) cnt[i]++;
vector<pair<int, int>> t;
for (auto i: cnt)
t.push_back(i);
int res = 0;
for (int i = 1; i * i <= mx; i++) {
if (mx % i == 0) {
if (!cnt.contains(i))
relaxma(res, calc(t, i));
if (!cnt.contains(mx / i))
relaxma(res, calc(t, mx / i));
}
}
cout << res << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--)
solve();
}
Попробуйте зафиксировать особенность столбца $$$i$$$ и наличие единицы в клетке $$$i, j$$$.
Давайте зафиксируем, что значение в $$$i$$$-й строке $$$j$$$-м столбце строго единица и она единственная в столбце. Тогда вся таблица задается однозначно и XORофикатор тоже.
Тогда давайте для каждого возможного состояния XORофикатора, который строит нужную таблицу поддерживать счетчик. Тогда состояние, которое максимизирует количество столбцов, в котором стоит ровно 1 единица, имеет максимальный счетчик.
Для того, чтобы эффективно поддерживать счетчик, необходимо поддерживать хеш XORофикатора и быстро пересчитывать его при переходе в нижнюю строку.
Ответ можно восстановить просто пройдясь еще раз по таблице и считая хеш, если получился нужный, то просто вывести состояние XORофикатора.
Итоговая асимптотика $$$O(nm \log{(nm)})$$$ или $$$O(nm)$$$, если использовать hash map.
Для хеширования удобно использовать Zobrist hashing.
#include "bits/stdc++.h"
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
void solve() {
int n, m;
cin >> n >> m;
vector<vector<bool>> table(n, vector<bool>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
char c;
cin >> c;
table[i][j] = c - '0';
}
}
vector<long long> rands(n), rands2(n);
for (int i = 0; i < n; ++i) {
rands[i] = rnd();
rands2[i] = rnd();
}
map<pair<long long, long long>, int> ans;
int res = 0;
pair<int, int> ind_ans = {0, 0};
for (int j = 0; j < m; ++j) {
long long summ = 0, summ2 = 0;
for (int i = 0; i < n; ++i) {
if (table[i][j]) {
summ ^= rands[i];
summ2 ^= rands2[i];
}
}
for (int i = 0; i < n; ++i) {
summ ^= rands[i];
summ2 ^= rands2[i];
ans[{summ, summ2}]++;
if (res < ans[{summ, summ2}]) {
res = ans[{summ, summ2}];
ind_ans = {j, i};
}
summ ^= rands[i];
summ2 ^= rands2[i];
}
}
cout << res << "\n";
string inds(n, '0');
for (int i = 0; i < n; ++i) {
if (table[i][ind_ans.first]) {
if (i != ind_ans.second) {
inds[i] = '1';
}
} else if (ind_ans.second == i) {
inds[i] = '1';
}
}
cout << inds << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
}
Сначала поймем почему 2 цветов действительно достаточно.
Заметим, что отношение достижимости в графе задает Частично упорядоченное множество.
По теореме Дилуорса размер максимальной антицепи равен минимальному количеству цепей, покрывающих ЧУМ.
Заметим, что условие на достижимость пары вершин внутри любой тройки влечет ограничение на максимальный размер антицепи. Он просто не больше 2. Значит 2 цветов действительно достаточно.
Осталось понять как явно строить эти 2 цепи.
Будем строить индуктивно. Давайте поддерживать 3 стека — последние вершины покрашенные в черный цвет, белый цвет и красный цвет соответсвенно. Они будут отвечать за цепи, которые мы строим.
Пусть мы построили цепи на $$$n$$$ вершинах и хотим построить на $$$n + 1$$$:
- Если белый или черный стеки пусты то просто добавим вершину $$$n+1$$$ в пустой стек.
- Если красный стек пустой:
-
- Спросим про достижимость последних вершин из белого и черного стеков из вершины $$$n+1$$$.
-
- Если достижимы обе вершины, то отправим вершину $$$n+1$$$ в красный стек.
-
- Если достижима только 1 вершина то отправим вершину $$$n+1$$$ в стек, последняя вершина которого достижима из $$$n+1$$$.
-
- Случай когда достижимо 0 вершин невозможен так как это противоречит условию.
Если красный стек не пустой:
-
- Спросим про достижимость последней вершины красного стека из вершины $$$n+1$$$.
-
- Если она достижима, то отправим ее в красный стек
-
- Если она не достижима, то сделаем вопрос про конец белого стека.
-
- Если вершина из конца белого стека не достижима, то тогда обязана быть достижима вершина из конца черного стека, иначе происходит противоречие с условием задачи.
-
- Покрасим вершину $$$n+1$$$ в черный стек, если достигается черная вершина или в белый стек, если достигается белая вершина.
-
- Перекрасим все вершины из красного стека в противоположный цвет относительно $$$n+1$$$ вершины. Мы так можем сделать так как по построению все вершины белого и черного стеков достижимы из всех вершин красного стека.
-
- не забудем очистить красный стек
При каждом добавлении новой вершины тратится не более 2 запросов. Тогда суммарно мы потратим не более $$$2 \cdot n$$$ вопросов.
В ходе алгоритма все операции производятся за $$$O(1)$$$, тогда асимптотика $$$O(n)$$$.
В качестве упражнения читателю предлагается доказать нижнюю оценку на количество запросов.
#include "bits/stdc++.h"
#define err(x) cerr << "["#x"] " << (x) << "\n"
#define errv(x) {cerr << "["#x"] ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
#define errvn(x, n) {cerr << "["#x"] ["; for (auto ___ = 0; ___ < (n); ++___) cerr << (x)[___] << ", "; cerr << "]\n";}
#define all(a) a.begin(), a.end()
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD = 1000000007;
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
template<typename T1, typename T2>
inline bool relaxmi(T1 &a, const T2 &b) {
return a > b ? a = b, true : false;
}
template<typename T1, typename T2>
inline bool relaxma(T1 &a, const T2 &b) {
return a < b ? a = b, true : false;
}
double GetTime() { return clock() / (double) CLOCKS_PER_SEC; }
/// Actual code starts here
const int N = 100005;
bool ask(int i, int j) {
cout << "? " << j << ' ' << i << endl;
string resp;
cin >> resp;
if (resp == "-1") assert(false);
if (resp == "YES") return true;
else return false;
}
void solve() {
int n;
cin >> n;
vector<int> st, st2, st3;
st = {1};
for (int i = 2; i <= n; i++) {
if (st2.empty()) {
if (ask(i, st.back())) {
st.push_back(i);
} else {
st2.push_back(i);
}
} else if (st3.empty()) {
int ok1 = ask(i, st.back()), ok2 = ask(i, st2.back());
if (ok1 && ok2) {
st3.push_back(i);
} else if (ok1) {
st.push_back(i);
} else if (ok2) {
st2.push_back(i);
} else {
assert(false);
}
} else {
if (ask(i, st3.back())) {
st3.push_back(i);
} else {
if (ask(i, st.back())) {
st.push_back(i);
for (auto j: st3)
st2.push_back(j);
st3.clear();
} else {
st2.push_back(i);
for (auto j: st3)
st.push_back(j);
st3.clear();
}
}
}
}
if (!st3.empty()) {
for (auto i: st3)
st.push_back(i);
st3.clear();
}
vector<int> colors(n + 1);
for (auto i: st2)
colors[i] = 1;
cout << "! ";
for (int i = 1; i <= n; i++) cout << colors[i] << ' ';
cout << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--)
solve();
}
better late than never. thank you for the editorial
Ooooh so you have a temporary third chain in E. I love it, it's close to what I was trying and makes it so elegant. Also thank you for the proof of existence using Dilworth.
The contest was of huge quality, one of my favorite codeforces. Thank you setters. orz
for the 2nd question; can anyone help me debug why/where is my logic wrong? its different than author's. https://codeforces.me/contest/1977/submission/262928317
It says "wrong answer coefficients do not sum to x (test case 3)" (failed on 1359) in the second test.
https://codeforces.me/contest/1977/submission/262935920
Here are the minor changes I've made.
oh yess, thank you for the correction, i get it now.
Thanks for the editorial!
Does anyone know any similar problems to C, Want to improve on the concept of LCM, GCD and divisors.
Does anyone know any similar problems to C,
Want to improve on concepts of LCM, GCD and divisors.
Learn it from math/number theory books, not codeforces problems.
Please can you suggest some good books?
this post my help bro https://codeforces.me/blog/entry/118882
thanks
I liked these problems https://codeforces.me/problemset/problem/1884/D https://codeforces.me/problemset/problem/1900/D
Yo for C can someone explain me this part?
"Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM."
It's not immediately clear why this will yield the max sequence bro
Edit: nvm I acc get it now it's clear from the tutorial, I'm so stupid bro
not easy to understand immediately, you are clever bro
thanks bro I needed that ego boost lmfao
Thank you so much Stefan! I quite enjoyed figuring out the solve to question C, even if I only figured it out after the contest... Question B was satisfying as well.
Radewoosh, This proves not only Indians say "question" instead of "problem".
what does this mean in C problem tutorial?? "Then we iterate over the divisors of the maximum and greedily check for the presence of a subsequence with such an LCM."
Basically since all elements in
a
dividemax(a)
, then any combination of elements ina
will have an LCM that dividesmax(a)
too. And for an LCM to belong to a sequence, it must beUsing those facts our search space is now the divisors of
max(a)
where we just need to check for those two facts and greedily get the maximum subsequence.crazzy bro,, great explaination. just one thing why this check is necessary in calc func? if (LCM != d) cnt = 0; as it will always be equal, right?
not always, take this for example:
3 2 10 20 60 1
here the overall LCM is 60 so we search over its divisors. If we choose 4, then only 1 and 2 divide it, but their LCM is 2 (which is acc in
a
), not 4. We're searching for a subsequence that has exactly that divisor as its LCM for this iteration so 4 is not even valid to consider.yup got it
Very well explained. This should be a part of the editorial! Thanks bruh
Can someone explain the solution of Problem D. Only thing I am seeing is Xor and Random numbers. Totally Confused right now!!
PS: Understood the solution. But why are we keeping 2 random numbers of each index?
To reduce the probability of collision. It's for the same reason that you use two modulos in hashing sometimes.
Oh! Okay. Thanks!
Will you please explain it for us?
Suppose we want the 1st column to contain exactly one 1. Then there are n options in which we can have that 1. Let's say we make the only one 1 at the first row itself. Then the set (of each row) of XORificator used will be unique. Similarly, it will be unique for each of the (i, j) if we decide that in the jth column the only 1 will be at ith row.
So, now we will calculate all the unique set of XORificator, for which we have used hashing. Now, if the cnt[hash] is x that means x columns will contain only one 1 with the following set of XORificator. So, you can just choose the one with the most cnt and that will be your answer.
Yep! Got the feel. Thanks.
But we still have a non-zero probability of getting a wrong answer , right?
No, it's actually 0, the only reason it might cause a wrong answer is when the hash values collide, where as seen in the editorial you can just store 2 values for the hashes, making the hash collision probability wayyy less(around 0 for the problem constraints), but a single hash suffices
Why is the probability zero: Well, the lower bound of the answer is 1, cause you can just select a single column and invert every 1 except one. Now imagine You selected the column $$$i$$$ as the column with the single inverted 1, and the row $$$j$$$ as the 1 bit, since there is only a single way to make that cell $$$(i, j)$$$ to be one and none other $$$(i, k)$$$, the operations you chose are unique, so just save the resulting table best answer, and since there is no other way to fix $$$(i, j)$$$, if it was to fix $$$(i, j)$$$ this would be the best result, just take the maximum for every $$$(i, j)$$$
Short answer: the only reason the probability for WA is 0 is just that for a fixed (i, j) there is only a single way to do it
It is not zero, but a very small probability (negligible for the purposes of passing tests).
which probability isn't zero? hash collision or the idea itself? (regarding of the hash function)
Like there is a chance that not fixing anything will be the best answer? in that case there is at least 1 column is special(since we know that the answer >= 1), where its answer is calculated during the selection of that column and row
You can't say that the probability is exactly zero unless you can make sure that there is absolutely not a single case where a hash collision that leads to wrong answer occurs, which is why we say it's a 'non-zero probability' because it is indeed not exactly zero, but negligible.
By zero I meant the prob of wrong answer not considering hash collisions, but yes, taking that into part even if u have 10000 different hash values for a single element there is always a way for the to collide even when n = 2, (and in my original comment I said unless hashes collide)
It seemed quite obvious to me that the original question was asking about whether hash collision can occur or not (because otherwise they wouldn't say terms like non-zero probability), so starting with saying directly "no, it's actually 0" to that question looked like you had some clear evidence that it can always avoid hash collision (or even if that occurs you still won't get wrong answer) somehow.
Ohh, I thought the question was asking if there is a chance the idea itself not being correct and giving wrong answer
yes , i was referring to the hash collisions. Can't we generate test cases for which there is high chances of collisions(considering the hash functions used)? Thanks
For B I did some uninteresting wack shit. Someone explain Jiangly or Tourist's solution for B please? They did something like % 4 = 1 then 1, % 4 = 3 then -1 and % 2 = 0 means 0.
In problem B, why is [-1 0 -1 -1 0 1] not a valid answer for x = 19? -1 + 0 + -4 + -8 + 0 + 32 = 19, so why am I getting wrong answer? Judge says "wrong answer. wrong coefficient format.", what am I doing wrong?
Atleast 1 number for every pair of adjacent elements should be 0
@SriRam523 How did you understand this point from the problem?
In the constraints of the problem (at the top), it reads, "There does not exist an index $$$0≤i≤n−2$$$ such that both $$$a_i≠0$$$ and $$$a_i+1≠0$$$."
Could someone explain the hashing in D. I could come up with the idea of trying to fix a $$$i, j$$$ cell to be 1, but couldn't deal with the efficient XOR operations. What will we actually hash right here?
You want to count which configuration on the rows appearead most often : if a given configuration appeared n times, it means that there will be n special columns if you use it.
So if you name a configuration "000110" for example (meaning flip rows 4 and 5 only), you want to hash this string to keep track of how many times it appeared. The issue is that you want this hash in O(1) time. Luckily, if, for each column, you try to make bit 1 special, then bit 2 special, etc... you will notice that the string representation of your configurations does not move much (only 1 or 2 characters change each time). So you want a hash that you can easily change in O(1) using this property instead of re-hashing in O(n).
For this, you can use author's trick to prevent collision, or use a more classic technique of "rolling hash" which worked for me for example.
I believe there is a typo in C's tutorial, it should be LCM > max
I am unable to understand why I am getting WA in problem C.
submission
I am unable to understand why I am getting WA in problem C.
submission
A possible reason:when you calculate the LCM of all elements, it will go beyond i64. So try to stop getting LCM as it becomes larger than the max element. (Cool painting btw)
Thanks for pointing it out. Got AC. Thanks for the painting as well :}
For D I got the idea, but why if I use an unordered_map to keep track of how many time had a configuration appeared I will get a ME
(At first, I wanted to use 01trie to maintain the times a configuration appeared but I think it would get a ME too.
Problem D can have also have deterministic solution rather than probabilistic one. we can write the solution for two different cases (m > n and m <= n). for m > n number of rows are less than 550, for a cell in the grid to be 1 the set of rows to be flipped can be encoded into a string (len < 550), complexity: n * n * m (n < 550). these strings can be stored in a map with their count and max count string is answer. unordered map can be used for speed up. for m <= n we can solve this using dp, where two columns differing at two or zero places are used for transitions, we check every pair of columns for transitions, answer can easily be constructed for a cell having max dp value, complexity: n * m * m (m < 550), max iterations ~ 1.65 * 10 ^ 8, safely under the time limit:
262840232
hey i was also using the same approach but didnt separate the case of m>n and my sol tled.Nice to see i was half right for the dp.Thanks
Can someone please explain the time complexity of Question C?
Has anyone tried solving problem C with the Hasse graph (an edge $$$u \rightarrow v$$$ means $$$v | u$$$ )? It's easy to construct it in $$$O(n^2)$$$ but I can't find a way to maximize the set (I tried DP on graph). Eventually I did to the Brute force solution.
i'm struggling with problem C.
here is my approach.
[solve for N]
if N <= 1: return 0
if LCM(A[1] ~ A[N]) overflow A[N]: return N
if LCM(A[1] ~ A[N — 1]) == A[N]: find maximum length subsequence its LCM is not A[N] <- brute force
if LCM(A[1] ~ A[N — 1]) < A[N]: [solve for N — 1]
https://codeforces.me/contest/1977/submission/263102096
what is wrong with my code
In the authors code for D did he just ignore the possibility of collisions? If yes then is this normal in competitive programming to ignore collisions if chances are too low?
Yep, if there's not a huge chance of collision then you can mostly ignore it
Honestly, don't know how I didn't realize that the LCM on C could be bounded that easily, I guess we have good and bad days
[RU] Здравствуйте! Не могу понять, почему мой код для задачи B проходит тесты на c++, но не проходит на c. Когда я выбираю компилятор c, то моя программа почему-то не проходит ограничение по времени на втором-третьем тесте. Объясните мне, новичку в c, где я ошибся.
[EN] Hello! I can't understand why my code for task B passes tests in c++, but does not pass in c. When I choose the c compiler, for some reason my program does not pass the time limit on the second or third test. Explain to me, a beginner in c, where I made a mistake.
Can the problem C be solved by Dynamic Programming ?
you can solve it with recursive and memoization but you need to use unordered map
262785009
Check out this soln
Thanks !!!
Can you please explain the logic behind this part of your solution:- I am not able to understand it.
if part
if our current lcm which is val,if we take lcm(val,a[p]) ll LCM = lcm(val, a[p]); if after taking lcm our result LCM comes an element which is already present int mp[] that means it's the factor in that case we hope that in future we can form a sequence that doens't exit in mp other wise base condition return a large negative value =-1e17
else part
now we get out LCM which isn't present in mp[] that means we can form sequnce till that and also we can also increase our sequnce further
but we have to store temporary ans that's why this max(mp[a[p]] * 1ll, mp[a[p]] * 1ll + func(p + (mp[a[p]] — 1), LCM, a, n))) first part in max return ans till that if we don't able to increase our length and 2nd part return the max if we can increase our length
now why i use m[p] instead of 1 bc
if we have element like 5 7 7 7 7
we can just take 5 7 7 7 as whole rather than
5 7
5 7 7
5 7 7 7
hope u understand
Yeah, Thanks
Has anyone tried divide and conquer in B? There are 5726623061 sequences of {-1, 0, 1} lenght 32 with at least one zero among every 2 adjacent elements. We can bruteforce first 16 elements of the sequence, and use precalced values for other half.
I have another approach for C :
sort the array and check for the longest prefix such that lcm of that prefix is not the last element of the corresponding prefix.
is this wrong?
Stefan2417, problem E editorial is incorrect.
Let $$$n = 3$$$ and only one edge $$$1 \leftarrow 2$$$. According to the text solution $$$1$$$ will be white and $$$2$$$ will be black (or vice versa). Then the red stack is empty, but no vertexes are reachable from the 3rd. You said such a situation is impossible, but here it is.
The editorial is incorrect, but the code handles this case correctly. In particular, the part
does not match with the editorial; the editorial says that the vertex should be put into the empty stack by default, but the code puts it into the first stack, if the last vertex in the first stack is reachable from the current vertex, and into the second stack only if the aforementioned condition is not true.
In editorial C, What d(C) means?
divisors of max element
In editorial C, why is O(N * d(C)) sufficient? Is'nt N <= 10**3 and C <= 10**9, thus O(d(C)) <= square root of C which is 10**4?
Would'nt O(N * d(C)) be 10**7 than?
A number up to $$$10^9$$$ can have at most $$$1344$$$ divisors. Check https://codeforces.me/blog/entry/14463.
[user:Stefan2417]Stefan2417
In Problem C this solution should not pass but it passes.
Please anyone try to hack it. https://codeforces.me/contest/1977/submission/263672671
I don't get C — Nikita and LCM. I understand that if the lcm of the whole array is equal to the max element in the array, then all elements divide the max. What I take from this is that the max element should not be in our solution subsequence.
What does "iterate over the divisors of the maximum" mean?
It means that If all the elements in array A are divisible by max(A), LCM of any subset of A will be divisor of max(A).
Let $$$a_i = p_1^{x_1} * p_2^{x_2} * p_3^{x_3}...$$$, where $$$p_i$$$ is the i'th prime number and $$$x_i\,€\,Z$$$ such that $$$x_i \ge 0.$$$ So LCM of this array is $$$p_1^{max(x_1)} * p_2^{max(x_2)} * p_3^{max(x_3)}...$$$ If number $$$a_i$$$ is extracted from this list, no primes $$$p_1 ... p_n$$$ were added to the new LCM, we can just decrease $$$max(x_i)$$$'s with this way, so new LCM will remain as a divisor of max(A). (Apologies for first time using latex.)
Do you mean if all the elements in array A divide max(A)?
Yes, If they didn't the answer would be simply length of array A which is N.
For problem "B" how can it be a WRONG_ANSWER.Can anyone help? https://codeforces.me/contest/1977/submission/264399208
Input 7 1 14 24 15 27 11 19 Participant's output 1 1 5 0 -1 0 0 1 6 0 0 0 -1 0 1 5 -1 0 0 0 1 6 -1 0 -1 0 0 1 5 -1 0 -1 0 1 6 -1 0 -1 -1 0 1
two consecutive -1s are there in the last output.
282198440 Can anyone please tell me what's wrong in this ?
lastonemaman