№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Thank you for participating!

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	string s;
	cin >> s;
	int a = 0, b = 0;
	for (char c : s) {
		if (c == 'A') {a++;}
		else {b++;}
	}	
	cout << (a > b ? 'A' : 'B') << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1926B - Vlad and Shapes

Idea: mesanu

Tutorial

Solution

 #include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    vector<string> g;
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        g.push_back(s);
    }
    bool triangle = false;
    for(int i = 0; i < n; i++)
    {
        int cnt = 0;
        for(int j = 0; j < n; j++)
        {
            if(g[i][j] == '1')
            {
                cnt++;
            }
        }
        if(cnt == 1)
        {
            triangle = true;
        }
        else if(cnt > 1)
        {
            break;
        }
    }
    reverse(g.begin(), g.end());
    for(int i = 0; i < n; i++)
    {
        int cnt = 0;
        for(int j = 0; j < n; j++)
        {
            if(g[i][j] == '1')
            {
                cnt++;
            }
        }
        if(cnt == 1)
        {
            triangle = true;
        }
        else if(cnt > 1)
        {
            break;
        }
    }
    if(triangle)
    {
        cout << "TRIANGLE" << endl;
    }
    else
    {
        cout << "SQUARE" << endl;
    }
}
 
int32_t main(){
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}

1926C - Vlad and a Sum of Sum of Digits

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
int res[MAX];
 
int S(int x) {
	int res = 0;
	while (x) {
		res += (x % 10);
		x /= 10;
	}
	return res;
}
 
void solve() {
	int x;
	cin >> x;
	cout << res[x] << '\n';
}
 
int main() {
	res[0] = 0;
	for (int i = 1; i < MAX; i++) {
		res[i] = res[i - 1] + S(i);
	}
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1926D - Vlad and Division

Idea: mesanu

Tutorial

Solution

#include "bits/stdc++.h"
using namespace std;
 
void solve() {
    int n; cin >> n;
    map<int, int> cnt;
    int ans = 0;
    for(int i = 0, x; i < n; ++i) {
        cin >> x;
        if(!cnt[x]) ++ans, ++cnt[((1 << 31) - 1) ^ x];
        else --cnt[x];
    }
    cout << ans << "\n";
}   
 
main() {
    int t = 1; cin >> t;
    while(t--) {
        solve();
    }
}

1926E - Vlad and an Odd Ordering

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
void solve() {
	int n, k;
	cin >> n >> k;
	vector<int> v;
	while (n) {
		v.push_back((n + 1) / 2);
		n /= 2;
	}
	int tot = 0, pow2 = 1;
	for (int x : v) {
		if (tot < k && k <= tot + x) {
			cout << pow2 * (2 * (k - tot) - 1) << '\n';
			return;
		}
		tot += x;
		pow2 *= 2;
	}
}
 
int main() {
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1926F - Vlad and Avoiding X

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200'007;
const int MOD = 1'000'000'007;
 
vector<pair<int, int>> odd, even;
 
bool valid(int gc[7][7], bool odd) {
	for (int r = 1; r < 6; r++) {
		for (int c = 1; c < 6; c++) {
			if (gc[r][c] && ((r + c) % 2 == odd)) {
				if (gc[r - 1][c - 1] && gc[r - 1][c + 1] && gc[r + 1][c - 1] && gc[r + 1][c + 1]) {
					return false;
				}
			}
		}
	}
	return true;
}
 
bool check(int g[7][7], int flips_left, int idx, vector<pair<int, int>>& vec, int valid_val) {
    if (flips_left == 0) {
        return valid(g, valid_val);
    }
    if (idx == vec.size()) {
        return false;
    }
    bool ok = false;
    ok |= check(g, flips_left, idx + 1, vec, valid_val);
    g[vec[idx].first][vec[idx].second] ^= 1;
    ok |= check(g, flips_left - 1, idx + 1, vec, valid_val);
    g[vec[idx].first][vec[idx].second] ^= 1;
    return ok;
}
 
void solve() {
    int g[7][7];
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            char c;
            cin >> c;
            g[i][j] = (c == 'B');
        }
    }   
    int res = 0;
    for (int i = 0; i <= 4; i++) {
        if (check(g, i, 0, odd, 1)) {res += i; break;}
    }
    for (int i = 0; i <= 4; i++) {
        if (check(g, i, 0, even, 0)) {res += i; break;}
    }
    cout << res << '\n';
}
int main() {
	
	for (int i = 0; i < 7; i++) {
		for (int j = 0; j < 7; j++) {
			if ((i + j) % 2) {
				odd.emplace_back(i, j);
			}
			else {
				even.emplace_back(i, j);
			}
		}
	}
	
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
}

1926G - Vlad and Trouble at MIT

Idea: mesanu

Tutorial

Solution coded by Dominater069, thanks!

Solution

 #include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
 
int n;
const int N = 1e5 + 69;
int dp[N][3];
string s; 
vector <int> adj[N];
 
