in the problem Permutation Cycle

why is it sufficient to break into cycles of lengths $$$A$$$ and $$$B$$$ ?

i mean — how can we be sure that the only way is when $$$A*X+B*Y=N$$$ ? why cant there be other overlapping solutions?

is this because its a functional graph? [directed graph in which all vertices have outdegree equal to 1]

can u please provide the intution behind the problem A Leapfrog in the Array

i cudnt understand the editorial

i tried to use KAHN algorithm but use set instead of queue...this doesnt work — why?

i got what you meant

thanks!!

EDIT: i figured out np

i found my mistake

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.me/contest/1176/submission/92309951

there is a better solution to this which i couldnt understand so i did a straightword solution which gave me AC.

i have a pbds — which contains all elements of current window — now i can get the median of the currennt window in log(n)

now 2 FWTs I used for —

1) count of certain element

2) sum

so for e.g. if i have a window 2 2 3, fwt1[2] = 2 and fwt1[3] = 1 and fwt2[2] = 4 and fwt2[3] = 3

now all i need is for each window is — elements above it, sum of elements above it, elements below it, sum of elements below it.

since number range is large i used cordinate compression.

look at the 7 lines i marked in my code and hopefully you will understand more

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define sz 200100
typedef tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> pbds;
ll sm[sz];
ll cnt[sz];
void upd(ll idx, ll tr[], ll add)
{
	while (idx < sz)
	{
		tr[idx] += add;
		idx += (idx & (-idx));
	}
}
ll que(ll idx, ll tr[])
{
	ll sum = 0;
	while (idx)
	{
		sum += tr[idx];
		idx -= (idx & (-idx));
	}
	return sum;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n, k, idx, mid, cntlow, cnthigh, sumlow, sumhigh, low, high;
	cin >> n >> k;
	vector<ll>a(n), b(n);
	pbds s;
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b.begin(), b.end());
	for (ll i = 0; i < k; i++)
	{
		idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
		upd(idx, sm, a[i]);
		upd(idx, cnt, 1);
		s.insert({a[i], i});
	}
	for (ll i = k; i < n; i++)
	{
		mid = (*s.find_by_order(k / 2)).first;
		idx = lower_bound(b.begin(), b.end(), mid) - b.begin() + 1;
		
                // look at the next 7 lines everything will be clear
                cntlow = que(idx - 1, cnt);
		sumlow = que(idx - 1, sm);
		cnthigh = que(n + 1, cnt) - que(idx, cnt);
		sumhigh = que(n + 1, sm) - que(idx, sm);
		high = sumhigh - (cnthigh * mid);
		low = (cntlow * mid) - sumlow;
		cout << low + high << " ";
 
		idx = lower_bound(b.begin(), b.end(), a[i - k]) - b.begin() + 1;
		upd(idx, sm, -a[i - k]);
		upd(idx, cnt, -1);
		s.erase({a[i - k], i - k});
 
		idx = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
		upd(idx, sm, a[i]);
		upd(idx, cnt, 1);
		s.insert({a[i], i});
	}
 
	mid = (*s.find_by_order(k / 2)).first;
	idx = lower_bound(b.begin(), b.end(), mid) - b.begin() + 1;
	cntlow = que(idx - 1, cnt);
	sumlow = que(idx - 1, sm);
	cnthigh = que(n + 1, cnt) - que(idx, cnt);
	sumhigh = que(n + 1, sm) - que(idx, sm);
	high = sumhigh - (cnthigh * mid);
	low = (cntlow * mid) - sumlow;
	cout << low + high << endl;
 
	return 0;
}

can we do this question using KMP?

thanks!!

i was using 31 and got WA on one testcase but when i switched to 131 like you i got AC

can u please explain what do u use as a standard when doing rolling hash questions like this?

can you please verify if i understood moving robots correctly —

for each robot we first get what is the probability for it to be on some i, j cell after k iterations.

then for each cell what is the probability that it was empty after k iterns? — probability that robot 1 isnt there * probability that robot 2 isnt there and so on.... so we multiply the 1 — dp[i1][j1]

now expectation — sum(P(xi)*xi) we calculated P(xi) and xi is 1?

please correct me if i am wrong — we are trying to make failure links for the nodes just like LPS array of KMP..

also — how can i solve https://cses.fi/problemset/task/1731 using the same algorithm?

i tried using the above hash function for this quesn — https://www.codechef.com/LRNDSA10/problems/MATTEG

but i still get TLE

