Hi Arpa,

Nice to hear. I'm interested in improving this project.

https://github.com/sukeesh/gocf

Shall we discuss on GitHub issue of this repo?

WA 29905833

Instead of storing all the divisors of current nude in a vector because of memory constraints, I tried to iterate through all divisors of current node again and decremented the count.

Why does this fail?

Can someone explain reason for WA?
MATDYS

Can someone explain reason for MLE in my code?

Code : 28646208

You can solve this without binary search too.

You should remove k integers either from starting or ending because removing elements from the middle of the array only increases the consecutive difference and It doesn't make sense.

We start by building segment tree on the consecutive differences.

and then we iterate the array from left to right, at every index i we assume that we have removed i elements from starting and now, we need to remove k — i elements from the end.

We now query for the maximum difference in this remaining segment and the final answer would be the minimum of these queries.

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

#define eps 1e-9
#define all(a)   a.begin(),a.end()
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define sz size()
#define rd(inp) scanf("%lld",&inp)
#define rd2(inp1, inp2) scanf("%lld %lld",&inp1, &inp2)
#define rl(inp) scanf("%d",&inp)
#define pf(out) printf("%lld\n", out);

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int inf = 1e9;

#define maxn 100100
ll a[maxn], nn, tree[maxn * 8];
vector<ll> d;

void build(ll node, ll start, ll end){
	if(start == end){
		tree[node] = d[start];
	}
	else{
		ll mid = (start + end) / 2;
		build( 2* node + 1 , start, mid);
		build( 2* node + 2, mid + 1, end);
		tree[node] = max(tree[node*2 + 1], tree[node*2+2]);
	}
}

ll query(ll node, ll start, ll end, ll l, ll r){
	if(r < start || end < l){
		return 0;
	}
	if(l <= start && end <=r){
		return tree[node];
	}
	ll mid = (start + end) / 2;
	ll p1 = query(2 * node + 1, start, mid, l, r);
	ll p2 = query(2 * node + 2, mid + 1, end, l, r);
	return max(p1, p2);
}

int main(){
	ll n, i, m = 0, k;
	cin >> n >> k;
	for ( i = 0 ; i < n ; i ++ ){
		cin >> a[i];
	}
	for ( i = 1 ; i < n ; i ++ ){
		d.pb(abs(a[i] - a[i - 1]));
		m = max(m, abs(a[i] - a[i - 1]));
	}
	nn = n - 1;
	build(0, 0, nn - 1);
	ll ans = m;
	for ( i = 0 ; i <= k && i < n ; i ++ ){
		ll rem = k - i;
		if ( rem + i == k ){
			ll rg = n - 1 - rem;
			ans = min(ans, query(0, 0, nn - 1, i, rg - 1));
		}
	}
	cout << ans << endl;
	return 0;	
}

Just mail them.

I'm in

Can someone explain why did my code fail?

23085756

Care to explain?

Same Argument!

Why does he even include bands with > m if he doesn't like them? :(

Much simpler solution for D 21091527

Push all elements into a Priority Queue and pop out the top element, reduce it ( divide by 2 ) until it encounters a value which isn't visited yet and push reduced value into this Priority Queue.

Repeat this process until you are unable to reduce the top most element further.

That's it!

Yes, I agree with you!

Yeah, this has become very frequent these days :(

O(N * sqrt(N)) doesn't work here.
Intended solution is O(N * log(N))
here N  =  10⁶
so O(N * sqrt(N)) would be of order 10⁹, which is hard to pass even though you make good I/O optimisation.
Use MO's Algorithm for N  =  10⁵ order.

Thanks for the test case!

19278465

Div2 D,
19261965 Where did I go wrong?
This test case has 0 roots.
Can someone please help?

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

I am majoring in Metallurgical and Materials Science Engineering. I have serious hatred towards my branch. I don't belong to any Programming/Mathematical Clubs in our Institute.

I like to solve Mathematical Problems and Participating in Programming Contests is fun!

Thanks!

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

This solution might lead to unbalanced BST. This leads to O(N) height and O(N^2) insertions.

Done, Now works fine for all the contests!

Done!

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

your first submission gets skipped

yes, will do it! :)

Yes,
We need to change it here
Almost all the contests have A-E , except for some openCup rounds
I will add that feature as soon as possible.

first incf, enter the contest code ( Contest code is different from round number )
. for example, take 8VC Venture Cup Quals.,
Contest code is 626, let's say you want to test it for problem A, Your Problem name should be in the format 626_A.cpp [Strict]. Now, gocf 626_A.cpp

open terminal sudo vim /bin/gocf, change the line 5
replace ~/GoCF/sukeesh.txt with /home/<username>/GoCF/sukeesh.txt

and in line 21 to pathe='/home/<username>/GoCF/'
It should work fine now!

did you create a directory named 'GoCF' in your home folder?
and do touch ~/GoCF/sukeesh.txt .

for Div2A,
My AC: http://www.codeforces.com/contest/624/submission/15794996
WA : http://www.codeforces.com/contest/624/submission/15793258

Why printf fails?

See this one, link

Reach Div1 by the end of 2016 ! :) , Happy New Year Everyone !!

How to solve problem E ?

my AC was : http://ideone.com/z8dqVj ( No Binary Search )
consider this dp state ,
dp[present_pos] = total_beacons_affected_by_present_beacon + dp[previous_unaffected_beacon]
here, previous unaffected beacon means the beacon which is unaffected by the present beacon
After that try to disable beacons from present pos to n and calc best using the previous data
i.e., min of total_beacons-total_beacons_until_this_beacon+dp[present_beacon] all positions .

I can't understand this solution too.
There is O(n) soln for this
my solution > 13779488

This Problem and Case of Matryoshkas (Div2) are exactly same problems.

Dude, Read my comment properly.

i got Wrong Answer on Pretest 6. But my GCC Compiler shows the correct output required!

why gnu inbuilt pow function fails?

Nice Round :)

Cool One :D !!