void dfs(int u){
    // dp[u][0] = nothing open 
    // dp[u][1] = P open 
    // dp[u][2] = S open 
    
    dp[u][0] = INF;
    if (s[u] != 'S') dp[u][1] = 0;
    else dp[u][1] = INF;
    if (s[u] != 'P') dp[u][2] = 0;
    else dp[u][2] = INF;
    int tot = 0;
    
    for (int v : adj[u]){
        dfs(v);
        dp[u][1] = dp[u][1] + min({dp[v][1], dp[v][2] + 1, dp[v][0]});
        dp[u][2] = dp[u][2] + min({dp[v][2], dp[v][1] + 1, dp[v][0]});
        tot += dp[v][0];
    }
    
    if (s[u] != 'C') tot = INF;
    
    dp[u][0] = min({tot, dp[u][1] + 1, dp[u][2] + 1});
    
    //cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << "\n";
}
 
void Solve() 
{
    cin >> n;
    for (int i = 1; i <= n; i++) adj[i].clear();
    for (int i = 2; i <= n; i++){
        int x; cin >> x;
        adj[x].push_back(i);
    }
    
    cin >> s; s = "0" + s;
    
    dfs(1);
    
    cout << min({dp[1][0], dp[1][1], dp[1][2]}) << "\n";
}
 
int32_t main() 
{
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    return 0;
}

Комментарии (139)

Написать комментарий?

MisterReaper

9 месяцев назад, # |

+74

For Problem-F, I have a bitmask dp solution: 247350477

→ Ответить

kgb_70

9 месяцев назад, # ^ |

+15

I am interested to know how you formed intitution for bitmask dp when it looks like a graph based problem at first.

← Rev. 3 →

+20

Firstly, I thought if we precalculate answers for all matrixes at the beginning, then we can solve queries in $$$O(n^2)$$$ which equals reading matrix.

But how can we precalculate answers for all matrixes. Like in the editorial, we can separate matrix into 2 sets; which one of them has 25 elements, other's 24. How can we calculate answers for all matrix designs in one set.

And then I reduced problem to a bitmask DP problem. And I found a classicial DP solution:

Try to show possible matrixes as a masks, which black square is 1, else 0. Then $$$f(mask)$$$ will show answer for $$$mask$$$.

We have 2 easy cases:

