### atlasworld's blog

By atlasworld, history, 6 weeks ago, ,

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).

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).

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.

• +11

By atlasworld, history, 2 months ago, ,

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.
}
};


• -2

By atlasworld, history, 3 months ago, ,

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.

why no one is replying ?

• -8

By atlasworld, history, 3 months ago, ,

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 !

• -3

By atlasworld, history, 3 months ago, ,

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.

• -12

By atlasworld, history, 4 months ago, ,

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.

• +4

By atlasworld, history, 5 months ago, ,

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 .

> < > < >

• -3

By atlasworld, history, 5 months ago, ,

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 . ?

Can anyone help me what the author is done in this code

• 0

By atlasworld, history, 6 months ago, ,

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)

• -8

By atlasworld, history, 6 months ago, ,

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

i searched on web i got these blogs :

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

• +5

By atlasworld, history, 6 months ago, ,

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.

• -19

By atlasworld, history, 6 months ago, ,

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 !

• 0

By atlasworld, history, 6 months ago, ,

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 !

• +6

By atlasworld, history, 6 months ago, ,

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 !

• -4

By atlasworld, history, 6 months ago, ,

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 !

)

• +3

By atlasworld, history, 7 months ago, ,

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.

• -3

By atlasworld, history, 7 months ago, ,

Hello , I was solving 510D .

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 ! :

• 0

By atlasworld, history, 7 months ago, ,

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

• -19

By atlasworld, history, 7 months ago, ,

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

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 ?

• 0

By atlasworld, history, 8 months ago, ,

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 ? ! @

• -20

By atlasworld, history, 8 months ago, ,

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 ..

• -8

By atlasworld, history, 10 months ago, ,

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 :))

• +4

By atlasworld, history, 10 months ago, ,

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

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

• +9

By atlasworld, history, 10 months ago, ,

in problem 28c

how to solve it >>

any helppp!!!

• 0

By atlasworld, history, 11 months ago, ,

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

how to solve it > >