### RNR's blog

By RNR, history, 9 months ago, ,

I have studied the Push-Relabel algorithm, the main difference between Augmenting path algorithms and Push-Relabel is that:

• Augmenting path algorithms maintain a flow(capacity constraints and conservation constraints are valid) and augment it some s-t path in each iteration to increase its value. We iterate untill there exists no s-t path in the current residual network.
• Push-Relabel algorithm takes a different approach, it works with pre-flow(conservation constraint is violated — the amount of flow into a vertex can exceed the amount of flow exiting it, the difference(flow_in-flow_out) in the amount present at that vertex is called excess, excess >= 0). This algorithm starts with a pre flow and terminates with an actual flow, eliminates all the excesses. We start with s-t disconnected and work towards a feasible flow.

To eliminate excess at a vertex it has the following function:

Push(v):
choose an outgoing edge (v, w) of v in Residual graph G_f (if any)
// push as much flow as possible
let fl = min{excess(v), capacilty of edge(v, w)}
push fl units of flow along (v, w)

Choose an edge(what type of edge will be clear later) and push as much as we can.

We maintain heights to route flow from source to sink, otherwise, if we have a cycle in the network we might end up pushing around it indefinitely. To route the excess flow systematically we maintain these heights, heights are always non-negative, and thus we can visualize edges going uphill, downhill or at the same level. We maintain these invariants, let's denote height by h then h(src)=|V|, h(sink)=0 and for every edge (v, w) of the current residual network G_f (with positive residual capacity), h(v) <= h(w) + 1, the third one says that if we have to go downhill through the edges we only go down 1 step at a time(height doesn't go down quickly).

The motivation for invariants: We maintain that s-t is disconnected as h(s)=|V| and h(t)=0 if there is a path then it is of length atmost |V|-1.

We initialize the network with the following:

h(s) = |V|
h(v) = 0 for V-{s}
flow = capacity for (s,*) // edges going out of source
flow = 0 for E-{(s,*)}

The Pre-flow for edges going out of s is at full capacity so as to maintain the third invariant so that we don't have edges going out of s with positive residual capacity.

We restrict the above Push() operation — flow is only allowed to be pushed downhill in the residual network. This restriction allows us to maintain invariants, if we push uphill then we get reverse arcs in the residual network which violate h(v) <= h(w) + 1.

The main iteration in this algorithm is to choose a vertex v in V-{s,t} with excess[v]>0, if there are many such vertices, choose any vertex with maximum height. Now if we have an edge going out of v in G_f with h(v)=h(w)+1, then Push() over this edge (v,w).

While there exists v in V-{s,t} with excess[v]>0:
Choose any vertex v with a maximum height
if there is an outgoing edge (v, w) of v in Gf with h(v) = h(w) + 1
Push(v)
else
Relabel(v)

The idea behind choosing maximum height is to select one furthest away from the sink t. The hope is that working on those nodes will move the flow towards the sink, and aggregate them along the way.

Here is the Relabel(v) algorithm

Relabel(v):
h[v]++;

One can observe that the same vertex will be relabelled until we find a vertex w such that h(v)=h(w)+1 so we can rewrite the Relabel(v) function as follows:

Relabel(v):
d=INF
for all edges (v,w) with positive residual capacity
d=min(d,h[w])
h[v]=d+1

About the running time $O(n^3)$:

• If the vertex v has positive excess in the pre-flow f, then there is a path v->s in the residual network G_f. — Clearly, the excess must have come from the source only so there should be a path to s.

• In the push-relabel algorithm, every vertex always has height at most 2|V|. — As the height of the source is |V|, and there is a path from v to s and height invariant. Therefore, the push-relabel algorithm performs $O(n^2)$ relabels

• Now if we think when the Push will flow will be bounded by Capacity(Saturating pushes) and when it will be bounded by Excess(Non-saturating pushes), One can prove that Between two saturating pushes on the same edge (v, w) in the same direction, each of v, w is relabeled at least twice. and Between any two relabel operations, there are at most n non-saturating pushes.

Here is implementation from CP-algorithms