It is a good matrix (every black square doesn't have 4 diagonal black square) and $$$f(mask) = 0$$$: We can check it in $$$O(bit \ number \ of \ mask)$$$.
It isn't a good matrix, and suppose we transform $$$k.$$$ black square to white: $$$f(mask) = \min_{\forall k \in mask} f(mask \otimes 2^k) + 1$$$ And our case will has a same complexity as 1. case.

Then we will have $$$2^{25}$$$ mask for first set, and $$$2^{24}$$$ for second set. And final complexity will be $$$O((2^{25} + 2^{24}) \times 25 + (T \times 49))$$$ or $$$O(2^{\frac{N^2}{2}} \times N/2 + T)$$$. Nearly $$$2 \times 10^9$$$ which is in TL. But it is too close to TL so it can get TLE if your constant is big.

Note: You can fast your solution with magical bitwise operations.

Also sorry for my poor English.

Thunnus

Wow, amazing approach, thanks for sharing. It helped a lot.

Shyren

great solution , can you share any resources from where I can learn it?

PieArmy

Usaco Guide Bitmask DP Tutorial may be helpful.

Thanks

Nemona

+26

I tried hard to solve F using bipartite matching but I failed. Does F can't be solved by bipartite matching? I think it can be solved by find minimum vertex cover with good network modeling. Plz help me.

Leftist_G

← Rev. 2 →

I think F is very difficult to be solved by flow (network modeling).

I tried to find a modeling of minimum cut, but I found that it's difficult to produce by flow that for an illegal black cell, we need only to change one cell's color to make it legal. In other words, for a black cell that is not legal, we need to manipulate at least one other cells to make it legal. The "at least one" operation is difficult for network flows.

But perhaps there is some subtle transformation in this problem that eliminates the "at least" condition. I'm looking forward the subtle way to solve it expectantly.

ABugWithTheBigDream

8 месяцев назад, # ^ |

hey how and where do you practice < I saw you're doing really good on contests.

Any tips !!!

My current level is solved 400+ on leetcode.

Practice as more as possible. CodeForces is not the main OJ on which I solve problem.

Which platform you use for practice and whats the good place to practice ?

The same as many Chinese CPer, I use Luogu mainly. You can wait for the international version of the site to use...

Sus_man

-13

problem f is so bad i cant solve it

ikmyhn

+21

it's hard for div4 I agree

coderdhanraj

If you're looking for an easier bruteforce solution which worked!

Have a look at this

not_ahmed_hamed

There's a much simpler solution for G.

Root the tree.
Do DFS
if your current node $$$u$$$ is P, install a wall between $$$u$$$ and every child node $$$v$$$ that has S. The same goes for S.
if your current node $$$u$$$ is C:
- let $$$cnt_s$$$ be the number of childs have S.
- let $$$cnt_p$$$ be the number of childs have P.
- if $$$cnt_s < cnt_p$$$, add $$$cnt_s$$$ to the answer and change the letter on $$$u$$$ to P (Changing the letter to P means that the parent of $$$u$$$ should never be S since we have some unwalled edges contain P).
- if $$$cnt_s > cnt_p$$$, the opposite of the previous step.
- if $$$cnt_s = cnt_p$$$, It doesn't matter whether we should change $$$u$$$ to S or P (We should change it to be the same as the parent) so we left it to be C as it's.

rhymehatch

Well done, I attempted the same DFS traversal, but never thought of changing C to P. What I did instead was to keep a count of P and S during traversal, and set either P or S to 0 once the wall is put. But haven't quite figured out how to make it AC. Although I have the same $$$cnt_s$$$ $$$cnt_p$$$ comparison :D

I did the same and got WA2, but I got lucky and found the bug 3 minutes before the contest ended :D

1528344561

Could you explain why: when $$$cnt_s$$$ = $$$cnt_p$$$,We should change it to be the same as the parent.

I didn't do this, so I got WA2.But I don't understand why we have to do this.

thank you

shufentainanle

you can try this hack 1 1 1 2 2 3 3 CCCPSPS anwser may be 2 or 3

Because if the parent is S and we changed the current node to P, this would take an extra operation.

For example :

6
1 2 2 2 2
SCPPSS

We should change node 2 to S (total cost = 2), but if we change it to P, the total cost will be 3.

Amazing, I also tried same approach but couldn't figure out last condition. This last condition cnts==cntp is what I was missing out and getting WA on test case 2.

Thanks it helped me getting AC. My AC Solution 247695620

Avijit_Biswas

Can you explain if node == c why you gave hasS = 1 and hasP = 1 instead of giving hasS = 0 and hasP = 0?

I didn't do that. They are initially 0, and I change them based on which gives the minimum answer.

    if (s[node] == 'C')
    {
        cnt += min(cs, cp);
        if (cs > cp)
            hasS[node] = 1;
        else if (cs < cp)
            hasP[node] = 1;
    }

Thelearned

Can you attach the submission link ? I tried the same thing although i am getting WA on Test 3

247362381

rishabhxchoudhary

I recorded myself live while solving A,B,C,D,E and thinking G. Hope it helps someone: https://www.youtube.com/watch?v=Zr2JbyTwq0A

idkao

Bro why you did it in live stream?

The stream was private during the contest. After the contest, I made it public. idk why there are so many downvotes. Many YouTube creators upload codeforces screencasts.

Sorry, i thought it was public during contest sorry for misunderstanding

jayy222

By the way why so many downvotes its just private live and made public once the contest is over and do consider checking it out its actually helpful.

avoid

Why this solution get TLE? https://mirror.codeforces.com/contest/1926/submission/247402006 I can't think of a single reason, every operation in loops are constant

I solved it other way: https://mirror.codeforces.com/contest/1926/submission/247402620 But still curious why first one is TLE

blitztage

Because of unordered_map blowing up.
This blog tells more about it.

Goddamn. Thank you.

Mr.Morpheus

Thank you. i had no idea why my ans was getting TLE.

MomenHossam

I wrote this solution which just check each line if it has substring of "010" since k>1 that means a square is at least 2*2

if it has a "010" then it is a triangle else is square

its an easier approach

#include <iostream>
#include <string>
#define ll long long

using namespace std;

int main()
{
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string arr[n];
        for(ll i = 0; i < n; i++) {
            cin >> arr[i];
        }
        bool found = 0;
        for (ll i = 0; i < n; i++) {
            found = arr[i].find("010") != std::string::npos;
            if(found){
                break;
            }
        }
        if (!found) cout << "SQUARE" << endl;
        else cout << "TRIANGLE" << endl;
    }
}

eemo

← Rev. 10 →

+12

I have a bitmask dp solution for problem F.

first assume that B = 1 and W = 0, and change the grid accordingly.

Let's say the bit on cell (i, j) is bad iff grid[i][j] = 1 and grid[i - 1][j - 1] = 1 and grid[i - 1][j + 1] = 1.

With that, let's define dp[i][j][k] to be the minimum number of flips considering the first i lines, the current mask on the i'th line is j, and k is a bitmask saying which bits from j are bad. Clearly, k is a submask of j, since the x'th bit from j can only be bad if grid[i][x] = 1, this is important because now we can iterate on j and k in $$$O(3^N)$$$. Now we need to transition to i + 1. How? simple, just iterate on all possible masks, and check if they are valid.

A mask is valid iff for all x, if x is bad than mask CANNOT have both (x — 1) and (x + 1) BOTH on. otherwise we would have that grid[i - 1][x - 1] = 1 and grid[i - 1][x + 1] = 1 and grid[i + 1][x - 1] = 1 and grid[i + 1][x + 1] = 1, which we cannot have.

With some clever preprocessing of the masks, this dp can be achieved with a complexity of $$$O(N * 2^N * 3^N)$$$, with N = 7 and 200 testcases, this is fast enough

here's my solution

VirnaAilin

I solve problem C without precomputing in O(t*log10(n)).LOL 247319547

Trigbluy

Do you have the math proof of that?? I couldn't understand

Wasif_Shahzad

