atlasworld's blog

By atlasworld, history, 5 days ago, In English,

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 !

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By atlasworld, history, 9 days ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • -19
  • Vote: I do not like it  

By atlasworld, history, 2 weeks ago, In English,

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 !

Read more »

 
 
 
 

By atlasworld, history, 2 weeks ago, In English,

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 !

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By atlasworld, history, 3 weeks ago, In English,

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 !

Read more »

 
 
 
 
  • Vote: I like it  
  • -4
  • Vote: I do not like it  

By atlasworld, history, 3 weeks ago, In English,

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 !

)

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By atlasworld, history, 4 weeks ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By atlasworld, history, 5 weeks ago, In English,

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

Read more »

 
 
 
 

By atlasworld, history, 5 weeks ago, In English,

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -19
  • Vote: I do not like it  

By atlasworld, history, 6 weeks ago, In English,

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 ?

Read more »

 
 
 
 

By atlasworld, history, 7 weeks ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • -20
  • Vote: I do not like it  

By atlasworld, history, 2 months ago, In English,

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 !

Read more »

 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By atlasworld, history, 4 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +4
  • Vote: I do not like it  

By atlasworld, history, 4 months ago, In English,

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +9
  • Vote: I do not like it  

By atlasworld, history, 5 months ago, In English,

in problem 28c

how to solve it >>

any helppp!!!

Read more »

 
 
 
 

By atlasworld, history, 5 months ago, In English,

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

how to solve it > >

Read more »

 
 
 
 
  • Vote: I like it  
  • +5
  • Vote: I do not like it  

By atlasworld, history, 7 months ago, In English,

can anyone please share his idea of solving problem 23E .

we are given a tree and we have to remove some edges from the tree (>=0) to maximize the product of sizes of connected components !

Read more »

Tags dp, tree
 
 
 
 

By atlasworld, history, 7 months ago, In English,

can anyone please explain how this problem will reduce to 0/1 Knapsack problem after increasing each t[i] by 1?

why we are increasing t[i] by 1 ?

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

By atlasworld, 8 months ago, In English,

Anyone who has solved problem E , please explain his approach .

the editorial says that first calculate cost for first level rows then do recalculation, but how to do it ? its quite unclear.

Problem

Upd:

What I thought is.. Suppose we have processed upto row no. x optimally and now processing x+1.

The calculation for the current row will not change the optimality of the row till x.

If we use this observation for the 1st row , We can optimally calculate the optimal cost to repaint the first row and make it in the form ABABAB....

Now... I got stuck from the 2nd row onwards..

What should we do to calculate the optimal cost for repainting from 2nd row to last row.

How should we process the column elements for a particular row ?

Upd 2:

Sol.`

Read more »

 
 
 
 

By atlasworld, history, 8 months ago, In English,

Anyone who solve problem 16E, can please share his ideas.There is no official solution of this round. link

in the announcement thread it is mentioned that it will be solved using state compression dp , but what is state compression dp and what will be the dp state for this question ?

Read more »

Tags #dp
 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By atlasworld, history, 8 months ago, In English,

anyone who solved this problem http://codeforces.com/problemset/problem/12/D , can please share his ideas.

i have read this blog http://codeforces.com/blog/entry/44775#comment-437643 , the explanation which is written by

@satyaki3794 , how will it fit in time limit ?

Read more »

 
 
 
 

By atlasworld, history, 9 months ago, In English,

Can anyone who solved problem 7E share his ideas , how to solve it.

http://codeforces.com/contest/7/problem/E

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it