### simp1eton's blog

By simp1eton, 5 years ago, ,

Hi all,

May I know if anyone knows an efficient way to write iterative dfs? I am asking this because I am writing a program that has to deal with extremely large rooted trees. Even if I increase the stack limit, I think recursive dfs will be much slower than iterative dfs in this case due to the numerous function calls. Therefore, I implemented an iterative dfs as follows.

Note: the tree is rooted tree (edges point from parent to child), so I do not check if vertices have been visited.

vector <int> graph[MAXN];
stack <pair<int,int> > S;

S.push(pair<int,int>(TREE_ROOT,-1));

while(!S.empty()) {
pair<int,int> cur = S.top();
S.pop();
cur.second++;
// do stuff
if (cur.second < graph[cur.first].size()) {
S.push(cur);
S.push(pair<int,int>(graph[cur.first][cur.second],-1));
}
else {
//do more stuff
}
}


I am not sure if this is the best way to implement what I have. In practice my performance is not that good. Does anyone have a better implementation? My main concern is with speed.

Thank you!

• -17

By simp1eton, 6 years ago, ,

Hi,

Does anyone know how to create mashup contests using some problems from Polygon? I created some problems on Polygon but it seems that I cannot access them here on codeforces.

Thank you very much!

• -2

By simp1eton, 8 years ago, ,

I recently found this article online, and found it pretty interesting, so I thought of posting it here.

What other programming slangs do you normally use?

• +19

By simp1eton, 8 years ago, ,

Hi all,

I refer you to the problem Lemmings from VK Cup Round 2.

I wrote a binary search solution, and I set my EPSILON value in binary search to 1e-12. My code is given here.

However, I still get wrong answers. For one testcase, the optimal solution will give 9.999999^-5, but my solution gave 0.0001. Can someone help me and tell me what I should do?

Also in general, may I know what most coders do when they need to have extremely accurate floating point values? I don't like coding fractions D=.

Thank you very much!

EDIT: I read the analysis, so I changed my EPSILON to 1e-18. But then I get TLE. Afterwards, I changed my code so that I run 90 iterations of binary search (Code here), but I still get wrong answer on the same testcase (testcase 12)!!

• +5

By simp1eton, 8 years ago, ,

Hi all,