I was literally trying to formulate a thing like this but failed on it badly and messed up with my rating. going back to grey again :(

amansingh81757

same. I literally wasted 20 minutes trying to find a formula, the 0.5 second bugged me.

KExa

me too,I didn't try to preprocess it

SoluckyBhavya9

Can you explain the mathematical proof behind this?

ANALIA

6 месяцев назад, # ^ |

Can you pls explain your solution? I also tried something similar but couldn't come up with one

jackson.souza

+19

I have a different approach with dp for problem F. First consider the following dp: dp[i][msk1][msk2].
i = current line
msk1 = what is the state of the last line
msk2 = what are the positions that, if we put two black cells in the diagonal in this line will make a X.
The transition for this dp will be: try every mask, see if the mask is possible and, if possible, calculate the cost of the mask.
The complexity of this would be O(7*2^7*2^7*2^7*7), and this is too slow for 200 test cases. But we can formulate the masks with a different way, take a number in base 3.
if the digit at pos j =
0: the pos j at last line was a W.
1: the pos j at last line was a B, and I can put two black cells in the diagonal.
2: the pos j at last line was a B, and I can't put two black cells in the diagonal.
This dp will be O(7*3^7*2^7*7), this will be sufficient for 200 test cases.
https://mirror.codeforces.com/contest/1926/submission/247403810

Cappucher

For problem D, rather than using XOR, I simply added the two numbers and checked to see if they were equal to 2^31 - 1. Here was my submission: 247301401. I then sorted the array and used two pointers. Is the editorial solution superior to mine? If so, why?

It's not superior. You also have a hard time accomplishing it in Python (dict can be TLE hacked). Sorting and 2 pointers is the safest option.

a_gt3_rs

Your solution probably will get better runtime than the editorial if implemented in C++, since the constant factor of map is bigger than traditional sorting.

ashays

The link to G in the tutorial is in russian for some reason.

tickbird

have problem with reading problem statement E. wouldn't all cards with number from 1 to n appears? for example 8, it's clearly not odd, it can't be 2 * (any odd number) number, it can't be 3 * (any odd number), it can't be 4 * (any odd number). 8 never appears, thus constraint on k, n is not valid

0x81

8 * 1

_Kee

The process does not stop at the step 4 -- in the step 8, you will have $$$8 \cdot 1 = 8$$$, because $$$1$$$ is an odd number.

so that was And so on, until all cards are laid down.. part now I can see thank you

cpchenpi

+27

So is there a polynomial solution for F? I tried modeling with network flow but failed, and I think such approach probably won't work.

Misty7

I tried modeling with network flow but failed too lol

vstiff

How can greedy approach ( 247465029 ) result in more deletions that optimal?

upd: think I understood why: it's a knapsack, in case anyone wondering

← Rev. 4 →

Okay, I've got it. Since we know from editorial that at most 4 squares are needed in each parity, we can replace knapsack with 4-sum (1-2-3-sums in fact) with total complexity $$$O(n^3)$$$. Slightly trollish but polynomial

Error_Yuan

+17

Sorry, but this solution is nothing different from the one in the editorial. Your solution requires the fact that "at most 4 squares needed in each parity", however, this won't work for $$$n\ge 8$$$. So I had to say that this is not a true polynomial solution. It's indeed $$$\mathcal{O}(n^{\lfloor \frac{n}{2}\rfloor})$$$.

+16

Indeed, should have checked it before. Thanks for pointing out.

While researching I found that low frequency set can be approximated, maybe that's the intended polynomial solution.

ja_g_an

Can anyone tell me why this is giving tle for E [submission](https://mirror.codeforces.com/contest/1926/submission/247361946)
i did the same as in the editorial but i used binary search to fing no of elements we can take at each step
am i missing something 
i tried to add link for my submission but i'm unabel to do that

code

#include<bits/stdc++.h>
using namespace std;
#define int long long

int f(int i,int n){
    
    int lo=1,hi=1e10;
    int ans=1;
    while(lo <= hi){
        int mid = lo + (hi-lo)/2;
        if(pow(2,i) + (mid - 1)*(pow(2,i+1)) <= n){
            ans=mid;
            lo = mid+1;
        }
        else{
            hi=mid-1;
        }
    }
    return ans;
}

void solve(){
    //find highest power of 2 which is less than n
    int n;cin>>n;
    int k;cin>>k;

    int h_p = log2(n);
    vector<int>v;//no of num we can take with 2^i
    for(int i=1;i<=h_p;i++){
        v.push_back(f(i,n));
        
        
    }
    // for(int i=0;i<h_p;i++){
    //     cout<<v[i]<<" ";
    // }
    // cout<<endl;
    vector<int>takes;
    takes.push_back((n+1)/2);
    for(int i=0;i<h_p;i++){
        takes.push_back(v[i] + takes.back());
    }
    int x=lower_bound(takes.begin(),takes.end(),k)-takes.begin();
    if(x == 0){
        cout<<k*k - (k-1)*(k-1)<<endl;
    }
    else{
        int a=pow(2,x);
        int d=pow(2,x+1);
        int n=k-takes[x-1];
        cout<<a + (n-1)*d<<endl;
    }
    
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

TJUHuangTao

For F,my submission 247420824, why i add the dfs branch (the //add part),the result become worse. For example,

1
BBBWBBB
BBBBBBB
BBBBBBB
BBBBBBB
BBBBBBB
BWBWBBB
BBWBBWB

If I remove the comment symbols in the code and dfs by five cases, I get a result of 7.While following the code inside my link to dfs with three cases gives a result of 6.

Besides , What is the problem with the code inside my link and why can't AC.

Sorry for my poor English, can anyone help me ?

I found the problem, I forgot to add "return" in this place during dfs

if (check(x, y) == 0)
        "return" dfs2(u + 1, cnt);

This can lead to otherwise legal points that I still go to enumerate to modify its diagonal, resulting in a large answer. And the more cases of dfs, the more likely it is to lead to a large answer, which is what led to my question above.

PROELECTRO444

How can I do hash collision on this solution?

from collections import defaultdict

t = lol()[0]
int_max = 2**31-1
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split())
    c = defaultdict(int)
    count = 0
    for e in a:
        if c[int_max ^ e]:
            count += 1
            c[int_max ^ e] -= 1
        else:
            c[e] += 1
    print(count + sum(c.values()))

aryxn5

use custom hash

I want to hack this not prevent it. Like I want understand how hack collision can be performed

You can checkout usaco guide,they have a section about generating hack cases for hack collisions.

Dev77G

Can somebody share the flow networks approach and solution for Problem G. I want to know how maxflow/mincut can find the solution. Thanks in Advance.

+10

I don't get why dp is needed in G. Isn't it simple dfs?

#include <bits/stdc++.h>
using namespace std;
const int int_max = 1e5 + 10;
char s[int_max];
vector<int> children[int_max];
int n;
 
int dfs(int i){
    int sm = 0;
    for (int j = 0; j < children[i].size(); j++){
        sm += dfs(children[i][j]);
    }
    int count_p = 0;
    int count_s = 0;
    for (int j = 0; j < children[i].size(); j++){
        if (s[children[i][j]] == 'P'){
            count_p++;
        }
        else if (s[children[i][j]] == 'S'){
            count_s++;
        }
    }
    if (s[i] == 'P'){
        return sm + count_s;
    }
    else if (s[i] == 'S'){
        return sm + count_p;
    }
    else{
        if (count_p > count_s){
            s[i] = 'P';
            return sm + count_s;
        }
        else if (count_p < count_s){
            s[i] = 'S';
            return sm + count_p;
        }
        else{
            return sm + count_p;
        }
    }
}
 
void solve(){
    cin >> n;
    for (int i = 0; i <= n; i++){
        children[i].clear();
    }
    for (int i = 2; i <= n; i++){
        int e;
        cin >> e;
        children[e].push_back(i);
    }
    for (int i = 1; i <= n; i++){
        cin >> s[i];
    }
    cout << dfs(1) << '\n';
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

soham_c04

I was thinking if we can solve G using min-cut.

Basically my idea was to combine all the 'P' to a node 0 in a new_graph and all the 'S' to a node n+1, which are basically acting as the source and sink respectively, and keeping the configuration of the 'C' vertices constant, which are acting as intermediate nodes. There can be multiple edges.

Then we calculate the max-flow, where each edge has a capacity of 1 which will be our final answer. But using Ford-Fulkerson gives $$$O(nm^2)$$$, thus giving TLE.

Can we use the fact that the capacity of each edge is 1 thus somehow reducing it to linear time ?

decltype_t

https://mirror.codeforces.com/contest/1926/submission/247492595

You need to use faster flow network

Thanks. It got AC using Dinic's algorithm. After you said faster flow network I googled and found out it takes less time for unit capacity $$$O(M√M)$$$.

Sorry, but since I didn't know about it before, I didn't really understand your implementation of it. Did you use the same?

AhemJi

+18

I would like to mention my solution for F.

Observation 1: Grid can be divided into 2 independent sets of cells based on whether (i+j) is odd or even, with 25 and 24 cells in each.

Considering only black cells, we can brute force all possible flips in O(2^25 * 25). But this is slow.

Observation 2: Flipping cells from the grid boundary is not necessarily needed, we will still find an optimal flipping.

This reduces our cell count to 13 and 12. And the brute force is fast enough now.

Code

_Unseen_

Sometimes your genius is just....astonishing.

rustam-cpp

My solution in C was $$$O(N + t)$$$ 247266041. If $$$n \le 10^6$$$ my solution will still work

But it contains precomputation too

A very simple solution for B. find the first instance of 1 in the grid. then check if the next cell is 1 and if the bottom cell is 1. if so then its square otherwise triangle.

dsanurag520

for problem D i got TLE. I believe its o(n) can someone correct

from collections import Counter

for i in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    c = Counter(a)
    count = 0
    for e in a:
        k = 2147483647-e
        if c[k] and c[e]:
            count+=1
            c[e]-=1
            c[k]-=1
    print(n-(count))

Counter behaves similarly to unordered_map in C++. It can be TLE hacked where c[k] or c[e] can be $$$O(n)$$$.

What you can do is a random.shuffle(a) to make the hackers work harder :D

noooo I didnt get hacked. I got TLE in contest itself.

They made the test case that will TLE if you use a dict or a similar hash based data type. They created a "hack" before the hacking phase.

Try adding a import random and random.shuffle(a) and you will see you will get AC (the test case that TLEs python will no longer work).

ohhh thanks for the reply. Any idea why do they do this on purpose? And how do they achieve this exactly

They do this on purpose to make people come up with efficient algorithms that don't rely on hash tables. Of course, in C++ there's ordered map.

For example, try solving:

Subarray Sums I: https://cses.fi/problemset/task/1660

Subarray Sums II: https://cses.fi/problemset/task/1661

You will be surprised :D

Here's a hack tutorial for Python and you can test it out yourself: https://mirror.codeforces.com/blog/entry/98994

You exploit the hash function to create collisions and make any resizing attempts still maintain collisions.

holy hell thanks for the articles

my c++ version also got TLE

#include <iostream>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
 
        unordered_map<int, int> counter;
        vector<int> a(n);
 
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            counter[a[i]]++;
        }
 
        int count = 0;
        for (int i = 0; i < n; ++i) {
            int k = 2147483647 - a[i];
            if (counter[k] > 0 && counter[a[i]] > 0) {
                count++;
                counter[a[i]]--;
                counter[k]--;
            }
        }
 
        cout << n - count << "\n";
    }
 
    return 0;
}

Change unordered_map to map

NovaByte

Could you please explain the reason behind this?

This because unordered_map in c++ has bad implementation

saisumanchitturi

Did you try using Fast IO? Python's Hash table uses Sip Hash. Not exactly similar to CPP's unordered_map but very strong. IMO hash table is not the cause for TLE.

https://mirror.codeforces.com/contest/1926/submission/247314271

Here's slow Python IO passing.

Hmm, this is interesting. I didn't come across such behaviour earlier. New learning for me.

Try this one: https://cses.fi/problemset/task/1661

They have a test case that purposefully TLEs a Python hashmap and if you switch to a $$$O(n \log n)$$$ solution, with same IO, it passes.

louyuxuan

As a nooooooooooob,even I can't solve D and E lol Next I will record the results of each of my races. I believe I can be LGM before 2026!

Tracck

For problem B, I have a solution in which I get the numbers of 1s in the first line the number 1 starts appearing.

If the numbers of 1s in the next line that has 1 is different (for example, line 1 has 3 ones, line 2 has 1 one) then it is a triangle, otherwise it is a square. However this solution doesn't work on test case 2 and I've not been able to find any edgecase in my mind that defies this logic: 247338503

robostac

Your description sounds correct, your code doesn't quite do that.

Thank you, my code didn't check for the case in which there're lines full of 0s below the shape, and it compared 0 number of 1s to the number of expected 1s to make a square (which was already completed) and flagged it as a triangle because these numbers are different.

Thank you for finding the test case!

i_ujjwal

Amazing work setters!! My Java Binary Trie Solution 247338014 with complexity O(30*N) TLEd on System Test which ideally should not. In contest it showed a runtime of 1091 ms , since it had a buffer of almost 1 sec , so i thought it was feasible. And again no surprise exact same code in C++ passes. 247463968 UPD : Got my AC back :)

