Maroof is visiting a new city. Being a Mathematician, he does not like to visit different places but visit places differently. The city has N places to visit. We are given the (X,Y) co-ordinates of the places to visit. Maroof wants to start from a random place i and want to go to a random place j. But he involved a little maths in his procedure. Following are his demands:

He will give a number A. Now, the place i and place j should be such that the line connecting these two points must have the Ath maximum slope (There are total N*(N-1)/2 possible slopes among all the unordered places pairs).

Input arguments to your function:

1. Integer A

2. B : An integer array containing X-coordinates of the places

3. C : An integer array containing Y-coordinates of the places

Note that the length of B (= N) will be equal to the length of C and the ith point is represented by (B[i], C[i]).

Output: An array having exactly 2 elements : numerator and denominator of the slope (fraction should not be further reducible).

Additional instructions:

1. Places can be overlapping (Two places can have same (X,Y) co-ordinates)

2. Overlapping places must not be considered as same places.

3. In case the line joining the places is vertical, slope is -INF.

4. Two overlapping places have slope -INF.

Constraints:

1 <= A <= 70

1 <= N <= 100,000

-10^9 <= B[i], C[i] <= 10^9 (Also X and Y coordinates can only be Integers)

Example:

Input: A = 2

B = [1, 2, 3, 1, 2] //X coordinates of the places

C = [2, 4, 6, 2, 3] //Y coordinates of the places

Output:

ans = [2,1].

Sorted Points = [(1,2), (1,2), (2,4),(2,3),(3,6)]

SortedSlopes: [3, 2, 2, 2, 2, 2, 1 , 1, -INF, -INF]

Output instructions:

1. Output fraction should not be further reducible [e.g. Reduce (6,4) to (3,2) before returning the answer]

2. In case the answer is negative infinity, return (-1,0)

3. In case the answer is zero, return (0,1)

4. In case the answer is negative, numerator must be negative. [e.g.: (-3,2) not (3,-2) ]

Any idea how to solve it in linear or linear log time.

Given an array A of N numbers, you have to perform B operations. In each operation, you have to pick any one of the N elements and add original value(value stored at index before we did any operations) to it's current value. You can choose any of the N elements in each operation.

Perform B operations in such a way that the largest element of the modified array(after B operations) is minimised. Return an integer corresponding to the minimum possible largest element after K operations.

Example:

Input : A = [1, 2, 3, 4] B = 3

Output : 4

Explanation : After the 1st operation the array would change to [2, 2, 3, 4] After the 2nd operation the array would change to [3, 2, 3, 4] After the 3rd operation the array would change to [4, 2, 3, 4]

A : [ 8, 6, 4, 2 ] B : 8 The expected returned value : 12

Thanks : the problem is solved, one more way to solve this problem is to use min heap priority queue with the following comparator

struct op
{
    bool operator()(const pll &a , const pll &b)
    {
        return a.fi + a.se > b.fi + b.se; /// greater than bcoz min and max works reverse in comparator, what i observed till now.
    }
};

We are to find the index of lexographically sorted balanced brakcet sequence.

I was referring to cpalgorithms, but couldn't understood,

while calculate the index number when we get ")" , why we are adding dp[2*n-i-1][depth+1] to our answer. what is the intution behind it.

Someone pls tell >> > Errichto Please help

why no one is replying ?

The problem wrong brackets asks you to find k_th lexographically incorrect bracket sequence.

Editorial uses dynamic programming method dp[i][j] = the number of strings (of length 2N that contain N open brackets and N closed brackets) that are not correct, but their prefix of length i is correct and it contains j more open brackets than closed ones.

but how can bracket sequence be correct when i is of odd length. since i can be odd how to make dp transistions on them. The editorial did almost same for both even and odd length i prefix. i didn't understood it. can someone please explain the approach.

Thanks !

Hello! We are given an integer N, The set [1,2,3,…,N] contains a total of N! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3 ) :

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