Here is an implementation from Stanford Notebook with Gap Heuristic.

[UPD -- Gap Heuristic]

Let g be an integer and 0 < g < n. Suppose at a certain stage of the algorithm there are no nodes with height/distance label g but there are nodes v with g < h(v) < n. Then the sink is not reachable from any of these nodes. Therefore, the labels of such nodes may be increased to n. (Note that these nodes will never be active.) If for every i we maintain linked lists of nodes with the distance label i, the overhead of detecting the gap is very small. Most work done by the gap relabeling heuristic is useful: it involves processing the nodes determined to be disconnected from the sink.

You can take a look at my implementation tested with SPOJ/MTOTALF and Kattis/maxflow for better understanding.

Code

Here is a submission from zscoder

If you have better implementations(with some heuristics), you can share in comments. Learn and Let Learn.

• +44

By RNR, history, 9 months ago, ,

I know the standard sieve algorithm for finding primes in a range [0..upperbound]

Here is a standard implementation

for(int i=2;i<=N;i++)
if(prime[i])
for(int j=i*i;j<=N;j+=i) prime[j]=0;

But when memory is tight, here is the famous implementation by yarin

#define MAXSIEVE 100000000 // All prime numbers up to this
#define MAXSIEVEHALF (MAXSIEVE/2)
#define MAXSQRT 5000 // sqrt(MAXSIEVE)/2
char a[MAXSIEVE/16+2];
#define isprime(n) (a[(n)>>4]&(1<<(((n)>>1)&7))) // Works when n is odd

int i,j;
memset(a,255,sizeof(a));
a[0]=0xFE; // 254
for(i=1;i<MAXSQRT;i++)
if (a[i>>3]&(1<<(i&7)))
for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)
a[j>>3]&=~(1<<(j&7));

I understood that we are only storing odd numbers and char can store 8 bits and we are storing it using j>>3 and unsetting using ~(1<<(j&7)). When considering only odd numbers, you let index 1 be 3, index 2 be 5 etc.

But I didn't understand the strange loop incrementations and initialization in for(j=i+i+i+1;j<MAXSIEVEHALF;j+=i+i+1)

Any help would be greatly appreciated. Thank you in advance.

• 0

By RNR, history, 10 months ago, ,

Many times while debugging in contests, to trace the elements I use multiple functions like following,

Code

It's good if I can trace all using one method, I was looking for one single function/method for printing variables, vectors, etc.

Watching Errichto streams and this tweet during ICPC live stream, I got interested in this template but couldn't understand much of this, I wanted to use this template, know how to use, but don't understand why it works, and I try not to put things that I don’t understand in my template, Can you please help me in understanding this

Original code

We can generally use this like this

debug() << imie(c * 2) imie(min(a, b)) imie(a != b);
debug() << "add" imie(i) imie(A) imie(diff);
debug() << imie(V); // V is a vector
debug() << imie(a) imie(h1) imie(h2) imie(my_dist) imie(path) imie(vertices); // int a,h1,h2; vector path;
debug() << "Zlaczacz::Ogarnij(" imie(a) imie(b) ") = " << res; // pair<vector<int>, vector<int>> res; int a,b;