hatuan09hcm

Why didn't my rating change ( my rating was 381 before the contest ) even though I solved the first three problems ?

Eren__Jaeger

Have patience, it takes some time. Check now.

Alright thanks :)

ASHWANTH_K

how to solve F in polytime?

Invincible24

Why my solution gets TLE for Problem C? 247461107

p4nd4v

This was my first Codeforces contest. Can anyone suggest study materials for dsa.

strglntoexist

Can anyone explain this line of the editorial solution of Problem G:Vlad and Trouble at MIT?

dp[u][0] = min({tot, dp[u][1] + 1, dp[u][2] + 1});

I can not understand it. Please give some explanation.

KasymK

I think this Div4 is harder than previous Div4, because problem F and G was very hard for pupil

abdur_rahman_41

Could you please explain the approach of D ?

pangs

-8

Problem C: Why does it fail on Test #8 ? : Submission

include <bits/stdc++.h>

using namespace std;

int sumDigits(int n) { int sum = 0; while(n > 0) { sum += n%10; n /= 10; }

return sum;

}

void solve(vector v, int n, vector &copy) { map <int, int> mp; int ans = 0; int p = 0; for(int i = 1; i <= n; i++) { if(i == v[p]) { ans += sumDigits(i); mp[i] = ans; p++; continue; } else ans += sumDigits(i); }

for(int i = 0; i < copy.size(); i++) {
    cout << mp[copy[i]] << endl;
}

int main() { ios::sync_with_stdio(0); cin.tie(0);

int t; cin >> t;
int maxN = 0;
vector<int> v;
while(t--) {
    int n;
    cin >> n;
    maxN = max(maxN, n);
    v.push_back(n);
}

vector<int> copy = v;
sort(v.begin(), v.end());
solve(v, maxN, copy);

return 0;

first of all, put your code beetween ` ` next time so its more readable, and I think your code fails on this test case:

I'll leave it to you to figure it out as to why.

Firefrog418

For Problem-F, we just need to check the cells marked as '@' below:

. . . . . . .
. . @ @ @ . .
. @ @ @ @ @ .
. @ @ @ @ @ .
. @ @ @ @ @ .
. . @ @ @ . .
. . . . . . .

For the blue part, we need to check these cells:

. . . . . . .
. . @ . @ . .
. @ . @ . @ .
. . @ . @ . .
. @ . @ . @ .
. . @ . @ . .
. . . . . . .

So we just brute force from 0 to 4095.

For the red part, we need to check these cells:

. . . . . . .
. . . @ . . .
. . @ . @ . .
. @ . @ . @ .
. . @ . @ . .
. . . @ . . .
. . . . . . .

So we just brute force from 0 to 511.

Here is my solution: 247559944.

3400942034

Problem-D,Why does using unordered_map table time out?

GMO_Goat

For problem C I've a O(n) solution which runs in about 15 ms (c++) 247602474

Day_Tao

How to deal with Problem C if n<=1e18. (Chinese student,Englishi is very poor...)

That means how to deal it with a O(t) solution. I think there is a solution which used math.

tbquan08hanoi

I don't sure but i think my solution here is O(log(n)) for each query

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll sumOfDigits(ll n) {
    if (n < 10)
        return n * (n + 1) / 2;

    ll d = log10(n);
    ll *a = new ll[d+1];
    a[0] = 0, a[1] = 45;
    for (ll i = 2; i <= d; i++)
        a[i] = a[i-1] * 10 + 45 * ceil(pow(10, i-1));

    ll p = ceil(pow(10, d));
    ll msd = n / p;

    return msd * a[d] + (msd * (msd - 1) / 2) * p + msd * (1 + n % p) + sumOfDigits(n % p);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t;
    cin >> t;
    while(t--) {
        ll n;
        cin >> n;
        cout << sumOfDigits(n) << "\n";
    }

    return 0;
}

Thanks for your healping.Last night I solve Problem C with a O(log10 n * t) solution.This is my code:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pql priority_queue<int,vector<int>,less<int>>
#define pqg_pii priority_queue<pii,vector<pii>,greater<pii>>
#define pql_pii priority_queue<pii,vector<pii>,less<pii>>
#define scnaf scanf
#define rt register int
#define int long long
int n,T,a[6],x[6],k[6];
string s;
signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>T;
	k[0]=45;
	for(int i=1; i<5; i++)
		k[i]=k[i-1]*10+45*pow(10,i);
	cout<<endl;
	while(T--) {
		cin>>s;
		int ans=0;
		a[0]=a[1]=a[2]=a[3]=a[4]=0;
		x[0]=x[1]=x[2]=x[3]=x[4]=0;
		n=s.size();
		for(int i=0; i<n; ++i)
			a[i]=s[i]-'0';
		for(int i=1; i<n; ++i)
			x[i]=x[i-1]+a[i-1];
		for(int i=0; i<n/2; ++i)
			swap(a[i],a[n-i-1]),swap(x[i],x[n-i-1]);
		if(a[0]!=0)
			ans=(a[0]+1)*a[0]/2+a[0]*x[0];
		for(int i=1; i<n; i++)
				ans+=a[i]*pow(10,i)*x[i]+k[i-1]*a[i]+a[i]+(a[i]-1)*a[i]*pow(10,i)/2;
		cout<<ans<<endl;
	}
	return 0;
}

And it could solve even though n<=10^1000 if t<=1^4

Oh,I'm sorry.The time complexity of my code is $$$O(t \log_{10} n)$$$.

kgkgkgkg

guys just to justify the tags for C, i came up with a digit DP solution.

digit_dp

I wondered if there is a not hard brute-force approach for the problem F

AlphaMale06

I think problem F can further be optimized by considering only the inner 5x5 square (the same idea, just considering less squares for backtrack). This approach should be more than 10x faster.

treasuryonly

I have upsolved problem F based on your idea by just checking the 5x5 square but using bit 1 in the generated binary numbers for painting (the 13 cells and 12 cells in the 5x5 square) rather than DFS.

Haskell submission

tushar_jain_10

For Problem D why my solution is giving TLE

CODE-:

int t;
cin>>t;
while(t--){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin>>v[i];
    }

    int ans = 0;
    unordered_map<int, int> mpp;
    for(int i = 0; i < n; i++){
        if(mpp.count(INT_MAX - v[i])){
            mpp[INT_MAX - v[i]]--;
            if(mpp[INT_MAX - v[i]] == 0)
                mpp.erase(INT_MAX - v[i]);
            ans++;
        }else{
            mpp[v[i]]++;
        }
    }

    for(auto it : mpp){
        ans += (it.second)
    }

    cout<<ans<<endl;
}

