Codeforces Round #806 (Div. 4) Editorial

#	User	Rating
1	Benq	3783
2	jiangly	3666
3	tourist	3611
4	Um_nik	3536
5	inaFSTream	3477
6	fantasy	3468
7	maroonrk	3464
8	QAQAutoMaton	3428
9	ecnerwala	3427
10	Ormlis	3396

#	User	Contrib.
1	Um_nik	185
2	adamant	178
3	awoo	177
4	nor	169
5	maroonrk	165
6	-is-this-fft-	164
7	antontrygubO_o	153
8	ko_osaga	151
9	dario2994	150
10	SecondThread	149

Thanks for participating!

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	string s;
	cin >> s;
	if (s[0] != 'y' && s[0] != 'Y') {cout << "NO\n";}
	else if (s[1] != 'e' && s[1] != 'E') {cout << "NO\n";}
	else if (s[2] != 's' && s[2] != 'S') {cout << "NO\n";}
	else {cout << "YES\n";}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1703B - ICPC Balloons

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	bool vis[26] = {};
	int res = 0;
	for (char c : s) {
		if (!vis[c - 'A']) {res += 2; vis[c - 'A'] = true;}
		else {res++;}
	}
	cout << res << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1703C - Cypher

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++)
    {
        int b;
        cin >> b;
        if(b == 0)
        {
            continue;
        }
        string now;
        cin >> now;
        for(int j = 0; j < b; j++)
        {
            if(now[j] == 'U'){a[i]--;}
            else if(now[j] == 'D'){a[i]++;}
            if(a[i] < 0){a[i]+=10;}
            if(a[i] > 9){a[i]-=10;}
        }
    }
    for(int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
 
int main(){
    int t;
    cin>> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

1703D - Double Strings

Idea: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	string s[n];
	map<string, bool> mp;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		mp[s[i]] = true;
	}
	for (int i = 0; i < n; i++) {
		bool ok = false;
		for (int j = 1; j < s[i].length(); j++) {
			string pref = s[i].substr(0, j), suff = s[i].substr(j, s[i].length() - j);
			if (mp[pref] && mp[suff]) {ok = true;}	
		}
		cout << ok;
	}
	cout << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1703E - Mirror Grid

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
    int a[n][n];
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            char c;
            cin >> c;
            a[i][j] = c-'0';
        }
    }
    int ans = 0;
    for(int i = 0; i < (n+1)/2; i++)
    {
        for(int j = 0; j < n/2; j++)
        {
            int nowi = i, nowj = j;
            int oldnowj = nowj;
            int sum = a[nowi][nowj];
            nowj = n-nowi-1;
            nowi = oldnowj;
            sum+=a[nowi][nowj];
            oldnowj = nowj;
            nowj = n-nowi-1;
            nowi = oldnowj;
            sum+=a[nowi][nowj];
            oldnowj = nowj;
            nowj = n-nowi-1;
            nowi = oldnowj;
            sum+=a[nowi][nowj];
            ans+=min(sum, 4-sum);
        }
    }
    cout << ans << endl;
}
 
int main(){
    int t;
    cin>> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

1703F - Yet Another Problem About Pairs Satisfying an Inequality

Idea: flamestorm

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAX = 200007;
const int MOD = 1000000007;
 
void solve() {
	int n;
	cin >> n;
	int a[n + 1];
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	long long res = 0;
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		if (a[i] >= i) {continue;}
		res += (long long)(lower_bound(v.begin(), v.end(), a[i]) - v.begin());
		v.push_back(i);
	}
	cout << res << '\n';
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
	// solve();
}

1703G - Good Key, Bad Key

Idea: mesanu

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    long long ans = 0;
    long long sum = 0;
    for(int i = -1; i < n; i++)
    {
        long long now = sum;
        for(int j = i+1; j < min(n, i+32); j++)
        {
            int copy = a[j];
            copy>>=j-i;
            now+=copy;
        }
        ans = max(ans, now);
        if(i+1 != n)
        {
            sum+=a[i+1]-k;
        }
    }
    cout << ans << endl;
}
 