So I have elaborated code and it resulted in the following

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {

/*sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);*/

template < class c > struct rge { c b, e; };
template < class c > rge<c> range(c i, c j) { return rge<c>{i, j}; }
template < class c > auto dud(c* x) -> decltype(cerr << *x, 0);
template < class c > char dud(...);

struct debug {
~debug() { cerr << endl; }

//eni(!=) cerr << boolalpha << i; ris; }        Part 1

template < class c > typename \
enable_if<sizeof dud<c>(0) != 1, debug&>::type operator<<(c i) {
cerr << boolalpha << i;
return * this;
}

//eni(==) ris << range(begin(i), end(i)); }     Part 2

template < class c > typename \
enable_if<sizeof dud<c>(0) == 1, debug&>::type operator<<(c i) {
return * this << range(begin(i), end(i));
}

/*sim, class b dor(pair < b, c > d) {           Part 3
ris << "(" << d.first << ", " << d.second << ")";
}*/

template < class c, class b > debug & operator << (pair < b, c > d) {
return * this << "(" << d.first << ", " << d.second << ")";
}

/*sim dor(rge<c> d) {                           Part 4
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}*/

template < class c > debug & operator <<(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
return * this << "]";
}

}
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

std::boolalpha is an I/O manipulator, it causes bool values to display as true or false. decltype inspects the declared type of an entity or the type and value category of expression.

When the macro is invoked, all the tokens in its argument list after the last named argument (this macro has none), including any commas, become the variable argument. This sequence of tokens replaces the identifier __VA_ARGS__ in the macro body wherever it appears. You may use the # and ## operators to stringify the variable argument or to paste its leading or trailing token with another token — Ref

template< bool B, class T = void >
struct enable_if;
/* If B is true, std::enable_if has a public member typedef type, equal to T; otherwise, there is no member typedef. */
template <typename T>
struct enable_if<true, T> {
typedef T type;
};

Can someone please explain what eni(x), dud does? and how does eni relate to Part 1 and Part 2? I didn't understand eni(x) and dud.

How rge is used in range?

I understand that Part 4 is to iterate through containers, is Part 3 for pairs?

• +31

By RNR, history, 13 months ago, ,

How to solve a generalization of this problem?

Given a string, remove identical consecutive letters ( not only pair as mentioned in the above question).

For example, if you have

wwwhaat --> ht
whhhaah --> w
reallazy --> rezy
whaahhhh --> w

Can someone suggest me an algorithm? For finding the minimum string at the end of this deletion?

• 0

By RNR, history, 14 months ago, ,

Consider a directed tree say for example P1--> P2--> P3--> P4--> ... --> Pn (consider this chain for simplicity), initially, it is like this, directed and atmost one edge going out of every node(for some nodes there might be no outgoing edges). Here it is like if the information starts at P1 it flows till Pn, similarly, if information starts at P2 it flows till Pn. Say if information starts at Pn it ends here itself.

We have two types of queries

Query 1: We have to answer where does it end if information starts at Pi?

Query 2: We may remove any existing edge, Eg we break a link say P2--> P3

Now the chain may look like P1--> P2 and P3 --> P4 -->...--> Pn now the query 1 for P1 is P2 and query1 for P2 is also P2?

I have seen this question in one contest on some website and it is removed now if you have seen something similar you can share here.

I want to know how to solve this efficiently?

• +4

By RNR, history, 2 years ago, ,

Hello,

I have a clear idea of implementing Suffix Links and I know how to build suffix links efficiently. I'm stuck with Output links, that is how to print the matched strings?

Suppose we have patterns:

i & in & tin & sting and the given string is sting

We miss both tin and in because each is a proper suffix of stin (Because suffix link of stin goes to n in tin and suffix link of n in tin goes to n in in).

Could someone share Implementation details of Aho-corasick automata?

• -4

By RNR, history, 2 years ago, ,

Hello,

Can someone explain the logic [and formal proof why this logic works] to solve this problem?

Consider a heap of N objects. Two players take turns playing the following game:

At his very first move, the first player removes from the heap between 1 and N-1 objects After that, at each step the player to move can remove any number of objects between 1 and the number of objects removed by the other player at the previous move When the heap becomes empty, the player to move loses the game.

[UPD.]

I know that removing the number of objects from Last on bit works. The Last on-bit, I mean the below.

int k=0;
while( n % (1<<(k+1)) == 0)
k++;
printf("%d",(1<<k));
fflush(stdout);
n -= (1<<k);

I need a formal proof/Argument that why is this working. Or why this is guaranteed to work?

Thank you.

• -3

By RNR, history, 2 years ago, ,

#### Reading Integers until End of file:

int a[110];
for(i = 0; scanf("%d", &a[i])!=EOF; i++);

Because scanf will return the total number of input successfully scanned.

int day, month, year;
scanf("%d/%d/%d", &month, &day, &year);

Helps when input is of format

01/29/64

char str[20];
scanf("%[01]s", str);
printf("%s\n", str);

%[01]s – Read only if you see 0’s and 1’s. Shorthand for matching characters in the seq [01] can also be extended for decimals using %[0-9]s. Similarly, %[abc]s – Read only if you see a, b, c. [...] read till these characters are found. [^...] read until these characters are not found.

char s[110];
scanf(“%[^\n]s”, s);

Here,we have [^\n]. The not operator (^) is used on the character \n, causes scanf to read everything but the character \n – which is automatically added when you press return after entering input.

#### Read but donot store. (use * assignment suppression character)

scanf("%d %*s %d", &a, &b);

The above segment can be used to read date format and do not store the month if the format is dd month yyyy (06 Jan 2018).Read the desired input, but do not store.

char c;
scanf("%*[ \t\n]%c",&c);
scanf(“%2d”, &x);

In this example we have, a number located between the % and d which in this case is 2. The number determines the number of integers our variable input (of integer type) will read. So if the input was “3222”, our variable would only read “32”.

#### End of File

while (scanf() != EOF){
//do something
}

#### Example from CP1

Take this problem with a non-standard input format: the first line of input is an integer N. This is followed by N lines, each starting with the character ‘0’, followed by a dot ‘.’, then followed by an unknown number of digits (up to 100 digits), and finally terminated with three dots ‘...’.

#### Input:-

3
0.1227...
0.517611738...
0.7341231223444344389923899277...

One possible solution is as follows.

#include <cstdio>
using namespace std;

int N;         // using global variables in contests can be a good strategy
char x[110];  // make it a habit to set array size a bit larger than needed

int main() {
scanf("%d\n", &N);
while (N--) {                  // we simply loop from N, N-1, N-2, ..., 0
scanf("0.%[0-9]...\n", &x);   // `&' is optional when x is a char array
// note: if you are surprised with the trick above,
// please check scanf details in www.cppreference.com
printf("the digits are 0.%s\n", x);
} } // return 0;

[UPD]

#### Scanf with search sets

We used hyphen in format string: dd-mm-yyyy

If we want more than one option: hyphen or slash: - or / then use search set %[-/]

Store the search string in a character variable

#include <stdio.h>
void main()
{
int date, month, year;
char separator[2];
printf("Input the date:");
scanf("%d%[-/]%d%[-/]%d", &date, separator, &month, separator,&year);
printf("Date: %d\n", date);
printf("Month: %d\n", month);
printf("Year: %d\n", year);
}

Examples

Input the date:31-12-2013
Date: 31
Month: 12
Year: 2013
*** another input ***
Input the date:14/1/2014
Date: 14
Month: 1
Year: 2014
*** another input ***
Input the date:26/2-2014
Date: 26
Month: 2
Year: 2014

The more simplified version using the above-mentioned assignment suppression operator.

scanf("%d%*[-/]%d%*[-/]%d", &date, &month, &year);

That the terminal is line-buffered means that it submits input to the program when a newline character is encountered. It is usually more efficient to submit blocks of data instead of one character at a time. It also offers the user a chance to edit the line before pressing enter.

Thanks

#### stringstream

You are given a String Rectangle consists of four integers separated by single spaces, with no additional spaces in the string. The first two integers are the window coordinates of the top left pixel in the given rectangle, and the last two integers are the window coordinates of its bottom right pixel.

string rectangle;
cin>>rectangle;
istringstream ss(rectangle);
int x1,y1,x2,y2;
ss >> y1 >> x1 >> y2 >> x2;

Thank you

• +66

By RNR, history, 2 years ago, ,

Given an array of N integers, you are given two types of queries:-

#### Type 1 ::: x y

Append y after index x (array size increases by 1 after every type 1 operation )

Print the array

### What is the efficient way to solve this problem?

Type 2 query takes O(n) time.

So the problem can be solved in O(n^2).

If we are given information that there are many many operations of Type 1 than Type 2 can we reduce the complexity?

For example, if we are given that Type 2 operations are <= sqrt(N) or so?

Thanking you.

UPD: Suppose if the query is like find the maximum in [l,r] range etc

• -19

By RNR, history, 2 years ago, ,

I am posting this just for beginners like me so that we can use such tricks in future and as both the problems are almost similar I just posted them together not to get confused in case.

# Q1.

You are given an array of N integers. Suppose you are allowed to change an element into any integer with one operation. Find the minimum number of operations to make the array strictly increasing. (Note that the elements can become <1). The given array contains N positive integers.

• 1 ≤ N ≤ 10^5
• 1 ≤ ai ≤ 10^9 for 1 <= i <= N

#### Example:

1) N = 5
1 2 2 3 6
Sol: 1 2 3 5 6. So the answer is 2