I refer you to C Lumberjack in EC 2012 (Link: http://ch24.org/static/archive/2012/2012_ec.pdf).

I have a question regarding this problem. In the problem statement, it is stated that the order in which trees are cut may matter. However, I am unable to find a example if which this is the case. Could someone help me understand why this is so or give me a small example that I can use to understand the situation?

Also, I have an alternative solution that gives wrong answer for large testcases, but I am unable to figure how why it fails. The solution is as follows.

Let L[x] denote the leftmost tree that will fall if tree x is pushed to the left.

Let R[x] denote the rightmost tree that will fall if tree x is pushed to the right.

Let F[x] denote the minimum number of cuts needed to cut down EXACTLY all the trees from 1...x (this means that cutting down the trees from 1...x must not let other trees fall)

Firstly, we initialise F[x] to infinity. Afterwards, we run a for loop for i from 1 to N, and we do the following updates.

F[i] = min(F[i], 1 + F[L[i]-1]); //If tree i is pushed to the left

F[R[i]] = min(F[R[i]], 1 + F[i-1]); //If tree i is pushed to the right

I think an assumption implicit in this DP solution is that the ranges of the trees I pushed down do not overlap. Therefore, the order in which the trees are pushed does not matter.

• -3

By simp1eton, 8 years ago, ,

Hi all,

I was wondering, is it possible for us to have access to full testcase. Sometimes I get a certain testcase wrong, but I cannot figure out why because the testcase is cut off, and the important part of the testcase is (probably) something after the "...".

• +56

By simp1eton, 8 years ago, ,
Hi all, I would like to ask the following qn:

In a computer, will

x / (a * b * c * d * e)

give a different solution from

x / a / b / c / d / e

where x,a,b,c,d,e are all integer data types? Since values are rounded down, I was wondering if that would cost the 2nd method of division to reach a smaller value than the 1st method if too much rounding is done.

Intuitively, it seems that it should not matter, but I cannot really prove it. Can someone help me out? Thanks!

• 0

By simp1eton, 8 years ago, ,

Hi,

I was doing the problem D-Power Permutation on CodeChef. The problem statement is given below:

http://www.codechef.com/problems/DPOWPERM/

I coded a PIE solution, but I kept getting TLE on the CodeChef server. I tried running on 10 testcases of max N and max D and randomised bijection on my own computer, but I got the result in 0.016 sec. Can someone help me out and tell me what is wrong?

My code is given below:

http://pastebin.com/mZcEaGcJ

• 0

By simp1eton, 8 years ago, ,
Hi all,

I have some problems with outputting long double.

Here is my code for Yandex Round 1 Problem C Petya and Tree:

http://pastebin.com/sHKuXg15

I submitted this code but got WA for testcase 1, even though it worked on my com. In the end, I realised that I cannot printf long doubles (something similar to printf long long int?), so I changed to cout. However, in that case it seems that I started to output integers :(. All my decimals places got cut off. Can someone help me?

• 0

By simp1eton, 8 years ago, ,
Hi,

For the past few days, whenever I tried to load Codeforces, I get pages that look like this:

http://imageshack.us/f/217/91805687.jpg/

http://imageshack.us/f/12/76055889.jpg/

Does anyone know what is wrong, and how I can fix it?

• +1

By simp1eton, 8 years ago, ,

Hi all,

I am trying to solve the APIO problems. The problems and the contest data can be found here:

http://apio2011.inoi.ir/?page_id=132

I can't seem to find the editorials anywhere, so I hope that you can help me out. Thanks!

Q1:

I am not sure how to solve this problem. I was able to find the solution in this thread:

However, it did not state how to solve invalid cases. Can someone help me?

Q2:

I was only able to solve the 60% case with a BFS. I think that to get 100%, you need to do some line sweep, but I am not sure how you can do so. Can someone help me?

Q3:

I really do not have much ideas for this problem. I could only solve the case for strings up to 3 letters long by bruteforce.

• 0

By simp1eton, 8 years ago, ,
Hi all, Are you experiencing extreme lag? I need to wait for a few minutes before the pages load :(

• +11

By simp1eton, 9 years ago, ,
Hi,

May I know how do I add someone as friend, so that I can see his score when I click on friend's ranking? Thanks!

• +5

By simp1eton, 9 years ago, ,
Hi all,

I was recently looking through problem E of Codeforces Beta #64. I finally understood how it works. I have a similar problem here that I am not sure how to do. Can someone help me?

The problem statement and testdata can be gotten from the links below.

Problem Statement: http://dl.dropbox.com/u/1872148/chocolate.pdf
Testcases: http://dl.dropbox.com/u/1872148/chocolate.zip

Thank you once again!

• 0

By simp1eton, 9 years ago, ,
Hi all,

I wonder if there is a place listing the urls to all the facebook hackercup problems. I couldn't seem to find such a page on the hackercup page. Thanks in advance!

• 0

By simp1eton, 9 years ago, ,
Hi all,

I was coding Codeforces Beta Round #59 (Div. 2) Problem C and encountered some problems. Can someone please help me? Thanks!

Problem: http://www.codeforces.com/contest/63/problem/C
Code: http://pastebin.com/F5E4pJVx

I got this testcase wrong:

Testcase:
87954 0 15638 0 18204 0 28293 1 13598 0 10894 0 16324 1 20572 0 1
Incorrect data
Need more data

• -1

By simp1eton, 9 years ago, ,
Hi all,

I recently tried solving this problem: Beautiful Numbers (url: http://www.codeforces.com/contest/55/problem/D).

I managed to get it AC( solution: http://pastebin.com/0kBFqTqu)

However, I am not sure why it works. In my initial solution, I need to reset my DP array each time, because I thought that my answer will change for different As and Bs. However, it seems that I will still give the correct answer even if I do not reset my arrays! Does anyone know why?

My DP recursion is f (prefix, N, LCM, five, seven, eight, nine)

This will return the number of beautiful numbers between A and B in the range prefix*10^N to prefix * (10^(N+1)-1), whose prefix has a lowest common multiple of LCM, and has remainder five when divided by 5, remainder seven when divided by 7 and so on ...

My dp array is dp[N][LCM][five][seven][eight][nine]. This is due to the observation that if N,LCM, five, seven, eight and nine are kept constant, then all prefixes, if their range (defined as prefix*10^N to prefix * (10^(N+1)-1)) is within A and B, will give the same answer. Therefore, I can reduce the number of states in my DP.

As you can see, the variables A and B are included in my definition of my DP. Therefore, I thought that once A and B changed, I will have to reset my arrays and work out the answers again. However, it seems that I do not have to do so! Does anyone know why?

• 0

By simp1eton, 9 years ago, ,
Hi all,

I have a suggestion. I wonder if it is possible for there to be a "My Submissions" page listing all your previous submissions. Currently, I need to click on the contest to see my submissions, and only my submissions to that contest will be shown. Allowing all the submissions to be shown in one page will allow greater convenience when one needs to refer to previous codes one has written.

Adding on to the suggestion above, I notice that there is no "My Submissions" tab when I click on problems under  "Problemset". Implementing this will also allow users to refer to their codes for that problem more conveniently.

Thanks!

• +9

By simp1eton, 9 years ago, ,
Hi all,

I have a question regarding the Tarjan's algorithm for finding strongly connected components. The Tarjan's algorithm that I am taught for finding strongly connected components is as follows:

1. Start from any arbitrary vertex.
2. DFS from that vertex. For each node x, keep two numbers, dfs_num[x] and dfs_low[x]. dfs_num[x] stores when that node is visited, while dfs_low[x] = min( dfs_low[k]) where k is all the children of x that is not the directly parent of x in the dfs-spanning tree.
3. All nodes with the same dfs_low[x] are in the same strongly connected component.

However, there seems to be a problem. Suppose the following testcase.

6 -> 5 -> 4 -> 3 -> 2 -> 1

Suppose I process the nodes in this order {1, 2, 3, 4, 5, 6}. Then, we notice that all the nodes will have dfs_low value 1, implying that all are in the same strongly connected component. Obviously that is not true.

To solve this problem, I think what needs to be done is that the dfs needs to be started from nodes with no incoming edges ie the nodes that will be the roots of the dfs-spanning tree.

However, that seems to require require much more computation. Firstly, a for loop is needed to find all nodes with no incoming edges. Then, dfs will be run from these nodes. Then, another for loop is needed to find any unvisited nodes (these nodes will be in a cycle) and dfs needs to be run again. In total, the runtime will be something like O(2*V+E).

Of course, essentially only one dfs is run (since the dfs visits different components of the graph). However, I wonder if there is an easier way to solve this problem, so that instead of breaking the dfs into two parts, only a single dfs needs to be run.

• 0

By simp1eton, 9 years ago, ,
Hi all,

I have a question about the maximal convex hull polygon. You are given N points on a 2D plane. Each point has a value X. You want to find the convex polygon such that the sum of the value of the points on the perimeter of the polygon is maximal. Output the maximal sum.

I have an N^4 DP solution. as follows.

I choose a point i and sort all the other points around this point according to angle (similar to convex hull graham scan). Then, I write the following bottom-up dp formulation:

DP[B][A] stores the best convex polygon with the last two points at B and A.

Then I calculate DP[C][B] for all C such that C-B-A is convex and I-C-B is convex.

The DP has a runtime of N^3. As I am doing this DP for all vertices I, the algorithm has a total runtime of N^4.

However, I think that there is a better algorithm with a runtime of N^3. Does anyone know this algorithm? Can someone give me some hints?

• 0

By simp1eton, 9 years ago, ,
Hi all,

I have a few problems in this contest that I am not sure about. Can I please have some help? Thanks!

The first problem is problem B (School).

I have no idea how to do this problem. Actually, I dont really understand the question as well :(. Can someone help me?

Problem C (Dancing Lessons):

I wrote my code, but it keeps failing on testcase 11 and I dont know why. The outline of my algorithm is as follows:

First, I find all the immediate pairs of boys and girls and push them all into a set. The pairs in the set are sorted according to the conditions given.

Then, if the set is not empty:
1) I take the best pair out of the set.
2) If both members of the pair have not gone off for the dance yet, I add this person into the dance. Then, I add the pair that envelopes this pair into the set (for example, if I remove pair (4,5), I add pair (3,6) if this pair is available).
3) If one member is present, I expand it until I hit someone. Then I push it into the set.
4) If both members are gone, I just remove this pair from the set.

I keep doing this. Below is a link to my code.

http://pastebin.com/qAipmk63

Can someone help me and tell me what is wrong? :(

• 0

By simp1eton, 9 years ago, ,
Hi all,

I refer you to the following problem.

http://www.codeforces.com/contest/10/problem/E

I tried reading the codes of people who solved the problem, but the codes are pretty cryptic to me. Can someone please enlighten me? Thanks :)

• 0

By simp1eton, 9 years ago, ,

• 0

By simp1eton, 9 years ago, ,
Hi all,

I was trying to do this question, but got stuck, so I wonder if you guys can give me some help. Thanks :)

https://www.spoj.pl/problems/SHOOTING/

My idea was to split the numbers up into two groups, positive and negative. Then I sort the negative numbers and pair them up. The two biggest (in terms of absolute value) will be paired, the 3rd and 4th biggest will be paired, and so on. I want to do this because I want to maximise my value, so I want to remove all my negative numbers while at the same time increasing the values of the numbers.

After I changed all numbers to positive, then I think I can use a greedy solution. I sort all the numbers in descending order and multiply the first X elements together such that there are M-1 or more elements left. The remaining elements will be distributed among the remaining targets while the first X elements are multiplied together to get the huge score.

However, I got into many difficulties trying to implement it, because pairing does not always works (there might be odd number of negative numbers), and there are weird cases and 1s and 0s (multiplying the first X elements by 1 does not increase the value. Also, I might want to pair a negative number with 0 so that it will not bring down my score).

Can someone help me? Thanks in advance.

• 0

By simp1eton, 9 years ago, ,

This problem is COCI 2009/2010 Contest 3 Problem 5. I went to look at the solution but do not really understand the solution, so I wonder if anyone here can help me.

I went to the COCI website (http://www.hsin.hr/coci/) and downloaded the solution and went to look at it, but I don't really get the solution. I ran it on the sample and this is what I got.

In the sample, there are 10 dwarfs:

1 2 1 2 1 2 3 2 3 3

Let's assume that we have splitted the segments into (1,8) and (9,10). Let's call them segment A and B respectively. We see that A's candidate is 2 and the count is 0. We see that B's candidate is 3 and the count is 2. Therefore, when we merge these two segments, the candidate is 3 and the count is 2. But if we count the number of 3s, there are only three of them out of 10.

So am I missing something here? Is there some additional steps required that is not mentioned?