my solution — https://www.codechef.com/submit/complete/37329776

what am i doing wrong?

i tried the approach you said in earlier questions and still got > 10 downvtes and no answers...**i ultimately delete the entry** and get answers to my questions 1 in 20 times..

in fact in an earlier blog i received the exact opposite review i.e. post the question and not the link

also, its a codechef question as i said and if you google the title the first link will be the question

thanks a lot though!

DISCLAIMER:

1. i usually dont reply on such topics (because i am a below average student myself and have a lot to learn) but ill make an exception this time.

2. at_kansal happens to be a good friend of mine and i cleared goldman sachs he is talking about.

3. i am by no means arguing and just want to share my experience.

Q. Why do companies judge on ds algo and why not webdev etc?

=> because a much more important job for a student is to have the ability to program. frameworks etc can be easily learnt.

e.g. i tried to learn javascript when i wasnt good at programming and left it after 4-5 days of trying. i found callbacks, promises etc quite tough to understand. however, when i did a bit of practice of ds algo etc, and got back to learning javascript, i also could appreciate the concepts much more.

Q. Why cp then?

=> CP IS IMPORTANT — but its objective is much much more than interviews — it gives you the ability to think — a stable expert / candidate master can easily ace interviews but for someone below that, a better option might be practicing on interviewbit and leetcode if he / she has less time. reaching the level as i mentioned above takes time for an average student. you have given 3 dedicated years to reach where you are. its commendable effort some people just cannot...because of a lot of constraints...

Q. If not CP then what?

=> i happened to practice interviewbit twice and also did quite a few problems on gfg and leetcode and still i found the interview questions very very easy. i cant solve greedy problems of C on codeforces but i could answer as well as code dp questions in interview — why? because they ask easy questions or better STANDARD QUESTIONS.

e.g. give me problem of binary search i cant solve — give me painter partition problem — i will solve it.

CONCLUSION:

someone above average at CP can easily crack interviews. but if you arent and you realise you dont have enough time, its always better to rethink. also, i can guarantee one thing — im not talking about companies like google maybe but for most of the other companies — there is a 95% probability that what you are asked is a direct question picked from leetcode / interviewbit (interviewbit is just a subset of leetcode).

oh i was treating Warnsdorf's rule as an optimisation too

The optimization you made of returning 0 when reaching vertex n, actually reduces the runtime by more than half and does the trick.

This is something i encountered the third time in cses problem set (there maybe more i am yet to do all)

knights tour

grid paths

all these questions use some kind of wierd optimisation which i cant see mathematically how they affect the runtime but after that optimisation they get AC.

my approach worked — though i did top down dp

i made one optimisation — if i reach vertex n before rest of the vertices are visited i return 0

maybe topdown works because unlike bottom up all states arent calculated in top down?

i dont really know a lot though i will include my accepted code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
vector<int>adj[22];
ll dp[1100000][22];
int n;
ll F(int mask, int i)
{
    mask = mask ^ (1 << i);
    if (mask == 0 && i == n - 1)
        return 1;
    if (i == n - 1)
        return 0;
    if (dp[mask][i] != - 1)
        return dp[mask][i];
    dp[mask][i] = 0;
    for (auto j : adj[i])
    {
        if ((mask & (1 << j)))
            dp[mask][i] = (dp[mask][i] + F(mask, j)) % MOD;
    }
    return dp[mask][i];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int m; cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b; cin >> a >> b; a--; b--;
        adj[a].push_back(b);
    }
    memset(dp, -1, sizeof(dp));
    cout << F((1 << n) - 1, 0);
    return 0;
}

THANKS!!!

thanks!

MZuenni i dont think meet in the middle would work. Can you prove me wrong please? I assume you are saying

• we store all pairwise sums

• sort the vector

then we try meet in the middle for the new vector(say new_v) formed.

why it wont work — suppose my one pointer is at s and another pointer is at e. Suppose new_v[s] + new_v[e] = required_sum BUT new_v[s] and new_v[e] have an element which is common to both e.g. new_v[s] was formed by a[5] + a[6] and new_v[e] was formed by a[5] + a[8]

now what do you think is optimal? incrementing s or decrementing e? (i think neither). as it might happen new_v[s] + new_v[e - 1] was a possible answer. so can new_v[s + 1] + new_v[e]

I may be wrong and i would really appreciate it if you could clarify this.

i understood the optimisations, but can you explain the runtime mathematically? the explanations there looks more experimental.

please ignore