2) N = 3
1 1 1
Sol: −1 1 2. So the answer is 2

3) N = 6
4 2 4 4 6 8
Sol: 1 2 4 5 6 8. So the answer is 2

4) N = 7
1 2 2 2 3 4 5
Sol: -1 0 1 2 3 4 5. So the answer is 3.

#### Here is how we can solve this problem:

Suppose the problem was simply named Non-decreasing Array. Obviously, you want to keep as many numbers as possible unchanged. It follows that you can select the longest non-decreasing subsequence and modify all the other elements so that they'll respect the rule (by making them equal to values from the subsequence we've extracted accordingly). Back to our problem now, we're looking for a Strictly Increasing Array. If we make another ci = ai - i, the answer is the equal to (n - the longest of the non-decreasing subsequence with no negative number) and for the longest non-decreasing subsequence, a O(nlogn) solution can be used.

#### Why does this work?

Consider for some i and j, ci <= cj then ai - i <= aj - j that implies ai + j - i <= aj , which means we have enough space to fit a strictly increasing array between i and j.

# Q2.

Now consider the same problem but with the condition that the resulting sequence should only contain positive integers.

#### Here is how we can solve this problem:

For each element of the modified(or resulting) sequence we have bi >= i (1<=i<=n) and we need to find the longest increasing subsequence of the original sequence ai and ai >= i. We keep such ai unchanged and other values can be changed into the value as their index.

