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!

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!

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?

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

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.

Thanks in advance for your help!

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 "...".

Thank you for your help!

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?

Thanks in advance!

My code is given below:

http://pastebin.com/mZcEaGcJ

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:

http://apps.topcoder.com/forums/?module=Thread&threadID=707486&start=0

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.

Thanks in advance! =D

8

7954 0 1

5638 0 1

8204 0 2

8293 1 1

3598 0 1

0894 0 1

6324 1 2

0572 0 1

Incorrect data

Need more data