sorry i thought you meant that there are only four 2*2s in one 4*4 because that is what the video editorial says as well

i can prove by code https://ideone.com/oaaysP

this prints all 4*4s such that all 2*2s inside of it have odd number of 1s in it

also, none of the 4*4s i printed have an odd number of ones

can u please explain why?

no...i think its beacuse chessboard case is included in both (no two same colored adjacent cells)

nvm i got it

my dp solution for B1 using 2 states — https://codeforces.me/contest/1384/submission/88165283

I want to verify time complexity — I think it should be n * k as for every index k times are possible i.e. earliest you could reach is i + 1 and latest you could reach is i + k

McDic in your code when u check if m edges are present or not, you iterate over two groups at a time

the complexity of that part is ab + ac + bc where a, b, c are the sizes of the vertex sets

why is this complexity not O(n^2) and not giving TLE?

my AC code

my solution for D

i just tried coloring the graph

let parent color = 1, cur node color = 2

• if there is an edge between [parent of cur node] and [child of cur node] => color child of cur node 3

• if there isnt an edge between [parent of cur node] and [child of cur node] => color child of cur node 1

just like bipartite graph + ensuring all the edges exist

nvm thats to ensure its complete

is this a usual way to code or something?

like after taking examples i understood why your code works

but did u think of this approach? how this performs on an array like 1 2 3 16 25 36 (say k = 5) is very interesting(for me)...

please ignore

YES ABSOLUTELY!! my final code that got accepted...

https://ideone.com/hKsG5K

i did the same thing as above but i added a trick — depth of a node in a cycle can be either the depth or if b is part of a cycle its depth can be depth[b] — cyclelength

thanks a lot!! i could never have done this question without you!!

Namnamseo i tried but i am still getting WA on only 1 testcase but its very huge so i cannot understand

approach: i first assign depth to nodes by randomly assigning any one node of the cycle as 1 then doing depth[node] = depth[child[node]] + 1

then by building a binary lifting table i jump

this will work because as you pointed out in functional graph, there is only one path i.e. a length 4 path from some node x has only one possible ending node

now depending on difference of depth of nodes i jump and if i reach the node i print the depth difference else print -1

special case here is that if two nodes are of the same cycle then depth[a] < depth[b] might be possible

in that case , i print the length of the cycle — depth[b] + depth[a]

my code: https://ideone.com/pi9Cx3

any help will be appreciated thanks!!!

• we want to 'resolve' all triplets such that there is an edge from L to R and there is no edge from L to M such that L < M < R.

• since its an undirected graph, every vertex in a component is reachable from each other.

• this means 'no such triplet can exist whithin a component'.

• in given testcase components are [1,2,5,7] [3,4,6,8] [9] [10] [11,12] [13] [14]

• paths which should be there but dont exist 'after visiting first component' => 1-3 1-4 1-6 2-3 2-4 2-6 5-6

• when dfs from 1 is over, we see for 3 that already a vertex greater than 3 could be visited by a vertex smaller than it.

• so we add an edge. adding an edge between any two components makes them into one component. Now see point three. So adding an edge between [1,2,5,7] and [3,4,6,8] removes all issues in point 5.

• now the claim is for every i you will have to add only one edge. why? suppose two vertices x and y exist such that x < y < i. now, if x could reach a point > i and y too could reach a point > i.

• Then, we would already have added an edge between y and x. so, x and y are already one component and adding one edge will be sufficient for i.

nvm i understood

i dont get your quesn..can u explain further? e.g. a = 2 b = 1 a is not the ancestor of b though b isnt on the cycle

thanks for the crystal clear explanation i absolutely understood everything!

implementing this is definitely going to be a little tough but ill try then get back

Edit: https://codeforces.me/blog/entry/79518 this is an attempt to writing the editorial

for the graph section of cses but its incomplete... if u have time can u finish this off? it

would be of great help!!

CAN SOMEONE PLEASE HELP ME???

for Investigation question above, i am doing exactly what the author does except for one thing:

he uses a visited array and if already visited, continues..

i do something like

pair = pq.top();
if(pair.first > distance[pair.second])
     continue;

i want to know constraint / testcase wise why this will give TLE. it was giving tle for 3 large testcases

the issue was resolved on introducing a boolean visited array

mycode = https://ideone.com/e6ZTWL (not needed tho)

nvm got it

pls ignore i got it

how can i ever learn to think like this?

nvm got it

nvm got it

ViciousCoder can you please clear a bit more..

