Codeforces Long Submission Queue !
What happened with Codeforces ?
UPD : Now okay !
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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 .
In graham's scan remove duplicate points is necessary but in Monotone Chain algo it is not necessary why?
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
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 ??
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 ..
Name |
---|