### Akin's blog

By Akin, history, 2 years ago, , Codeforces Long Submission Queue !

What happened with Codeforces ?

UPD : Now okay !

By Akin, history, 4 years ago, , My solution First make a convex hull , then check is missile inside the convex polygon? if yes then add with the answer . I check random case in udebug , but its work fine !

Getting WA , but why ?

By Akin, history, 4 years ago, , Suppose we want to fill one array A (which has M elements) such that the sum of the numbers is X.

X=A+A+A....A[m] where A[i] is a non-negative numbers. The number of ways to fill this row can be obtained using a combinatorics formulae: (X+M-1) C (X-1).

Can anyone explain ? Thanks in advance.

By Akin, 4 years ago, , I submit 2 solution of this problem , both are almost same . But this one need 2.31 sec and that one need 1.49 sec , why ?

If I change the second solution the compare function as

bool cp( Q a, Q b ) {
int ax=a.L/tmt,bx=b.L/tmt;
if ( ax!=bx ) return ax<bx;
return (ax&1)?a.R<b.R:a.R>b.R;
}


and change the value of as

tmt=(int)(1.514*sqrt(m)+1);


then it need .96sec to pass , why ?

By Akin, 4 years ago, , Problem : The number of ways one could remove letters from a particular word so that it would become a palindrome.Two ways that differ due to order of removing letters are considered the same. And it can also be the case that no letters have to be removed to form a palindrome.

I am trying to solve this problem . But my solution gives wrong answer . Then I found a solution that works here. But don't understand the recurrence . Something like this ..

ll rec(int i, int j)
{
if(j < i) return 0;
if(i == j) return 1;
ll &ret = dp[i][j];
if(ret != -1) return ret;
if(str[i] == str[j])
return ret =  1 + rec(i+1, j) + rec(i, j-1);
else
return ret = rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1);
}



I don't understand why subtract rec(i+1, j-1) ? For order of removing letters are considered the same, means we count same way 2 times that why subtract ? Please explain the recurrence , thanks in advance . dp,
By Akin, 4 years ago, , In graham's scan remove duplicate points is necessary but in Monotone Chain algo it is not necessary why?

By Akin, 4 years ago, , I found misof to use Compound Operator <?= and <? in his Code

Eryx also use those in his Code

I don't understand what ** <?= and <?** means ?

How they works ?

By Akin, 4 years ago, , Problem looks greedy to me !! But I can't find any way to solve it .

Most confusing line is "waiting time of a person who waits longest is minimized?"

Here waiting time means previous waiting time+new queue waiting time and waits longest consider by waiting time ?

"calculate the minimum waiting time for a person who waits the longest."

Here waiting time previous waiting time+new queue waiting time or new queue waiting time only ?

If anyone confused with my question , then please explain details forgot all the above. Anyone explain how to solution ? By Akin, 5 years ago, , There are many good blogs in Codeforces Blog where people describes about different Algorithm and Data Structures .

Lets gather all the resources about Algorithm and Data Structures Explanations. You can comment bellow the link and about it . I will always update that post gather new resources.Hope ,its help all and inspire all to write new blog post in future :)

Last added blogs link will have a tag (New)

Resources:

C++ STL

C++ STL: Policy based data structures

C++ STL: Policy based data structures. Part 2

String Processing

Suffix tree. Basics. Building in O(nlogn)

Z Algorithm

Great resource for string algorithms

Aho-Corasick algorithm. Construction

Suffix tree. Ukkonen's algorithm

Data Structures

Partially Ordered Sets

Segment Tree

Basic Binary Indexed Tree (English version)

Memory-optimal Range Queries and Updates in logN

Segment tree with insertion and deletion operators

An efficient way to strengthen up your segment tree

Palindromic tree: behind the scenes

Game Theory

Nim (Algorithmic Game)

Dynamic Programming

Dynamic Programming Optimizations

Dynamic Programming Type

Enumeration of combinatorial sequences

Dynamic programming over subsets and paths in graphs

Kadane's Algorithm — (Dynamic Programming) — For new Solvers!

Geometry

Geometry shrink trick

Graph

Basic Graph Theory

Tutorial on Heavy Light Decomposition + Problems

Heavy-light decompositon — it can be simple!

0-1 BFS

Sorting & Searching

Binary search implementation

Number Theory

Sieve Methods : Prime, Divisor, Euler Phi etc

Remainder Theorem

Prime Factorization In log(n) After Sieve

Misc

C++ Tricks

Anti-hash test. Tutorial of Abinash By Akin, 5 years ago, , I see it sometimes in editorial of CF round and in problems tag ?

But don't know what it is ? I searched and found something like that

Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X.

But how to implement it and when it can be implemented for better result ?

Thanks in Advanced :) By Akin, 5 years ago, , My Idea :If D = Distance between Two Upper L Block then there are two case

1. If I make D larger that make the circle larger
2. If I make D smaller that make the circle larger for upper 'v' block

So this properties make the graph of Distance like 'U' ( Unimodal ) That why I thinks it can be solve by Ternary Search where variable is D here . But don't figure out how to check is circle is larger or smaller when searching ? I checking I have calculate radius of circle for mid values , but how ?

Thanks in Advance !! By Akin, 5 years ago, , It's a game.Let’s say at the beginning of round i, Alice has a Taka (Currency of Bangladesh) and Bob has b Taka. and c is the minimum of a and b. Alice and Bob are equally likely to win the round. If Alice wins, she gets c Taka from Bob, otherwise Bob gets c Taka from her and go to the next round and so on. Game ends when one of them has 0(Zero) Taka and obviously the person with 0 taka loses.

The initial amount Alice has is a and the initial amount that Bob has is b, you have to find the probability that Alice is going to win and expected number of rounds the game is played.

My solution Idea: There are a situation when playing rounds , we found same position of (a,b) as started .This situation will come when min(a,b) will win the round.Every round the probability to win the round 0.5.

But my solution didn't work ,but why ?

Can anyone explain how to solution ? dp,
By Akin, 5 years ago, , In a race there are n horses. You have to output the number of ways the race can finish. Note that, more than one horse may get the same position. For example, 2 horses can finish in 3 ways. - - Both first - horse1 first and horse2 second - horse2 first and horse1 second

My Idea is just Count all the way , there are two case when position are same or position increment of horse.

ans= solve(pos,h+1)+solve(pos+1,h+1)


My Solution

But it fails , But Why ?

Can anyone explain why my idea fail and describe about the idea above or give a solution idea .

Thanks in advanced :) By Akin, 5 years ago, , You are developing a 'Love calculator'. So, given two names your software will generate the percentage of their 'love' according to their names. The software requires the following things: 1.The length of the shortest string that contains the names as subsequence. 2.Total number of unique shortest strings which contain the names as subsequence. Now your task is to find these parts.

I find 1st part by computing (length of 1st name +length of 2nd name — LCS(1st name , 2nd name ).

But how to find 2nd part ?? lcs,
By Akin, 5 years ago, , By Akin, 5 years ago, ,  