Then we should modify the above solution such that we have to consider longest non-decreasing subsequence only among those numbers such that ai - i >=0 but not the whole array ci. This ensures that the resulting array has the integers which are positive and forms strictly increasing sequence. Because in this way we make sure that all the elements such that ai < i initially have to be changed.

Another way is to modify the algorithm to only use positive numbers is to append a whole lot of numbers at the start of the array .i.e. change 1,2,9,10,3,15 to -5,-4,-3,-2,-1,1,2,9,10,3,15. Then you can be sure that the optimal answer will never decide to make the 1 go negative because it would cost so much to make all the negative numbers smaller. You only need to add N dummy nodes (the same as the length of the sequence, not the maximum number i.e 10^9 ).

#### Example:

Original sequence 1,2,2,2,3,4,5
Add dummy elements at start -5,-4,-3,-2,-1,1,2,2,2,3,4,5
Subtract off position in array -5,-5,-5,-5,-5,-4,-4,-5,-6,-6,-6,-6
Find longest non-decreasing sequence -5,-5,-5,-5,-5,-4,-4,*,*,*,*,*
So answer is to change 5 numbers. 1 2 3 4 5 6 7

[REF.]

• -40

By RNR, history, 2 years ago, ,

How does this work?

• llui mul_mod(llui a, llui b, llui m){
• llui y = (llui)((float64)a*(float64)b/m+(float64)1/2);
• y = y * m;
• llui x = a * b;
• llui r = x-y;
• if ( (lli)r < 0 ){
• r = r + m; y = y-1;
• }
• return r;
• }

For example if we do c = (a+b)%m;

What if a+b itself causes the overflow that is a+b is larger than the size of typeof a or b.

Doesn’t x in the above code cause overflow that is a*b is larger than a size of llui.

Here llui means long long unsigned int and lli means long long int and float64 stands for long double

• 0

By RNR, history, 3 years ago, ,

UVa 11173 — Grey Codes with a one-liner bit manipulation expression for each test case, i.e. ﬁnd the k-th Gray code.

Solution is k^(k>>1)

Let’s reverse the UVa 11173 problem above. Given a gray code, ﬁnd its position k using bit manipulation.

Solution: ????