int main(){
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; /* UserName SeniorLikeToCode [Abhishek Gupta (AKGEC 3rd year)]; */ #define int long long #define endl '\n' void solve() { int n, k; cin >> n >> k; vector<int> a(n); for (auto &i : a) cin >> i; int dp[n + 1][40], ans = 0; memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) { dp[i + 1][0] = dp[i][0] + a[i] - k; for (int d = 0; d <= min(32ll, i + 1) ; d++) { dp[i + 1][d + 1] = max(dp[i][d + 1] + (a[i] >> (d + 1)) - k, dp[i][d] + (a[i] >> (d + 1))); } } for (int i = 1; i <= n; i++) for (int d = 0; d <= 33; d++) { ans = max(ans, dp[i][d]); } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); int test = 1; cin >> test; while (test--) solve(); }

int ans = 0; for(int i = n - 1; i >= 0; i--) { // We check for an element only when the element itself follows the v[i] < i rule // AND // Only when its index is in our range 1 to n-1 (skipped 0 because there are no elements before it) // THEN // we find how many elements are before the index equal to i since there is strict inequality if (i + 1 > v[i] && v[i] > 1) ans += cnt[v[i] - 1]; }

#include<bits/stdc++.h> using namespace std; #define ll long long int char check_string(ll k,vector<string> &v){ if(v[k].size() == 1) return '0'; for(ll i=0;i<v.size();i++){ if(i == k) continue; for(ll j=0;j<v.size();j++){ if(j == k) continue; if(v[i]+v[j] == v[k]) return '1'; } } return '0'; } int main(){ ll t; cin>>t; while(t--){ ll n; cin>>n; vector<string> v(n); for(ll i=0;i<n;i++){ cin>>v[i]; } string s; for(ll i=0;i<n;i++){ s += check_string(i,v); } cout<<s<<endl; } return 0; }

t = int(input()) for _ in range(t): n, k = map(int, input().split()) *arr, = map(int, input().split()) MAX_HALF_CNT, NINF = 1, -2**63 max_coins = max(arr) while max_coins >> MAX_HALF_CNT: MAX_HALF_CNT += 1 MAX_HALF_CNT += 1 dp = [[NINF] * MAX_HALF_CNT for _ in range(n)] # dp[i][half_cnt] 打开第i个抽屉后所能得到的最大硬币数，其中使用了half_cnt次坏钥匙， dp[0][0] = arr[0] - k # 用好钥匙，减k dp[0][1] = (arr[0] >> 1) # 用坏钥匙，减半 # print(dp) for i in range(n-1): for h in range(MAX_HALF_CNT): dp[i+1][h] = max(dp[i+1][h], dp[i][h] + (arr[i+1] >> h) - k) if h + 1 < MAX_HALF_CNT: dp[i+1][h+1] = max(dp[i+1][h+1], dp[i][h] + (arr[i+1] >> (h + 1))) else: # 啥都没了 dp[i+1][h] = max(dp[i+1][h], dp[i][h] + 0) print(max(dp[n-1]))

#include<bits/stdc++.h> using namespace std; vector<vector<long long>> dp; long long rec(vector<long long>& arr, long long k, long long factor, long long i){ if(i>=arr.size()) return 0; if(dp[i][factor]!=-1) return dp[i][factor]; long long temp=-k+arr[i]/pow(2, factor)+rec(arr, k, factor, i+1); long long t=arr[i]/pow(2, factor+1)+rec(arr, k, factor+1, i+1); if(temp>t) return dp[i][factor]=temp; return dp[i][factor]=t; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); long long t; cin>>t; while(t--){ dp.clear(); long long n, k; cin>>n>>k; vector<long long> arr(n); for(long long i=0;i<n;i++) cin>>arr[i]; dp.resize(n+1, vector<long long>(n+2, -1)); cout<<rec(arr, k, 0, 0)<<endl; } }

#include <bits/stdc++.h> using namespace std; long long arr[32]; long long rec(long long i,long long n,long long p,vector<long long> v,long long k,vector<vector<long long>>& dp){ if(i==n || p>30) return 0; if(dp[i][p]!=-1) return dp[i][p]; int x = v[i]/arr[p]; return dp[i][p] = max(x-k+rec(i+1,n,p,v,k,dp),x/2+rec(i+1,n,p+1,v,k,dp)); } int main() { long long t;cin >> t; arr[0] = 1; for(long long i=1;i<32;i++) arr[i] = 2*arr[i-1]; while(t--){ long long n,a,ans=0,k; cin >> n >> k; vector<long long> v(n,0); vector<vector<long long>> dp(n,vector<long long>(32,-1)); for(long long i=0;i<n;i++) cin >> v[i]; cout << rec(0,n,0,v,k,dp) << endl; } return 0; }

# include <bits/stdc++.h> #define ll long long #define re register #define il inline using namespace std; string s[100010]; int main() { int t; scanf("%d", &t); while (t--) { int n; bool f = 0; scanf("%d", &n); set <string> str; for (int i = 1; i <= n; ++i) { cin >> s[i]; str.insert(s[i]); } for (int i = 1; i <= n; ++i) { f = 0; for (int j = 1; j < s[i].size(); ++j) { string a = s[i].substr(0, j), b = s[i].substr(j, s[i].size()); if (str.find(a) != str.end() && str.find(b) != str.end()) { printf("1"); f = 1; break; } } if (f == 0) printf("0"); } printf("\n"); } return 0; }

# include <bits/stdc++.h> #define ll long long #define re register #define il inline using namespace std; char g[110][110]; int f[110][110]; int cnt[5]; int main() { // freopen("output.out", "w", stdout); int t; scanf("%d", &t); while (t--) { int n, ans = 0; scanf("%d", &n); for (int i = 1; i <= n; ++i) { string s; cin >> s; for (int j = 1; j <= n; ++j) g[i][j] = int(s[j - 1] - '0'); } int len = (n + 1) >> 1; for (int i = 1; i <= len; ++i) { int k; if (n % 2) k = len - 1; else k = len; for (int j = 1; j <= k; ++j) { cnt[0] = cnt[1] = 0; int x = n - i + 1, y = n - j + 1; cnt[g[i][j]]++; cnt[g[j][x]]++; cnt[g[y][i]]++; cnt[g[x][y]]++; // printf("%d %d %d %d\n", i, j, cnt[0], cnt[1]); ans += min(4 - cnt[0], cnt[0]); } } printf("%d\n", ans); } return 0; }

#include<iostream> #include<algorithm> using namespace std; #define ll long long #define endl '\n' const int N=1e5+10; int T,n; ll dp[N][31],b[N]; void solve(){ ll maxx=0,t=0,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=n;i++) for(int j=0;j<=30;j++) dp[i][j]=-1e9; for(int i=1;i<=n;i++){//第i个 dp[i][0]=dp[i-1][0]+b[i]-k; for(int j=1;j<=30;j++){//用了j此bad if(i>=j)dp[i][j]=max(dp[i-1][j]+(b[i]>>(j))-k,dp[i-1][j-1]+(b[i]>>j)); else break; if(j==30) dp[i][j]=max(dp[i][j],dp[i-1][30]);//无代价从上层转移 } } ll ans=0; for(int j=0;j<=30;j++) ans=max(ans,dp[n][j]); cout<<ans<<endl; } int main(){ int T=1; cin>>T; while(T--){ solve(); } return 0; }

Comments (171)

Write comment?

poituk

11 months ago, # |

Quickly

→ Reply

SeniorLikeToCode

6 months ago, # ^ |

most satisfying G solution : state : dp[i][j] means at ith element we use exactly j bad keys. trans : either we have to use bad key at ith place or it already been use before.

dark_ethics

5 months ago, # ^ |

Can u please explain , that why u have taken ans as the maximum of all elements in the dp array ? shouldn't we just take maximum of dp[n][j] for all j from 0 to 33? because we have to open all the chests ( so n in place of i) .

Dr.DRUNKESTEIN

Hey I would like to request a clarification: why do you report answer as the maximum of dp[i][j] over all values of i and j? should it not be just maximum value of dp[n][j] over all values of j?

hasika

4 months ago, # ^ |

I also want to ask this question，did you get the answer?

HideBeyondYou

Thanks for fast tutorial

__xQc__

Amazing contest !! ..E is tricky one!

goku20001

11 months ago, # ^ |

It was exactly the same as rotating a 2d array using two for loops on leetcode.

yao789as

放屁

Black_Fate

That's why I Aced F instead of E.

ButterChickenn

Yeah, I just used the same logic(leetcode 90 degree rotation) to create all four rotated configurations of the matrix and then checked min moves to make any cell equal in all four configurations.

Snapper_001

E is full implementation based

peti1234

← Rev. 2 →

+60

F is solvable with prefix sums in $$$O(n)$$$.

For each $$$i$$$ count the number of elements, where $$$j \leq i$$$ and $$$a_j<j$$$ ($$$pref_i$$$). And for each $$$i$$$ where $$$a_i<i$$$ just add $$$pref_{a_i-1}$$$ to the answer.

Here is my solution 163953789.

primeprogrammer2021

+10

You beat me by 1 second, gonna say the same thing.

akash_musky

← Rev. 6 →

-33

163923034

CoolKid_19

can you please explain a bit more?

the prefix sum approach isn't really clear to me?

monuk7735

For every element we can store how many element we have encountered before it, that have v[i] < i

int c = 0;
for(int i = 0; i < n; i++)
{
    cnt[i] = c;
    // 1 Based Indexing
    c += (i + 1 > v[i]);
}

Now for every element we can find whether we have it's value in range and whether we can find element so that we can satisfy the 2nd part in the condition i.e. i < v[j], other conditions are already satisfied

My Submission

guptaaman200229

10 months ago, # ^ |

woww great idea understood completely

sky_light

the number of pairs $$$i != j $$$ of n elements is $$$C_{n}^{2}=\frac{n(n-1)}{2}=\sum_{i = 1}^{n-1}i $$$

so you can keep a prefix sum of number elements that satisfied the condition $$$i>a_i$$$

Can you plz tell me why your code is giving correct ans for the case when a[i]-1 becomes -1. Beacause that should give a garbage value

My bad, thanks for noticing. Probably it is $$$0$$$ in this case.

Now the code is correct.

__HACKER__

i've solved it Using ordered Multiset:

after Getting a value which is lesser than its index just check how many values are present in the set which is lesser than this...

and after this just insert the index of the value ( not the value! to satisfy ""ai<i<aj<j this"" )

Hamroz_JONN

-10

Can G be solved by DP ?

suraj10

Yes I solved G using DP. I used the fact that applying the bad operation 30 times would make all elements 0 since log(1e9) is approximately 30.

Here's my solution: https://codeforces.com/contest/1703/submission/163933460

Munnoo

Yes, I made a Recursion + Memoization solution, using similar concept. Check it here : Recursive Solution

mdvorak

Just wanted to comment the exact same thing. My solution

minh20cm

:))

