scopeInfinity's blog

By scopeInfinity, history, 6 years ago, In English

I was going through a blog (https://cp-algorithms.com/data_structures/segment_tree.html )

It says something like -

The query function is also almost equivalent, only now the lower_bound function of the multiset function should be called instead (std::lower_bound only works in O(logn) time if used with random-access iterators).

I need some help, to clarify few doubts(might help others too) —

  • How can I define multiset with random-access iterators in C++?
  • Can we find the rank of an element using it?
  • How is it different from "C++ STL: Policy based data structures"?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By scopeInfinity, history, 8 years ago, In English

For a general Min Cost Max Flow problem cost C associated to an edge having flow F results in C*F .

Thus Objective is to minimize Sigma Ci * Fi, where Fi <= Capacity of ith Edge and giving maximum flow.

0-1 Version

If we have a variation that with a flow F <= Capacity is flowing through an edge only Ci cost should be considered NOT Ci*Fi.

i.e. If edge allows flows its going to cost C or else its going to cost 0.

I am not sure, How can I proceed for it. The optimal cost flow is not required.

Full text and comments »

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

By scopeInfinity, history, 8 years ago, In English

There are few problems in which we can't determine length of input. Program is meant to process all the input it is given and terminates after no input is left in stdin.

For Example

Problem : Print Sum in new line for every two integer in a line.

Sample Input —

5 6
10 15
3 4

Sample Output -

11
25
7

Similar Question on SPOJ

http://www.spoj.com/problems/NHAY/

What is a good way to handle this kind of Inputs??

Full text and comments »

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

By scopeInfinity, history, 8 years ago, In English

While I was submitting solution for http://www.codeforces.com/contest/86/problem/D, I was getting TLE.

So, I searched for getting faster inputs in C++. Somehow, It was Accepted. But, I didn't understand weird behavior of inline functions.

I think using inline functions make program runs faster, but in my case it was making TLE.

My Submissions with minor changes in 'readLongLong' function:

  • No Inline and Pass By Reference : Accepted

http://www.codeforces.com/contest/86/submission/18234613

  • Inline and Pass By Reference : TLE at test 42

http://www.codeforces.com/contest/86/submission/18234625

  • No Inline and value return : TLE at test 42

http://www.codeforces.com/contest/86/submission/18234694

  • Inline and value return : TLE at test 51

http://www.codeforces.com/contest/86/submission/18234684

Inline with Pass By Reference : TLE

inline void readLongLong (ll &val) {
	char ch;
	val = 0;
	while (true)
	{
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		val = val*10 + (ch - '0');
	}
}

No Inline with Pass By Reference : Accepted

void readLongLong (ll &val) {
	char ch;
	val = 0;
	while (true)
	{
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		val = val*10 + (ch - '0');
	}
}

Full text and comments »

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