tag:blogger.com,1999:blog-29632375.post786840622393277825..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: Topcoder open 2012: Round 1BUnknownnoreply@blogger.comBlogger8125tag:blogger.com,1999:blog-29632375.post-74518071079526632852012-04-27T20:40:33.534-07:002012-04-27T20:40:33.534-07:00I don't get the time concept. Why do you go th...I don't get the time concept. Why do you go through the loop with t from 1 to 3600*50*2. I realize 50 and 3600 are the max bounds over the number of jobs and the time for each job, but I don't get your concept. What does that 'time' and the time limit exceeding stand for?Amit Ruparelnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-6962072566886103152012-04-27T13:42:24.084-07:002012-04-27T13:42:24.084-07:00It is not so important because there is an editori...It is not so important because there is an editorial with an easier solution already.<br /><br />But anyway, without knowing what is it that you can't understand it is difficult to know what to elaborate. <br /><br />Either way, let us say you begin with one Fox. Since we are in a rush, there is no reason to wait without doing nothing, so we have to decide: will the Fox reproduce or work on a task? If it splits, there will be two foxes left after some time, and each of the foxes can split or work. The other thing is that it is never necessary for a Fox to split after doing the homework. Because you can just swap the order of both processes and you will get either a better result or the same result.<br /><br />So in fact, what we do is split fox after fox , some in parallel until we get n foxes left, then we do the homework.Whenever a Fox splits, we can see it as a node in a tree becoming two children. This means that the Foxes make a binary tree. You will notice that the shape of the tree will determine the total time. There are many different binary trees with n leaves.<br /><br />So, how to find the optimal way? What I did was to sort the durations of the homework in non-increasing order and put time limit. After this time limit is set, then there is a point in time in which you need to stop splitting one of the nodes you got left and instead order it to do the available homework that takes the most time. (The homework duration + the current time exceed the time limit), so we order the Fox to do homework, we will get some Foxes and homework remaining, and we must continue until either all homework is done or there is a piece of homework that needs to be done but we could not reproduce enough Foxes (In which case, we need to increase the time limit and repeat).vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-27817944293873910702012-04-27T10:51:00.593-07:002012-04-27T10:51:00.593-07:00I've been trying to read your explanation for ...I've been trying to read your explanation for the 500-pt and I still don't get it. Any chance you can elaborate more? Thanks!Amit Ruparelhttp://www.facebook.com/ruparel.anoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-29319306281127913072012-04-08T07:56:51.056-07:002012-04-08T07:56:51.056-07:00I think you initialize your dp with 1000, but then...I think you initialize your dp with 1000, but then use it as infinite when picking the best result.<br /><br />But if the test case does not have a solution, there will be many states that always stay marked with 1000, and thus you will keep executing those states and doing a lot of processing.<br /><br />Just use 1000000 to mark a state as not-visited and 1000 to mark it as impossible.(initialize dp[i]=1000000 and ret=1000)vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-80996647982143458462012-04-08T07:36:05.936-07:002012-04-08T07:36:05.936-07:00class FoxAndPhotography {
public:
int dp[1<&l...class FoxAndPhotography {<br />public:<br /> int dp[1<<16];<br /> int n;<br /> int front[16];<br /> int back[16];<br /><br /> int cal(int subset) {<br /> if (dp[subset] != 1000) return dp[subset];<br /> int m = __builtin_popcount(subset);<br /> int left = 0;<br /> int ret = 1000;<br /> for (int i = n - 1; i >= 0; i --) {<br /> if (!(subset & (1 << i))) {<br /> if (back[n - i - 1] > front[m]) {<br /> ret = min(ret, cal(subset | (1 << i)) + left);<br /> }<br /> left ++;<br /> }<br /> }<br /> dp[subset] = ret;<br /> return ret;<br /> }<br /> <br /> int getMinimumSwaps(vector heightsFront, vector heightsBack) {<br /> n = heightsBack.size();<br /> for (int i = 0; i < n; i ++) {<br /> front[i] = heightsFront[i];<br /> back[i] = heightsBack[i];<br /> }<br /> for (int i = 0; i < 65536; i ++)<br /> dp[i] = 1000;<br /> dp[(1 << n) - 1] = 0;<br /> int res = cal(0);<br /> if (res == 1000) return -1;<br /> return res;<br /> }<br /><br />Hi! I got your idea and try to implement. My implementation is almost the same with yours but I kept getting TLE for testcase which has 16 elements.<br />Would you mind explaining for me what I did wrong here ?<br /><br />Thank you in advance.trungdanoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-2613804514648450652012-04-08T06:34:35.916-07:002012-04-08T06:34:35.916-07:00Got it! Thanks once again ^^Got it! Thanks once again ^^Brunonoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-78492253997283405682012-04-07T16:44:41.165-07:002012-04-07T16:44:41.165-07:00Yes, this is the part that took me the most time t...Yes, this is the part that took me the most time to do.<br /><br />Let us imagine you have already decided that ABCD have to change their positions to DCBA, what is the minimum cost to do this?<br /><br />You will eventually find that it is a good idea to first move D to his position, then C, then B. Or maybe the opposite and first A, then B, then C..<br /><br />Let us say for front positions ABCDEFGH that one state is like this:<br /><br />(2, ABxDExGH)<br /><br />The x are people that we already moved to their locations, so the mask will be like 00100100. 2 is p in the explanation, but as an optimization, it will be equal to the number of 1 bits in the mask (subset).<br /><br />So, in reality the state represents the following thing:<br /><br /><br />CF ABDEGH<br /><br />C and F are already in their positions. You now have to decide which of ABDEGH to move to the third position. But note that the cost to move one of them to the third position depends on the number of people that have not moved to their seat yet. For example, if we want to move E to this position:<br /><br />ABxDExGH There are 3 people between E and the third position (AB D) we ignore the people that are already in the subset (mask).<br /><br />So the cost to move E by swapping is behind = 3.<br /><br /><br />Maybe I should have called that variable "totheLeft" instead of "behind"<br /><br />After moving E, the stuff becomes ABxDxxGH, that means our new mask is 00101100.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-20811959100742273352012-04-07T16:36:12.693-07:002012-04-07T16:36:12.693-07:00Hi could you explain the solution for the 1000? I ...Hi could you explain the solution for the 1000? I could not understand very clear, specifically that 'behind' counter :p<br />What if the p is ahead the position i? And what about the people already matched between p and i?<br /><br />Thank you!Brunonoreply@blogger.com