BrxDeputat

I will say that it was a good contest. Thanks for the quick tutorial

ProgramMastergg

I'll just say it. This contest is the best for me .

Venturo

D and F are good problems.

Silverbridge

Hey! Can anyone clarify why my solution is showing TLE on Test Case 10 (Problem D), my approach is similar as that mentioned in the Editorial. Thanks! 163871330

hydroshiba

Your problem lies here I suppose:

Spoiler

if(flag || mark[v[i]]){
         ans=ans+'1';
         mark[v[i]]=1;
        }
        else{
         ans = ans+'0';
         mark[v[i]]=0;
       }

When you wrote ans = ans + '1' what the code did was calculate ans + '1' then assign that resulted string to ans, which made this operation $$$O(N)$$$. Use ans += '1' next time.

Bonus: Here's your very same code accepted with those changes.

Thanks!

YesPy

You just need to speed up the I/O. Just add this line (before defining t int your main funtion). ios::sync_with_stdio(false);cin.tie(nullptr); After that, tabulate the code correctly and you'll get AC.

No it didn't

Fast IO does not solve every problem.

But your tabulation is not correct.

chromate00

But who asked.

Bryce3D

I think problem F can be done in O(n) time.

As mentioned, we only need to consider indices i such that a_i < i. Call such indices "good". We can make a prefix array such that the ith element is the number of good indices less than or equal to i.

