Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
long long n;
cin >> n;
int cnt2 = 0, cnt3 = 0, cnt5 = 0;
while (n % 2 == 0) {
n /= 2;
++cnt2;
}
while (n % 3 == 0) {
n /= 3;
++cnt3;
}
while (n % 5 == 0) {
n /= 5;
++cnt5;
}
if (n != 1) {
cout << -1 << endl;
} else {
cout << cnt2 + cnt3 * 2 + cnt5 * 3 << endl;
}
}
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
int t, n;
int cnt[3];
int main(){
cin >> t;
for(int tc = 0; tc < t; ++tc){
memset(cnt, 0, sizeof cnt);
cin >> n;
for(int i = 0; i < n; ++i){
int x;
cin >> x;
++cnt[x % 3];
}
int res = cnt[0];
int mn = min(cnt[1], cnt[2]);
res += mn;
cnt[1] -= mn, cnt[2] -= mn;
res += (cnt[1] + cnt[2]) / 3;
cout << res << endl;
}
return 0;
}
```

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
vector<int> p({4, 8, 15, 16, 23, 42});
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] = lower_bound(p.begin(), p.end(), a[i]) - p.begin();
}
vector<int> seq(6);
for (int i = 0; i < n; ++i) {
if (a[i] == 0) {
++seq[0];
} else {
if (seq[a[i] - 1] > 0) {
--seq[a[i] - 1];
++seq[a[i]];
}
}
}
cout << n - seq[5] * 6 << endl;
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 3 * 1000 * 1000 + 13;
int lst[N];
int num[N];
void sieve(){
forn(i, N) lst[i] = i;
for (int i = 2; i < N; ++i){
if (lst[i] != i){
lst[i] = i / lst[i];
continue;
}
for (long long j = i * 1ll * i; j < N; j += i)
lst[j] = min(lst[j], i);
}
int cur = 0;
for (int i = 2; i < N; ++i) if (lst[i] == i)
num[i] = ++cur;
}
int cnt[N];
int main() {
int n;
scanf("%d", &n);
forn(i, 2 * n){
int x;
scanf("%d", &x);
++cnt[x];
}
sieve();
vector<int> res;
for (int i = N - 1; i >= 0; --i){
while (cnt[i] > 0){
if (lst[i] == i){
--cnt[num[i]];
res.push_back(num[i]);
}
else{
--cnt[lst[i]];
res.push_back(i);
}
--cnt[i];
}
}
for (auto it : res)
printf("%d ", it);
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m;
vector<int> d;
vector<vector<int>> g;
void bfs(int s) {
d = vector<int>(n, INF);
d[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (d[to] == INF) {
d[to] = d[v] + 1;
q.push(to);
}
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
for (int tc = 0; tc < t; ++tc){
cin >> n >> m;
g = vector<vector<int>>(n);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
bfs(0);
vector<int> even, odd;
for (int i = 0; i < n; ++i) {
if (d[i] & 1) odd.push_back(i);
else even.push_back(i);
}
if (even.size() < odd.size()) {
cout << even.size() << endl;
for (auto v : even) cout << v + 1 << " ";
} else {
cout << odd.size() << endl;
for (auto v : odd) cout << v + 1 << " ";
}
cout << endl;
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution**

```
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long li;
const li INF64 = li(1e18);
const int N = 200043;
vector<int> cards[N][4];
li dp[N][10];
int n;
li dp2[4][2];
int main()
{
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
for(int i = 0; i < N; i++)
for(int j = 0; j < 10; j++)
dp[i][j] = -INF64;
dp[0][0] = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
int k;
scanf("%d", &k);
for (int j = 0; j < k; j++)
{
int c, d;
scanf("%d %d", &c, &d);
cards[i][c].push_back(d);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 1; j <= 3; j++)
{
int s = (j == 1 ? 3 : 1);
sort(cards[i][j].begin(), cards[i][j].end());
reverse(cards[i][j].begin(), cards[i][j].end());
while (cards[i][j].size() > s)
cards[i][j].pop_back();
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 4; j++)
for (int k = 0; k < 2; k++)
dp2[j][k] = -INF64;
dp2[0][0] = 0;
vector<pair<int, int> > cur;
for (int j = 1; j <= 3; j++)
for (auto x : cards[i][j])
cur.push_back(make_pair(j, x));
sort(cur.begin(), cur.end());
do
{
int mana = 3;
li score = 0;
li mx = 0;
int cnt = 0;
for (auto x : cur)
{
cnt++;
if (mana < x.first)
break;
mana -= x.first;
mx = max(mx, li(x.second));
score += x.second;
dp2[cnt][0] = max(dp2[cnt][0], score);
dp2[cnt][1] = max(dp2[cnt][1], score + mx);
}
} while (next_permutation(cur.begin(), cur.end()));
for(int j = 0; j < 10; j++)
for (int k = 0; k <= 3; k++)
{
int nxt = (j + k) % 10;
int f = (j + k >= 10 ? 1 : 0);
dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + dp2[k][f]);
}
}
li ans = 0;
for (int i = 0; i <= 9; i++)
ans = max(ans, dp[n][i]);
printf("%lld\n", ans);
return 0;
}
```

Problem E was little tricky, learned a lot. Thanks a lot for great contest!!

can u explain problem E? I haven't understood the tutorial. thanks in advance!!

Maintain a adjacency list, and then arrange the vertices by number of other vertices it is connected to(v[current_vertex].size) in a multiset or priority_queue (descending order). Pop to the priority_queue and mark the vertex as visited and push it in ans_vector. Iterate all the vertices to which it is connected as also mark them true but dont put these vertices in ans. (Because you need to maintain different colour). Do this until all vertices are visited.

Ex: For a tree with 3 vertices and 2 edge: 1-2 and 2-3. Vertex 2 will have max size(2), push it in ans_vector and also mark 1,2 and 3 as true.

Now you have an answer vector. If the size if less than equal n/2 print it otherwise print those which not not in ans_vector . This is because the set of vertices which are in ans_vector and which aren't both satisfies the condition of given problem (expect for size one)

My submission: https://codeforces.com/contest/1176/submission/55381513 Though i was not able to do it in contest.

thanks!!

If someone is trying this approach, try this case. You will understand why pure greedy approach won't work.

1

9 8

1 3

2 3

3 4

4 5

4 6

9 7

4 9

9 8

Thats why we have to use either the found set or compliment of it.

Thanks for your testcase. I thought greedy was possible but I was wrong.

Thanks a lot for this test case. I was thinking greedy will work

What do you exactly mean by greedy here, I just ran a dfs on the graph starting with coloring 1 with 0, its uncolored neighbors with 1 and so on, got ac link , then printing each all colored 0 or1 based on their size

Am i missing something,

I meant to say that I was thinking greedy will work, but actually it won't work. And by greedy, I mean select the edge with maximum number of edges.

hey, I tried the same method as yours but the time taken by your code is much less than mine. I even modified my code to match yours but still, it's much slower can you help me to figure out why it's much slower than yours

please explain the condition when the ans.size() > n/2 if i understood it correctly you want the answer to be all the other remaining vertices. Why is it so?

This is because the vertices not present in ans vector will also satisfy the given problem statement.

Consider coloring the vector in answer vector by color 1 and rest by color 2. Now reverse the colors. You can better understand by drawing some examples.

thanks for help.

please tell why i am getting a TLE on test 2, when i am using a priority queue. PS: the solution is not correct but i just want to know why TLE,it should give a WA

https://codeforces.com/contest/1176/submission/67014259 my solution

Can you elaborate this

If the size if less than equal n/2 print it otherwise print those which not not in ans_vector .with a test case. Since we are sorting in descending order why there is a need to do so?https://codeforces.com/blog/entry/67530?#comment-517334

Thanks

For the future readers. Here it's not necessary to select nodes with highest priority based on their cardinality since we don't have to optimize the number of selected nodes. Here is my solution. my java solution

Alternately, you can try the approach given in tutorial.

Use BFS. Since BFS transverses the graph layer-wise, you can 'color' the alternate layers with color 0 and 1.

Ex:For a tree with 3 vertices and 2 edge: 1-2 and 2-3. Color vertices 1 and 3 with color 0 and 2 with color 1. You would get two answers, the vertices those on even layers and the other on odd. Print the one with minimum size.

This is a more cool approach :)

thanks for the explanation.very clear

Anyone having solution of E using DSU? or give some idea?

DSU is giving TLE in Python , In fact every approach is giving TLE in python 3

Check this 68882087 if you're interested.

"you can just simulate the process, performing actions from third to first."__why in that order ?

Every time you perform operations 2 and 3, you multiply the number with 2 or 4. Therefore, each application of 2 and 3 will make the number divisible by 2, thus forcing you to perform operation 1. If you perform 3 and 2 first until you cannot anymore, then the only possible operation you need to perform is 1.

Of course, you can perform the operations in any order you want (eg. 1, 3, 2, 1, 2, etc) as long as you can still perform one.

why 3*cnt5 not 4*cnt5 in problem A? please answer.

for each power of 5 you have to do:

apply once operation 3 (/5, * 4)

apply twice operation 1 (divide twice by 2 since you multiplied with 4 before)

so 3 operations

thanks

How would you do problem C with DP and binary search? Thanks!

anyone, please explain the problem D in Graph (dfs and similar) approach. Thanks

https://codeforces.com/contest/1176/submission/68009898 I have done it using graphs. If you are further interested in knowing the method ask :)

yes i am interested plz tell

How to solve problem F with DP ?? Thanks!

Won't the solution to the problem D have a worst time complexity of O(n^2) ?

55473892

I guess my submission is clear it has some comments if you did not get the idea I can explain it a little bit more here

Can someone please explain problem F I am not able to understand the editorial solution. Thanks in advance.

is the graph is bipartite?

Not necessarily

could you give an example where it is not bipartite ?

C: https://codeforces.com/contest/1176/submission/55357411 (no dp/binarySearch solution)

B: https://codeforces.com/contest/1176/submission/55350519 (with stacks)

Hello. I'm interested. Do someone implement some algorithms and data structures from scratch during competition or they have been implemented? I mean sieve, for example, in task D.

in my opinion,one should be familiar with sieve through practice so that one can easily implement it within a minute during contest.

why 3*cnt5 not 4*cnt5 in problem A? please answer.

you see. Here's three steps to execute: 1.perform the third operation: n = n * 4 / 5 2.perform the first operation: n = n / 2 3.perform the first operation: n = n / 2 after theses three steps the result you got is the n you type divided by 5. so it's 3 * cnt5.

thanks

Can anybody explain me problem F, the problem say that

"you choose the cards and the exact order they are played", I think that if we have 3 cards 1, 2 ,3, we have to choose card 1, 2 and 3, not 3, 2 ,1 or 1, 3, 2, ... But I read that the solution has sorted the array and chosen maximum if we can, I think in some case, it will wrong, because we have neglected that we have to choose the cards in order they are played. Sorry about bad englishHey! can someone please tell me what is wrong with my code? http://codeforces.com/contest/1176/submission/55369953

Can someone tell me why this python code is giving WA while its c++ version is giving correct result: PROBLEM A: ~~~~~ Your code here... t = int(input()) while (t > 0): t = t — 1 n = int(input()) count = 0 while (n % 5 == 0): count = count + 1 n = 4 * n / 5 while (n % 3 == 0): count = count + 1 n = 2 * n / 3 while (n % 2 == 0): count = count + 1 n = n / 2 if (n == 1): print(count) else: print("-1") n = 0 ~~~~~

link: https://codeforces.com/contest/1176/submission/55432686

Can anyone tell me why it is not accepting for problem E [](https://codeforces.com/contest/1176/submission/55372927)

@MikeMirzayanov Can you please tell me why this approach for problem E fails?

Basically I am greedily selecting vertices if none of their neighbours have been selected. At the end ,if the selected set has more than ceil(n/2) vertices then i print the complementary set

I feel this should work because one of the sets ie the original or the complementary set should have size less than or equal to ceil(n/2) and no two vertices in the original set have edges between them , so they are connected to some vertex in the complementary set (since the graph is connected) . So the complementary set is also a possible answer.

I just now realized the mistake in my code. I should have checked for the floor(n/2) instead of ceil of n/2. Thanks anyways

why 5 4 3 is not a valid answer for D for below test case-- 3 3 5 2 3 2 4

In problem statement, "if a[i] is a prime number, then one integer p[a[i]] is appended to array b" if a[i]=5 and here 5 is prime number so 5th no. prime number is 11 which must appended in array b.But 11 is not in given array b that's why 5 4 3 is not a valid answer.

yeah got it thanks

For E,I tried "Graph coloring" with G and R such that neighbouring nodes have different colors,through BFS,now count the number of Green and Red,which ever is less than n/2,print that.

PROBLEM CCAN SOMEBODY TELL ME WHY I M GETTING TIME OUT IN #TC 9.Ii know m algo is not efficient but i m not able to get editorial pls helpmy solution is 55554895 55554895It has been quite long but still Have you figured out the solution?

Can someone please explain Problem D in detial.

Ok I'm a noob, I absolutely suck, and I can't program for my life. Can someone explain problem B in detail to me -_- sorry about it

Look, when we divide a number by 3, the only possible remainders are 0, 1, and 2.

Now consider an array:

`(3, 4, 7, 1, 1, 2, 4, 11, 12)`

For this array, let

cnt[0]denote total numbers which give remainder 0 when divided by 3, similarlycnt[1]for remainder 1 andcnt[2]for remainder 2.So,

cnt[0]= 2,cnt[1]= 5,cnt[2]= 2Now the idea is to add all the numbers which have remainder 1 & 2, so that when they are added the new element is divisible by 3. Since there are only 2 elements with remainder 2 (4 and 11) in this array, we add these to 2 elements with remainder 1 (say, 4 and 7).

New array is: (3,

6,18, 1, 1, 4, 12)Now,

cnt[0]= 4,cnt[1]= 3,cnt[2]= 0After this operation the number of elements that are divisible by 3 in this array (cnt[0]) has increased. For the remaining elements (cnt[1]), we add these together. because 1 + 1 + 1 = 3.

Finally the array becomes:

`(3, 6, 18, 6, 12)`

which has the max number of elements divisible by 3thnx bro great explaination

Tell me if u don't get it somewhere I will try to explain more.

This makes sense to me now. Thank you so much.

(Maybe my English is poor)

My idea is similar to the tutorial. This codedoes not exceed O(n), isn't it? But it really timed out. Why is this?

I mean E.

what is wrong in this solution of problem D( Recover it!)?

hey i have a WA on same test as u had. Can u tell me what was the problem? or what was that tricky test?

EDIT: i figured out np

For Problem E, apparently just finding a bipartite coloring of the graph will suffice. That is what I did and got AC. My submission (in java) is here: https://codeforces.com/contest/1176/submission/58155189

why my solution is giving a TLE. Help Please https://codeforces.com/contest/1176/submission/67014259

Problem E can be easily done by colouring nodes red and blue (like in biparite graph) and then print all the nodes with minimum count of colors (**red** if count of red nodes < count of blue nodes) .

Can someone explain problem C? I can't understand the editorial.

iterate over the array

we can use the current element e.g. we can use a 23 only if we have an exisiting sequence upto 16.

so, when we get a 23, decrement 23's count and increment 16's count.

the answers is n — (6*cnt[42]) as these are the only valid subsequences

https://codeforces.com/contest/1176/submission/92309951

i found my mistake

1176E — Cover it

Could anybody explain why I am getting TLE my solution https://codeforces.com/contest/1176/submission/92457008

Then there is this solution by a friend of mine and he is getting TLE on case 15. Why? https://codeforces.com/contest/1176/submission/56036460