i was thinking of doing +1 on a range of tin[lca] to tout[lca] and -1 on tin[a] to tout[a] and tin[b] to tout[b]

but clearly this is not covering all cases..

can you please specify the segments you would carry out the operation on?

(i understood what needs to be done without seg trees but i am looking for a soln with seg tree)

mycode without seg tree: https://ideone.com/1NJn9n

pefect!! can you please help me in one more thing?

https://codeforces.me/contest/1385/submission/87155344

i had precalculated the count...

isnt my solution O(n)?

i am still having difficulty for understanding complexity of prob D depth of recursion is log n

there are n possibilities if i am not wrong

e.g. aaaabbcd aaaabbdc aaaacdbb aaaadcbb the rest four with aaaa at the end... like we try all n possiblities but doesn the editorial do an additional step of counting at each step?

before loop totcnt[2] = 3 forwdcnt[2] = 0

totcnt[1] = 4 forwdcnt[1] = 0

after loop begins

i   totcnt  forwdcnt

1   1: 3    1: 1
  
    2: 3    2: 0

2   1: 3    1: 1
    
    2: 2    2: 1

and so on

fenwik tree gives me sum from 0 to R if i query on R i.e. prefix sum

forwdcnt stores

=>count of elements from 1 to i

=>that have been seen upto i

totcnt will store

=>initially count for all elements in the entire array

=>then as we iterate through the array we decrement the totcnt

e.g. if my array is 1 1 1

intitally forwdcnt[1] = 0 and totcnt[1] = 3

after i = 1: forwdcnt[1] = 1 and totcnt[1] = 2

after i = 2: forwrdcnt[1] = 2 and totcnt[1] = 1

and so on

https://codeforces.me/contest/459/submission/85599666 i think the code is easy and try tracing an example throught this code maybe??

        for (int i = 1; i <= n; ++i)
	{
		f.update(totcnt[a[i]], -1);
		totcnt[a[i]]--;
		forwdcnt[a[i]]++;
		ans += f.query(forwdcnt[a[i]] - 1);
	}

do u undertsand this part? i realised this part can explain more than my stupid english

i think i am late but still... split function's work is to convert a string for e.g. hhelllo to h 2, e 1, l 3, o 1 now if u obtain this equivalent for both strings you can easily check if at each index, the alphabet is same and count for string t >= count of string s for that alphabet

please correct me if im wrong

let numbers = 2e5

let all be 2e5

they contribute to log(2e5) arrays

so log(2e5) numbers have 2e5 numbers in their array

total = log(2e5) * 2e5 = z

worst case O(zlog(z)) i.e. sorting all of them

zlog(z) + klog(2e5)

i did it by FWT just asking why this didnt work :)

could you identify the error?

i had encountered a similar problem on using PBDS but there memory constraints were given less clearly there it was 28 MB https://codeforces.me/contest/1354/problem/D here though that isnt the problem...

i can try problem basically translates to finding all pairs such that

1) i < j 2) number of a[i] from 1 to i > number of a[j] from j to n

let count[a[i]] — count of a[i] from 1 to i

for all i we will add to fenwick tree count[a[i]]

now we will again iterate from beginning and keep on removing count[a[i]]

what does my fenwick tree have at any i?

for each "value" number of times that "value" can be obtained "value" is the count of some element from i + 1 to n

now a simple query of count[a[i]] — 1 shall give me how many js are there such that count[a[j]] from i + 1 to n is lesser than count[a[i]] from 1 to i

https://codeforces.me/contest/459/submission/85599666

in your code why are you checking for the dsu merge as well?

while(l < r && dsu.merge(l, r — 1, tr))

once we get the length from where we cn start merging i.e. L + len and R — len are in same component dont we just merge till they meet?

thanks!(i couldnt understand it though)

happened to me during contest today :( i wont give it now

feodorv i dont think so cc is the value in left tree cnt is value i need if left can give me what i want, i go towards left anyways will it pass upto case 10 with such a blunder? thanks for ur help!!

lmn0x4F can u please help me in COT?? i am getting seg fault on testcase 10/11 for my submission my code click here i have increased the size significantly too as people were saying in the comments there...

i implemented what Noureldin and bhishma are talking about but i am getting TLE. here is my code what i did found totient[i] — n loglogn compute ans[i] — that too is n loglogn

Auto comment: topic has been updated by Shameek (previous revision, new revision, compare).

Can someone pls explain the solution to aerodynamic? I couldnt quite get it asto why a figurewith central symmetry would be an ans.