Now consider all possible pairs (i,j) that work for a fixed good index j. The number of possible values for i is the number of good indices less than a_j, which is stored within the prefix array. The answer can then be found by summing across all good indices j.

The prefix array can be created in 1 pass, so that takes O(n) time. The summing across all good indices can also be done in 1 pass, so this is O(n) time again.

Code for this can be found in my submission

Edit: Apparently got sniped lmao

I specifically excluded it in the if condition to handle that bug if a[i] < i+1 and a[i] > 0:

divyansh_sahu

Had a similar idea but instead of using a prefix array, for all indices i where a_i<i, I wanted to count all the indices j ahead of i where a_j<j. This however, would not work for cases where a_j<=a_i.
Then i left the question thinking i needed to know segment trees etc to solve it in O(nlogn) :(
Solved it after the contest using prefix array though.

some_randomguy

i have done the same. What do you mean by "sniped" ?

Someone else said a similar thing while I was typing my message

B_Consistent

Anyone could tell me what's wrong with this approach?

abhi_ram

Problem G was a good one.

white_devil_403

Yes

quater_nion

For the problem D we can use unordered_set<string> cache to store the strings. Then for each string, bruteforrce divide the strings in two and check whether both of these strings exist in the cache or not. Simple

to be honest though, you should be very cautious on using hash-based data structures in codeforces. Some people are masters of hacking and can easily find hundreds, even thousands of hash collisions.

Thats true... I think one way we can avoid is by making 2 or three hashes differently and storing in each of them. That way the chance of getting same hashes reduces significantly

Royal_Drax

-15

This code of mine for question D(double strings) is giving TLE on test 3 and I don't know why. Please help me where is the problem?

Lanceloia

Your solution is $$$O(n^2)$$$.

QingFy

use markdown correctly plz

kaisellin

Can F be solved by Fenwick tree??

Yes. 163916062

← Rev. 3 →

any solution which can count pairs where $$$i < a_j$$$ where $$$a_i < i, a_j < j$$$ in all $$$i$$$ and $$$j$$$ is a valid solution. therefore Segment Trees and Fenwick Trees are valid solutions, so are prefix sums.

Tirthsuthar

Yes. I have done it using segment tree. here is my solution 163925757

Honestly, F was too easy with Segment Trees (or Fenwick Trees, those two have identical purposes). I think any person with some experience of common segment tree problems would easily solve it.

Platanito_Frito

BS enters the room*

Prefix Sum enters next and slap both on the face*

MuheshKumar

it can be easily solved with pbds with a few lines of code

tgp07

yes, very easy code.

+14

Let's see in the hacking phase if people learned to use the map instead of the unordered_map. beethoven97 I summon you!

pranav_63

why this solution 163935126 giving TLE ? Anybody please help

wackyIndian

because memset function fills the DP using its size --> O(N), here it is N = 1e5 so your dp gets filled for all test cases which can be upto 1e4, so ~1e9 operations per second are performed.

use this

for(int i = 0;i <= n; i++){
   for(int j = 0;j < 32; j++){
      dp[i][j] = -1;
   }
}

Thank you

you are initializing the dp array in each test case. There can be up to 1e4 test cases. Even if n is 1 in all test cases, you're initializing an array of size 3e6 in each test case. In the worst case, you'll be doing 3e10 operations which is way out of the problem constraints. To avoid this, you can declare a dynamic array(vector) and resize it in each test case according to the value of n. Because we're guaranteed that the sum of n across all test cases doesn't exceed 1e5

Thank you.

DoomsDay861

You can try something like this.163938289

another_love

Thanks for this amazing contest and fast tutorial.

LakshaySodhi29

why my dp solution doesn't work for G https://codeforces.com/contest/1703/submission/163929073

lotusblume

For the testcase:

1
32 100
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

your code gives a negative answer. The dp needs to be able to go from dp[i-1][31] to dp[i][31] without decreasing it by k.

Oh thats the problem...Thnx

people_plus_plus

Here is a little trick. We know, that answer always $$$0$$$ or bigger (because we can just open chests for free). That means answer is not only $$$max(dp[n][i]) \; for \; all \; i < 32$$$, but $$$max(dp[i][j]) \; for \; all \; i < n \; all \; j < 32$$$

TISHAD07

thank you

tezk

Thank you for the very good contest, all the problems are enjoyable

I learn some new thing from problem G

dr.bae

This was the first contest I attempted. I really liked the problems even though I couldn't solve them. Thanks for all the effort. :D

AMERMH123

I've gained four ideas from issues I thank those who wrote those for issues and I hope that the contests div4 will increase in future

Sidharth_71

can somebody explain probelm E again , what if

1 0 0 1

1 0 0 1 , if this is the test case , does it have zero movies required?

The number of rows and columns should be equal in this problem. So your testcase is invalid.

sorry just consider this one

glitchsin

4 moves are required. U have to make either top 2 zeroes and bottom 2 zeroes to one or u can either make left two ones and right two ones to zero.

Amer_Mahfudh

Amazing contest , I've gained four ideas from issues I thank those who wrote those for issues and I hope that the contests div4 will increase in future

HNOONa

i tried to solve F with multiset (c++) along with lower_bound, distance methods here: link

but i get TLE, why?

filippodigra

distance has O(N) complexity for set e multiset (N is the size of the set)

is there a way around this to get O(1) distance operation?

distance has O(1) complexity only with random access data structures such as vectors. check the complexity section: https://m.cplusplus.com/reference/iterator/distance/

ok thanks

never doing that again

Tanish69

I implemented it using 2 sets. Check my submission.

https://ideone.com/diXeOD (My code) Problem F using Ordered Set. Simple Code.. Hope it will help!

okay, so order_of_key is like lower_bound? without iterator part?

alonemanlivewith20cats

"the number of items in a set that are strictly smaller than our item". you can see here https://codeforces.com/blog/entry/11080

ok got it, thanks everyone

It returns how many values are strictly lesser than this in order of log(n) time

Milsu

So amazing

lemon_fresh

Can anyone tell why using vector in this solution for problem E gives wrong answer? Replacing vector with plain array makes it accepted. Submission link

sumitprajapati

Look at the case when x = 0, you are accessing sum[x-1] or sum[-1]

You're right. I guess it was luck that it got accepted with c array.

tushar_kumar

someone hacked my D (163901816) can anyone provide me test case ?

adityagamer

Wait for system testing

Literally_Me

ans = ans + '1' makes copy of ans then adds '1' you should use ans += '1'

Why 163895211 is giving TLE?

← Rev. 4 →

DP solution for G. Lang: PyPy3-64 ____________________________________________________________________________________

second_saturday

The idea for solving Problem F was very nice

AC_zjb

Could help me G problem?i use dp to slove it ,but i cant fine my problem.thank u very much

problem G

TAT...my english is poor ,but i try to share my idea

j:the number of good key

pw(2,x)=2**x

when we open the i th box ,if we use j good keys so we use (i-j) bad keys.but pw(2,33)>1e9,so i think the number of good key is lower than 33.

if the number of bad key is upper than 33,we can see it as 1e14.

so when we open some box,if we use good keys ,we got a[i]/(pw[(i-j)] -m cost

and we use bad keys ,we got a[i]/(pw[(i-j)] -m

so DP[i][j] is mean open i boxes use j good keys.

Dp[i][j]=Dp[i-1][j]+ bad keys or DP[i][j]=DP[i-1][j-1] + good keys

so whats wrong with me TAT

Ssarpa

Suppose that n and k are very large And the optimal operations are always use bad keys. In this case obviously we use more than 32 bad keys but your solution don't considers this and gives the wrong answer.

To fix it : for calculating answer iterate over all dp values and get maximum instead of only dp[n — 1] (because if we do this we consider above case):

for(int i = 0; i < n; i++)
   for(int j = 0; j < 32; j++)
       ans = max(ans, dp[i][j]);

My submission : 163915709

4e1s3n8e7g

I am getting TLE on second TC, can you ples help LINK

Thanks.

i think you need let done be 31

thank u ,i know

pr7nce

Can anyone help me find why I'm getting TLE on 5th case and how to further optimize this code?

link There you go, Its working now

I changed your dp size n , 32 and early pruning in base case

Thanks a lot man.

Dasher001

For which test case it fails.. My solution

Big_Soul

For first 30 minutes i think in E we need to make matrix by add 1. Later i eays accepted this Problem

Hey! Can someone please clarify why my Dp solution for Problem G is showing TLE on Test Case 3? Thanks!
163941930

altforminuscontribution

G is quite hard, other problems are great. Hope the rating will change soon so well-perform participants could get to the next rank!

rakshitsahu20

I did a,b,c,d,e,f with 0 wrong submission can i expect pupil ... Now

MiracleFFT

Thanks for the fast editorial

AVdovin

Another F approach. We can create p where p[i] = (a[i] < i), after that create a prefix sum on that array and iterate over a and do the following:

check if p[i] = 1, otherwise continue

check if a[i] >= 2, otherwise continue

add prefsum[a[i] — 1] to the answer

So why do we need a[i] >= 2 statement? If a[i] < 2, then there is no way to satisfy this inequality. a[i] >= 0, i >= 1, therefore a[i] < i < 1 < j can't be satisfied. Check out my implementation if you are interested 164005949. What do you think about this one?

P.S Well, just find out some guy already told about the same approach...

dhaw92

Simple recursive DP solution for G here.

ivan100sic

map<string, bool>? Why not just use a set<string>?

MoSalah10

Can anyone help to reduce time complexity of G

Nidz05

Can someone tell me why this dp solution is getting WA, doesn't make any sense to me? https://codeforces.com/contest/1703/submission/163945776

epsilon_573

You also have to update your answer while calculating dp so as to counter cases when you use more than 30 bad moves. One such example will be, 60 chests containing 2 coins and lets say k = 1e9.

You are saying that i have to take the max of the whole matrix?

Not really the whole matrix, max of $$$dp[i][30]$$$ over all chests $$$i$$$ + your current logic will be sufficient.

Okay thanks, i fixed it

not max { dp[n][i] },try max{ dp[i][j]} because maybe after dp[i][j] all cost of box if 0.so maybe this i is not n.

Video Solutions of complete problemset.

Yousef_Sameh

When is the result?

ishu_rc

did ur rating update? i am newbie but rating not updated

No , i am waiting

lis05

F can be solved in linear time. submission

maddler

What is the rating range for problems F and G?

hey my rating is not updated even I am a newbie and gave 8-9 rated contests before

nonrice

Ratings did not seem to update. Anyone else having this problem?

Yes... Not updated

Just checked again. Ratings are updated now.

RahulAhuja2901

Can anyone please tell why am I getting Memory Limit Exceeded in Problem E? I am just using a 2D Array. Link to my submission :- https://codeforces.com/contest/1703/submission/163908463

zhaoxi_zheng

Hello sir, There are two layers of recurrence in your code, so your code's time complexity is $$$O(n^2)$$$, and when $$$n = 200000$$$,you will get TLE.

I solved this problem with set, and my time complexity is $$$o(n \log n)$$$.

This is my code:

Although there are two lawers of recurrence in my code, but $$$s[i].size \le 8$$$, so my code doesn't go TLE.

Hey, Thanks for the reply but I am asking about Problem E, Mirror Grid. The solution that you have explained is Problem D, Double Strings.

Sorry, it's my mistake. Let me show you my code of problem E.

vitosevski

You are creating new 2D array every test case.

Thank you so much for replying. Can you tell what should be approach for this problem?

To be honest I didn't solve this problem and now I don't have time now because the contest starts in 2 minutes.

To fix your problem (MLE) you can create 2D array before first test case. (before while (t > 0) line)

Because in the editorial they are also creating a 2D array for each test case.

Then I don't know. Maybe I was wrong.

np_incomplete

Loved the round! Wish I could solve G. Thanks to the setters and testers.

I solved F in O(n) Here is my solution: 163897273

jcnp

Why also use map<string, bool> mp in D,but i Time limit exceeded.

utku_1234

i did question f in O(n logn) but still it is showing me TLE in one test case can anyone help me out please .... i would be grateful my sol 164096201

NafisAlam

you have to pass the vector by reference in the find_pos function

reneger

C no Problem is quite interesting! in my opinion

v7fgg

Good solution for problem G!

ajblahblah

For question good keys bad keys why is recursion + memo wrong

my submission 164141664

figured out the solution. made a silly mistake. Ignore the above comment

I did the same recursion + memo. check here: Recursion+Memo

Note that, in problem G, don't use memset all the times, or you will get TLE on test 2 (I had tried it), because memset has a time complexity as $$$O(n \times \log a_i)$$$, if $$$t$$$ is very big, the total time complexity will be too large to solve this problem.

I hope that this note will help you!

lol_py

I am getting runtime error in G. Please help me out. Here is my submission

Can someone suggest more problems similar to G?(like DP states like this)

antsparrow5

good round

A7med_Nageh

good

Arthur_Weng

10 months ago, # |

Good Tutorial!

rigvedinho

Can someone please explain to me what is wrong with my solution for F or provide a counter example? I probably messed up my binary search implementation but cannot figure it out. https://codeforces.com/contest/1703/submission/165016289

anyone please tell me my mistake in problem G 165412847

sheikhfoysal

Call a pair good if it satisfies the condition. Let's split the inequality into three parts: ai<i, i<aj, aj<j.

Note that if ai≥i for any i, then it can't be an element of a good pair, because it fails the first and third conditions.

my question is: how does it fail the third condition?

I intuitively got the solution for G but was unable to prove it. The proof in the editorial is great!

vk20july

https://codeforces.com/contest/1703/submission/165888535

I solved the question Double strings using a map but I still didn't get how the time complexity is O(l*nlogn) According to my code time complexity would be

logn->to insert elements in map

n->outer loop l->maximum length of input string l->substr(inbuiltfunction) Total TC->logn+n*(l*l)->(l^2)*(n)

6iza

9 months ago, # |

lol, D is copy of https://acmp.ru/?main=task&id_task=87

Cassifa

4 months ago, # |

DP solution for G 191342440

rahmanfaisal516

7 weeks ago, # |

nectarl

7 days ago, # |

In G, reason why we have to iterate over all dp array instead of only go through dp[n][0-32] is that during the transferation of dp array, once the second dimension hit the boundary, we would lose one stratey, which is using the bad key. Because we were supposed to do dp[i][33]=dp[i-1][33-1]+a[i]>>32(or 33?im not sure), but the boundary force us to only do dp[i][32]=dp[i-1][31]+a[i]>>32(?)-k, which is using the good key, taking all the cost painfully. so u see how the bad key strategy is lost during the process, besides iterating all dp array, we can also do dp[i][j]=dp[i-1][j-1] when a[i]>>j==0.

flamestorm's blog