Codeforces Long Submission Queue !

What happened with Codeforces ?

**UPD** : Now okay !

# | User | Rating |
---|---|---|

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | awoo | 185 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

6 | Radewoosh | 176 |

6 | maroonrk | 176 |

6 | -is-this-fft- | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

Codeforces Long Submission Queue !

What happened with Codeforces ?

**UPD** : Now okay !

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 .

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)

Great resource for string algorithms

Aho-Corasick algorithm. Construction

Suffix tree. Ukkonen's algorithm

On suffix automaton (and tree) **New**

**Data Structures**

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

Algorithm Gym :: Data structures

Algorithm Gym :: Everything About Segment Trees

Palindromic tree: behind the scenes

Implicit cartesian tree in GNU C++ STL

Efficient and easy segment trees

Splay tree and its implementation. **New**

**Game Theory**

**Dynamic Programming**

Dynamic Programming Optimizations

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

Easy geometry using std::complex **New**

**Graph**

Algorithm Gym :: Graph Algorithms

Tutorial on Heavy Light Decomposition + Problems

Heavy-light decompositon — it can be simple!

Faster Dijkstra on Special Graphs **New**

**Sorting & Searching**

**Number Theory**

Sieve Methods : Prime, Divisor, Euler Phi etc

Prime Factorization In log(n) After Sieve

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

**Misc**

An awesome list for competitive programming! **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

- If I make D larger that make the circle larger
- 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)
```

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

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2021 10:45:46 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|