| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 167 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
What is the proof that from any index idx , idx + (idx&-idx) is the next closest index that covers idx? I mean how can I prove that no other index in range ( idx,idx+(idx&-idx) ) actually covers idx? '(' means exclusive and covers idx means contains information of idx ??
Thanks in advance.
Original Statement https://community.topcoder.com/stat?c=problem_statement&pm=13268&rd=16187
Problem Summary : Given an array of 1<=N<=47 integers. All the integers are in range [1,47]. Given two number low,high(1<=low<=high<=47). We have pick a sub sequence of the given array in minimum move that contains only the numbers in range [low,high] and all the numbers in range[low,high]. In a single move we can pick a continuous sequence of numbers from the given array. We need to find number of ways to pick such sub sequence in minimum move.
Examples
First line contains the integers. Second and third line contains value of low and high respectively.
(Case 0)
{2, 1, 3}
1
3
Returns: 1
The only way to choose the subset is to choose all animals.
(Case 1)
{3, 4, 1, 3, 4, 2}
1
3
Returns: 2
In the optimal solution we send away animals #2, #3, and #5 (0-based indices). Animals #2 and #3 form one group, animal #5 forms the other.
(Case 2)
{3, 4, 3, 1, 6, 2, 5, 7, 5, 2}
2
6
Returns: 2
(Case 3)
{3, 1, 4}
2
4
Returns: -1
(Case 4)
{2, 1, 3, 1, 4}
1
4
Returns: 1
Note that we are not required to minimize the number of animals we send. Here, we could select just four of these five animals but that would create two groups. A better solution is to select all five animals, then they all form a single group.
(Case 5)
{7, 12, 2, 12, 10, 13, 6, 5, 3, 3, 4, 11, 12, 4, 3, 1, 8, 11, 4, 7, 6, 5, 47}
2
7
Returns: 3 I couldn't figure out the DP idea. Can anyone show me a direction in the problem? Thanks in advance.
Problem Link I can think about a n^2 DP approach, But I don't know how to optimize it further :( . Any hints,plz??? Thanks in advance.
EDIT: NICE PROBLEM. SOLVED IT. WROTE A TUTORIAL ON IT. https://www.linkedin.com/pulse/beautiful-composition-data-structure-algorithm-najim-ahmed?published=t
Given N points. I want to find convex hull keeping collinear points. How should I prepare my initial sort function so that I don't have to make a right turn for points who are collinear? Example: 6 1 1 3 0 2 0 4 1 2 2 0 0 
Educational Codeforces Round 18 and laters are nicely organized in this blog (https://mirror.codeforces.com/harbourspace).
Special thanks to shahidul_brur for his kind update on this event.
I failed to manage any good resource on 2-SAT that illustrates printing solution for the value of each variable.Basically, I am stuck with this problem: lighoj — 1251 — Forming the Council http://www.lightoj.com/volume_showproblem.php?problem=1251
But how can I decide value of each variable?
Thanks in advance ...
Lesson :
Moral : Avoid fraction as much as you can.
Given a tree, you have to remove exactly k edges.Now you get k+1 subtrees. Each has a diameter. You have to say x = maximum of all the diameters. Now you have to minimize x removing exactly k edges.he tree has 50,000 nodes. Can anybody help me with some idea so that I can find a way to solve it? T
I just found that topcoder problem archive can not be filtered by probability category. But it has some good practice problems with tutorials for mastering probabilities. Here is the list of some basic and intermediate level problems(div2 500+div1 250) + (div2 1000). Problems are in ascending order of points, so you can attempt them in the order they appear in the list.
It happened to me many times that I submitted my solution without commenting out freopen and got compilation error! How virtual judges determines that I am using freopen/fopen? Interesting part is, I use - #define filein(x) freopen(x,"r",stdin) - #define fileout(x) freopen(x,"w",stdout)
it compiles when I do not call them. but it gets compilation error when I use filein("input.txt"); My question is, is it should be compilation error even though I use it! How they detect it!
Today I found a very interesting fact. int gcc, If you write cout << 5/0 << endl; it will cause a division by zero exception and get RTE. if you write cout << 5.0/0.0 << endl; it will output nan!!!!!!!! cout << atan(5/0) causes RTE while atan(5.0/0.0) causes correct output!
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2767
I am stuck on this problem. I can't formulate the recurrence relation exactly. Can anybody help me to formulate the recurrence relation,please? I can think of three state recurrence f(n,k,largest) = how many was we can express n as sum of k distinct integers where none of the integers is greater than largest. If somehow I could compress the last state(largest) by a and k , I could use matrix exponentiation. But how can I eliminate this state?
This post is only for newbies. A very common trick with Cumulative Sum + BIT is discussed with some examples and problems. Here is the link Thanks for reading.
problem link: http://www.lightoj.com/volume_showproblem.php?problem=1390 my code: http://pastebin.com/gZmFux20 verdict : WA My idea: did a topo sort to find an order then ran a dfs and marked cross edges and removed them. What did i miss !!!
I am trying to learn 2-SAT. All I found is a google translated e-maxx.ru and a wekipedia page. But I could not understand all of them. I understand the graph construction and the impossible case, why and when it does not have solution. its clear to me . But I can not understand the topo sort / start time finish time part inside it. What else information can we extract form 2-SAT besides satisfiable/not?
I have learned suffix array from this pdf:- Suffix arrays – a programming contest approach Adrian Vladu and Cosmin Negruşeri (appearedin GInfo 15/7, November2005)
Whatever there are some very good problems discussed in the pdf , and I want to practice them,test them with my code. Unfortunately I don't find those problems in any OJ or somewhere else to test them. Because some of the descriptions look like "training camp 2003" , i don't know which training camp or where to go. If somebody knows the source of the problems used in this article , please let me know. Sorry for such a large post.
If you are just learnt suffix array, try those problems discussed in this article. those are really awesome.
There are two kinds of operations that you will be instructed to perform:
This post is for those beginners who want to learn and practice matrix exponentiation. I am just here to share my idea on a very basic problem form lightoj(1142).
Task is simple A + A^2 + A^3 + ... + A^k =? where A is a n*n matrix.
Mr. 'Jotishi' is a superstitious man. Before doing anything he usually draws some strange figures, and decides what to do next.
One day he declared that the names that contain a string S as substring is unlucky. For example, let S be 'ab', then 'abc', 'cabe', 'pqqab', 'ab' etc are unlucky but 'ba', 'baa' etc are not.
So, he gives you the string S and asks you to find the number of names of length n, which are lucky, that means you have to find the number of strings that don't contain S as substring.
Input Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 109). The next line contains the allowed characters for a name. This non-empty line contains lowercase characters only and in ascending order. The next line contains a string S (1 ≤ length(S) ≤ 50), and S contains characters from the allowed characters only.
Output For each case, print the case number and the total number of names that don't contain S as substring. As the number can be very large, print the number modulo 232.
Sample Input Output for Sample Input 3 3 ab ab 4 acd ca 5 ab aaa Case 1: 4 Case 2: 55 Case 3: 24 //http://www.lightoj.com/volume_showproblem.php?problem=1268
Given 50 integers.Their sum will be less than 5*10^5. We have pick a subset from those numbers and distribute then into two arrays.The sum of integers in both array should be equal.If there are multiple solution we have to maximize the sum.If not possible report that.
Sample: 3 3 4 7 Case 1: 7 3 10 9 2 Case 2: impossible 2 21 21 Case 3: 21 9 15 15 14 24 14 3 20 23 15 Case 4: 64
Constraints: Time Limit: 4 second test cases: 100.memory limit: 32MB
Original Problem:
I came up with a recursive idea with two states (current_position,current_absolute difference) and three choices,(I will skip number at current position,I will take it in set A,i will take it in set B). I also tried to convert it in iterative but couldn't really do it. Can anybody help me with an idea to this problem.