adaptatron

I made video editorial for problem G.

Can anyone tell me why this is giving tle for E i did the same as in the editorial but i used binary search to fing no of elements we can take at each step am i missing something

ochaku

For problem d:

for i in range(int(input())): n = int(input()) l = list(map(int,input().split()))

my_dict = {}

for num in l:
    if(num not in my_dict):
        my_dict[num] = 1
    else:
        my_dict[num] += 1

count = 0

for num in l:
    if(my_dict[num]!=0):
        count+=1
        xor_val = ((1<<31)-1)^num
        if(xor_val in my_dict and my_dict[xor_val]!=0):
            my_dict[xor_val]-=1
        my_dict[num]-=1

print(count)

i am getting tle... how can i optimise it??

MD.Atik

I found this solution helpful as a beginner programmer. However, I believe attaching a video solution would greatly benefit learners like me who might need a bit more visual guidance

Impostor_Syndrome

Can anyone give test case for the case 1(no type of water flowing up) in case of Question G: Vlad and Trouble at MIT? I feel that the latter two cases are enough.

peeyush2000

For Problem-C, I have a O(1) time complexity solution: 247367957. O(#digits(n))...better than the one in tutorial?

THEGREATHERMIT

In the problem C, you don't need to use the sum of digits function at all. You can also use dp to find the answer. This removes the logn factor.See my code;

include <stdio.h>

include <stdlib.h>

int main() { int* a = (int*) malloc(sizeof(int) * (2000001)); for (int i = 0; i <= 9; ++i) { a[i] = i; } int c = 1; for (int i = 10; i <= 2000000; i++) { if(i / c == 10) { c = 10; } a[i] = a[i — c] + 1; } int b = (int*) malloc(sizeof(int) * (2000001)); b[0] = 0; for (int i = 1; i <= 2000000; ++i) { b[i] += b[i — 1] + a[i]; } int t; scanf("%d",&t); for (int i = 0; i < t; ++i) { int n; scanf("%d", &n); printf("%d\n", b[n]); } return 0; } If you have any doubt, feel free to ask.https://mirror.codeforces.com/contest/1926/submission/249616774

srirams06

8 месяцев назад, # |

// Could someone try to identify the logic mistake for the B problem? I am just checking if any //row's sum is equal to 1 if yes it is a triangle else square.

int main() { ios_base::sync_with_stdio(false); cin.tie(0);

int t, n, flag, sum;
char c;
cin>>t;
while(t--){
    cin>>n;
    flag = 0;
    for(int i=0; i<n; i++){
        sum = 0;
        for(int j=0; j<n; j++){
            cin>>c;
            if(c=='1')
                sum++;
        }
        if (sum==1){
            flag = 1; 
            cout<<"TRIANGLE"<<"\n";
            break;
        }
    }
    if(!flag) cout<<"SQUARE"<<"\n";
}
return 0;

SpecialOperations0

first you have to take ALL the inputs otherwise inputs of other tests may overlap, second what if there is only one 1 in the whole grid? this is square not triangle!

first you have to take ALL the inputs otherwise inputs of other tests may overlap could you please explain the above statement because I have used break so it shouldn't overlap right. Also, the input grid contains atleast 2*2 sqaure.

my bad, then you just have to take all the inputs, imagine with me that the shape it triangle, so in the first row of this triangle there is only one 1, your code just after getting that whole row prints triangle then break BEFORE you continue to take the coming rows for the triangle so those will go the next testcase

Thanks for the hint. My solution was accepted after I removed the break statement.

Reason: If we use break, it prints "Triangle" but after that it breaks. So instead of getting the "n" it just inputs the next line as "n".

For example, in the below case, it should go and input next "n" and not next line i.e. it inputs n = 1110 instead of n = 2

4 0000 0000 0100 1110 2 11 11

acingcp

For Problem-E, I have written this code but I am not able to understand the problem in my logic , and it gives wrong result for n=10^ and k=10^9. Please help me with this.

int main() { int t; cin >> t; while (t) { long long int n, k, m = 1, j = 0; cin >> n >> k; long long int r = 0; long long int x = 0; x = n / 2 + n % 2; while (1) { if (k <= x) { while (k) { r = m * (2 * j + 1); j++; k--; } break; } else { m = m * 2; k = k — x; x = x / 2 + x % 2; } } cout << r << endl; t--; } return 0; }

CompScientist

For problem C, I guess there is a solution with complexity O(t). I am just a beginner, so I can be mistaken. Someone more experienced can check this. Here is my solution :

include

include<math.h>

int main()

{

ios_base::sync_with_stdio(0);

cin.tie(0);

int t;

cin>>t;

for(int tests=0;tests<t;tests++)

int n;

cin>>n;

int e=n%10;

n/=10;

int d=n%10;

int c=n%10;

int b=n%10;

int a=n%10;

int p=n;

bint res=(e+1)*(a+b+c+d+p+e/2)+(d>0)*d*(5*(d-1)+45+10*(p+a+b+c))+(c>0)*c*(50*(c-1)+100*(a+b+p)+900)+(b>0)*b*(500*(b-1)+1000*(a+p)+13500)+(a>0)*a*(5000*(a-1)+10000*p+180000)+(p>0)*p*(50000*(p-1)+2250000);

if(e%2==1)

{

   res+=(e+1)/2;

}

cout<<res<<endl;

return 0;

DBWGLX

g[vec[idx].first][vec[idx].second] ^= 1;

In the solution of Problem G,this option is only need when g[][] is 1.

Downcake

7 месяцев назад, # |

New to c++ for problem c, can someone please explain why my logic is wrong , couldn't get the subject

#include <iostream>
#include <string>

int main()
{
	int testcase ;
	std::cin >> testcase;
	while (--testcase >= 0)
	{
		int a;
		int b = 0;
		int i = 1;
		std::cin >> a;
		while (a != 0)
		{
			if (i == 10)
				i = 1;
			b += i;
			i++;
			a--;
		}
		std::cout << b << std::endl;
	}
}

Ayu_041

3 месяца назад, # |

why does mysolutionto c shows TLE; i believe i have implemented dp correctly. is bottom up really better that top down approach???

_Priyank

For problem E. What I did is I observed the pattern that it was forming and then I calculated the row in which my no is coming and then i found the position where the no will be and then found out the odd no corresponding to that position and then ans is (oddno*(1<<rowno)),

Блог пользователя mesanu

include <bits/stdc++.h>

include <stdio.h>

include <stdlib.h>

include <bits/stdc++.h>

include <bits/stdc++.h>

include

include<math.h>