For example, given n = 3, k = 4, ans = "231"

if n = 11, k = 1, ans = "1234567891011"

In this case, k will be a positive integer that is less than INT_MAX. n is reasonable enough to make sure the answer does not bloat up a lot.

N can be upto 1000 , k can be upto 1000.

How to solve it, simple backtracking will time out after N>10.

How to solve problem D of abc124. The editorial is in japanese. Can anyone who solved it, share logic!

i m thinking on using 2 pointer.

IN the problem colorful slimes you have to pick all color in minimum moves ,

Its mentioned in the editorial for a particular color i we need

min{a[i] , a[i-1] , ... , a[i-k]} . i dont understand how author uses this condition . and should we iterate for each k and then each i or for each i and the each k . how to deal with cycles , that is when we reach last index , how to relate it with first.

Can anyone who solved this problem , share approach .

> < > < >

The problem asks to toggle bits in a given range that after certain operations all bits becomes 0 .

My O(N2) solution is for a given light bulb if it is on the switch it off and update all the given ranges , but this will be N^2 complexity . How can we reduce it to O(n) . The last lines of the editorial i couldn't understood , how the author is updating the ranges .

how to do it . ?

#include <bits/stdc++.h>
#include <random>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef vector<int> vi;

const int MOD = 1e9 + 7;
const int INF = INT_MAX / 2;

int main() {
	int N; cin >> N;
	string s; cin >> s;
	vector<int> r(N), c(N);
	rep(i, N) scanf("%d", &r[i]);
	rep(i, N) scanf("%d", &c[i]);
	vector<int> diff(N + 1);
	int x = 0;
	ll ans = 0;
	rep(i, N) {
		x = (x + diff[i]) % 2;
		if (x != s[i] - '0') {
			ans += c[i];
			x = !x;
			diff[r[i]]++;
		}
	}
	cout << ans << endl;
}

You are given n checkpoints in (x , y) plane . you have to choose any two pairs i , j (j can be = i ) such that (xj-xi) + (yj-yi) = k

How to solve it in O(n) time .

N = 1e5 .

xi, yi = -1e9 , 1e9

Any idea.

example :

N = 4

(-2 , 2 ) , (0 , 3) , (1 ,2 ) , (1, 2)

k = 0 .

ans = 10

pairs are (1,1) (2,2) (3,3) (4,4) , (2,3) , (2,4) , (3,2) , (3,4) , (4,2) , (4,3)

i was solving 320E . the problem required some convex hull optimization.

i searched on web i got these blogs :

blog1 by meooow

blog2 by infinity

blog3 by indy256

what are the difference between above three , and how many more are there . which hull to study (i think 3) to solve this .

what is convex hull and where to apply. Are there different algorithms for different questions

Also this link is not working , does anyone know what was in that : http://wcipeg.com/wiki/Convex_hull_trick

Please tell !

You , are given an array of n elements and q queries . Both n and q can range upto 10^5 , and 1<=a[i] <= 10^9.

how to find / count all the elements less than a given element in each query .

queries are in the form of l , r , x where x is number and l and r are starting and ending indices.

Example: index 1 based

a[] = {5 , 3 , 2 , 2 , 3 , 1 , 2 , 9 , 10 , 2 }

q1 = 5 9 5

ans = 3 { 3 , 1 , 2}

q2 = 1 4 2

ans = 2 {2 , 2 }

The problem gives a feel of segment tree , but how to solve it using ST ?

any idea.

Hello , can anyone give me any good blog or tutorial on priority queue . i always have difficulty in implementing it , using and updating values in it .

Thanks !

You are given a binary array consists of 0's and 1's , and q queries . q can be large !

in each query you are given a certain range [L , R].

suppose a[] = {1,0,0,1}

L = 1 , R = 3 .

do toggling , resultant array = {0,1,1,1}

L = 1 , R =4

count all one's , ans = 3.

you have to either toggle bits in the given range i.e make 0 = 1 and 1 = 0 .

