Codeforces Long Submission Queue !

What happened with Codeforces ?

UPD : Now okay !

Problem

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 ?

Suppose we want to fill one array A (which has M elements) such that the sum of the numbers is X.

X=A[1]+A[2]+A[3]....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.

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 ?

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 .

In graham's scan remove duplicate points is necessary but in Monotone Chain algo it is not necessary why?

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 ?

Problem : Link

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 ?

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

On suffix automaton (and tree) New

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

About ordered set

An efficient way to strengthen up your segment tree

Algorithm Gym :: Data structures

Algorithm Gym :: Everything About Segment Trees

Mo's Algorithm

Palindromic tree: behind the scenes

Cartesian tree (Treap)

Implicit cartesian tree in GNU C++ STL

Efficient and easy segment trees

SQRT decomposition

Splay tree and its implementation. New

Mo's Algorithm on Trees New

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!

A little bit of classics: dynamic programming over subsets and paths in graphs

Geometry

Geometry shrink trick

How to sweep like a Sir

Easy geometry using std::complex New

Graph

Algorithm Gym :: Graph Algorithms

Basic Graph Theory

Tutorial on Heavy Light Decomposition + Problems

Heavy-light decompositon — it can be simple!

2-SAT Tutorial

Dynamic connectivity problem

0-1 BFS

Faster Dijkstra on Special Graphs New

Sorting & Searching

Binary search implementation

Quicksort and chill

Number Theory

Sieve Methods : Prime, Divisor, Euler Phi etc

Remainder Theorem

Prime Factorization In log(n) After Sieve

Counting Divisors of a Number in O(N^(1/3))

Extensions of the Prime Sieve

Misc

C++ Tricks

Anti-hash test.

Matrix

CodeChef Tutorial

An awesome list for competitive programming! New

Tutorial on FFT — The tough made simple. New

O(n) solution for 631E (Convex Hull Trick special case) New

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

Problem :Link

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

Problem : Link

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 ?

Problem : Link

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

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

I think everyone show ACM ICPC 2014 World Finals Scoreboard with TopCoder and Codeforces Handles , but most people don't know there was a Chat Bar .In that website there was a box show chat , just click and chat with everyone about ACM ICPC 2014 World Finals ..

Easier To Harder

1. http://www.spoj.com/problems/MST1/
2. http://uva.onlinejudge.org/external/1/100.html
3. http://mirror.codeforces.com/contest/368/problem/B
4. http://projecteuler.net/index.php?section=problems&id=15
5. http://community.topcoder.com/stat?c=problem_statement&pm=13159
6. http://lightoj.com/volume_showproblem.php?problem=1004
7. http://lightoj.com/volume_showproblem.php?problem=1005
8. http://uva.onlinejudge.org/external/8/825.html
9. http://community.topcoder.com/stat?c=problem_statement&pm=10240
10. http://uva.onlinejudge.org/external/9/900.html
11. http://acm.timus.ru/problem.aspx?space=1&num=1225
12. http://mirror.codeforces.com/contest/359/problem/B
13. http://community.topcoder.com/stat?c=problem_statement&pm=11341
14. http://community.topcoder.com/stat?c=problem_statement&pm=10182
15. http://community.topcoder.com/stat?c=problem_statement&pm=2292

6.6.2014 — 1,2,7 number problem Discussed

7.6.2014 — 1,4,7 number problem Discussed

_harun mehadi13 Al_Mamun inxor97