and on another query you are about to count all 1's in the range of [L,R]. **** The problem gives a feel of segment tree + lazy propogation . but how to do toggling in segment tree .

how should we update the lazy tree !

Any idea !

Suppose you are given an Array : a[] = { 0 , 0 , 1 , 0 , 0} . size of array can be large upto 2e5. **** You have to count all the subarrays in which a particular element x occurs more than length(subarray) /2 times

for example if x = 0 :

subarrays are :

{0} index = 1

{0} index = 2

{0} index = 4

{0} index = 5

{0,0} index 1 --> 3

{0,0} index 4 -->5

{0,0,1}

{0,1,0}

{1,0,0}

{0,0,1,0}

{0,1,0,0}

{0,0,1,0,0}

ans = 12.

Any idea !

hi ! i came to see that there are there more supports in most compilers :

1. int_fast64_t

2. int64_t

3. int_least64_t

i use long long every time ! which is the best , normal int probably not as it gives wa due to overflow !

which is the best in above 3 !

)

Suppose we have an array of n = 10^5 elements . 1 index based.

now , we build a segment tree with lazy propogation .

there are large queries , in each query you have to update elements in the range from 1 to n every time . by +x.

will the time complexity be O(n*m*logn) ? ? since everytime our numbers are from minn index to maxxindex.

Hello , I was solving 510D .

Here are my two submssions : link1 , link2

why map in link1 is giving correct answer while un.map gives wrong.

the question is to choose k subsets ,to make their gcd = 1 and minimise the cost of choosing .

Any idea ! :

Can anyone explain me how binary search will lead to answer.

https://mirror.codeforces.com/problemset/problem/1100/E

the problem asks to maximize the number of blocks and volume .

from the editorial it is clear that we should select block of sizes a and a-1 for our

optimal answer .

but in code1 mentioned in the editorial , how does the second recursion came in picture .

here is the code :

Your code here...

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

pair<ll,ll> best;

ll my_pow(ll x) { return x * x * x; }

void rec(ll m, ll steps, ll subtracted) {
	if(m == 0) {
		best = max(best, make_pair(steps, subtracted));
		return;
	}
	ll x = 1;
	while(my_pow(x+1) <= m) ++x;
	rec(m - my_pow(x), steps+1, subtracted + my_pow(x));
	if(x - 1 >= 0) 
		***  rec(my_pow(x)-1-my_pow(x-1), steps+1, subtracted + my_pow(x-1));  /// here **** 
}

int main() {
	ll m;
	scanf("%lld", &m);
	rec(m, 0, 0);
	printf("%lld %lldn", best.first, best.second);
	return 0;
}

while subtracting pow(x-1) shouldn't we subtract it from m ? and how the second recursion will lead us to answer ?

in problem zuma , why do we need a dp state like : as mentioned in tutorial

if(arr[i] == arr[i+1]) dp[i][j] = 1+dp[i+2][j]

i checked by removing this state and it gave WA .

why only these 2 dp states are not enough ! #@

dp[i][j] = 1+dp[i+1][j] and

dp[i][j] = dp[i+1][k-1] + dp[k+1][j]

CAN anyone clarify it more ? ! @

in problem 459d we have to find the i,j pairs for which f(1,i,a[i]) > f(j,n,a[j]])

we will first count left[i] i.e frequency of a[i] in the range [1,i] and r[i] i.e freq. of a[i] from [i,n] .

after that what to do .. how to solve it in O(n) time ..

please help !

Please provide me some very easy segment tree questions . help would be appreciated..

i always faces difficulty in segment tree problem.. and if question is tough then it is out of my bound...

pls help.. thanks :))

Can anyone please share the idea behind , how to solve 35E

any help ... since no tutorial is available..

in problem 28c

how to solve it >>

any helppp!!!

in problem 27E you are asked to find the smallest positive integer which has exactly n divisors .

how to solve it > >