KAN's blog

By KAN, 4 years ago, translation,

I'm sorry for the delay, it took some time for me to translate analysis to English.

Problem author: KAN, preparation: KAN.

Problem author: KAP, preparation: KAP.

Problem author: KAP, preparation: demon1999.

Problem author: ZhNV, preparation: ZhNV.

Problem author: SYury, preparation: kuzmichev_dima.

Problem author: KAP, preparation: KAN.

• +21

 » 4 years ago, # | ← Rev. 2 →   +5 After waiting for a long time,the tutorial is finally ready.
 » 4 years ago, # | ← Rev. 2 →   +2 C was quite hard to understand, time zones are really confusing mind :Dthanks for cool task )
•  » » 4 years ago, # ^ |   0 Can someone please explain it again, thanks.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Let's find out which timezones will participate when the local time in TZ#1 is 1 hour. s =minimum time of start f =maximum time of finish => f-1=maximum time of start.If time is 1 in first time zone then in the second time zone is two, in the third is 3...Okey, let's make it on a sample: 51 1 1 1 12 4Which time zones will participate? TZ#2 and TZ#3. TZ#4 won't participate because their local time will be 4. So the contest will end at 5, which is not good for us.Now let's find out: "How many people will be in?" Answer is obvious a[2]+a[3], which is a[s]+a[s+1]...+a[f-1].Now let's find which timezones will participate on h=1...n; (h=local time at TZ#1)Let's make it again on sample:51 1 1 1 12 4h=1: a[2]+a[3]h=2: a[1]+a[2]h=3: a[5]+a[1]h=4: a[4]+a[5]h=5: a[3]+a[4]More formally for (h=1 to n ) {beg=s-(h+1)if (beg<1) beg=n+beg;end=f-h;if (end<1) end=n+end;curans=sum(beg->end)if (curans>ans){ans=curans;time=h; }} This is an O(n*(f-s)) solution. Because each time we calculate sum from the beginning. But we don't need to calculate each that way. We can save previous sum. And the current sum will be:cursum=(previoussum+a[begin])-a[end%n+1];Complexity O(n)
•  » » » » 4 years ago, # ^ |   0 Thanks!
•  » » » » 2 years ago, # ^ |   0 When comments are explains things better than the actual editorial.Well, No offence to the editorial.
•  » » » » 16 months ago, # ^ |   0 how did you get to know beg=s-h+1 and end=f-h??
•  » » 4 years ago, # ^ |   0 Can someone explain problem C with example given in the problem.
 » 4 years ago, # |   +3 Using lemmas 1 and 3 from E editorial it is easy to prove that we can use ternary search as alternative way to find optimal prefix for each query with type = 2.
•  » » 4 years ago, # ^ |   0 Can you please explain the ternary search idea ? At first glance on this problem I thought a ternary search idea but while implementing it, I found some difficulties. Then I solved it using binary search. Thanks in advance.
•  » » » 4 years ago, # ^ |   +3 Well, let store all x in x[i], and while adding i element we will calculate prefix sum for first i elemets (sum[i] = sum[i - 1] + x[i]).Then, it is obvious that we should always use x[1] and x[cnt] element (where cnt — how many elements we have at the moment). So, we take x[cnt] and then search best answer choosing what prefix should we use from [1;cnt - 1].Define get(i) as function returns max(i) - mean(i) (what we want to maximize). max(i) = x[cnt] for any i, mean(i) = (sum[i] + x[cnt]) / (i + 1).Suppose we have best answer with i = p. Then, get(i - 1) ≤ get(i) for any i in range [1;p], and get(i) ≥ get(i + 1) for any i in range [p;cnt - 1]. We can use it to search p in [1;cnt - 1] with ternary search (and answer for query will be get(p)): http://codeforces.com/contest/939/submission/35440173
 » 4 years ago, # | ← Rev. 7 →   +19 I would like to share What I learnt from question E. Solution with Queue, O(n) in worst case scenario, uses long double, gets TLE , 3 seconds Solution with Queue, O(n) in worst case , uses Long long instead Long double, Gets Accepted , 608 mili seconds Solution with multiset, O(n*log n) in worst case, uses long long instead of long double , gets Accepted , 654 mili seconds Conclusion : 1) O(N) solution with 'long double' data type is slower than O(N*log N) solution with 'long long' data type. type. (still runtime depends on how many operations we are doing in each cycle)2)Question E is pretty straight forward, There was no need for Binary Search or Ternary Search. 3)Always prefer to use "long long" or "int" , instead of "double" or "long double". Because simple operations like Addition or subtraction becomes very slow on these data types. GL & HF :) .
•  » » 4 years ago, # ^ |   0 Q·log1.5Q solution with long long got accepted in 951 ms
•  » » » 4 years ago, # ^ |   0 yeah, but still better than using Long double :D .
 » 4 years ago, # |   0 I can't understand problem C, In example 1 it is said that contest should start at 3 hours at time zone 1 that would be 1 hour in time zone 2 and 2 hour in time zone 3. But As stated by problem time at ith time zone should be i if time at 1 is 1 hour. So the time at second time zone should be 4 hours and third 5 hours.
•  » » 4 years ago, # ^ | ← Rev. 5 →   0 hmm, you should imagine that like in real life, except it only has n hours ( not 24 hours) and doesn't have 0 hours. Here is an example how that goes in time zone 1 if we have n=4: TZ1: 1 2 3 4 | 1 2 3 4 | 1 2.. and so on. Meanwhile, in TZ2: 2 3 4 | 1 2 3 4 | 1.. and so on . Hope you can understand, my English and explanations is not good at all =))) .
•  » » » 4 years ago, # ^ |   0 I got it, thanks.
 » 4 years ago, # |   +1 Shouldn't in Task E, Lemma 3 should say f(i) is non-increasing?
 » 4 years ago, # |   +8 Anyone please explain or share the solution idea of problem F — Cutlet. I think another editorial is needed for understanding the given editorial for this problem.
•  » » 4 years ago, # ^ |   +8 I'm not sure what the editorial is saying either, but let me explain my solution. Let the two sides of the cutlet be A and B. Consider the case where we have two availability intervals [li, ri] and [lj, rj] with i < j. Let's say we enter interval i with side A, flip to B during interval i, stay at side B until interval j, and flip to A during interval j. If we only consider these two flips, then the amount of time we had side B would be in the interval [lj - ri, rj - li]. If we have two more intervals x,y where i < j < x < y, we can perform the same flip as above between i and j with x and y as well (ie. A -> flip at x -> B -> flip at y -> A). In fact there are no conflicts regardless of how we flip things at i, j, x, and y as long as they are of the form I described earlier. Let's build a graph as follows. Each interval becomes a vertex. Let i < j, we connect interval i to j with a directed edge of length 1 and value [lj - ri, rj - li]. Connect the source to all intervals with value [li, ri], and connect all intervals to the sink with value [2n - ri, 2n - li]. These edges represent the time the cutlet spends at side B. We also have to add the side A edges, which are just duplicates of these with value [0,0]. Value here means the time the cutlet spends on side B. Now, taking an edge from i to j means we do the flips A -> flip at i -> B -> flip at j -> A. This gives some time in the value of the edge. The value of a path whose edges have values [l1, r1], [l2, r2], ... is simply [l1 + l2 + ..., r1 + r2 + ...]. IF we add the restriction that we can only have The solution to the problem is now finding the shortest path from the source to the sink whose value contains n, taking alternating side A and side B edges (ie. we can have the cutlet on side B for time n). To deal with the case where we might have to flip multiple times in one interval, first we note that we want to flip at most twice in a given interval. So we add side B edges from i to i with value [0, ri - li]. This doesn't cause a problem because we must take alternating side A and B edges. However, this only considers cases where we do A -> flip at i -> B -> flip at i -> A, but this is sufficient because the B -> flip at i -> A -> flip at i -> B case cancels out with this one. To find the shortest alternating path, you can use Dijkstra with an extra flag that says whether to take a side A edge or a side B edge. Also store the value for each visit. Whenever we reach the sink, check to see if the value contains n, if it does, then we found the answer, otherwise, skip this path and keep looking.
 » 4 years ago, # |   0 Can some one explain the E problem in a more detailed way?
 » 4 years ago, # |   0 How to solve D if we can apply spells only on first string?
•  » » 4 years ago, # ^ |   0 Applying spells only on first string is equivalent to applying spells on either strings since spells are bidirectional in this case.
•  » » » 4 years ago, # ^ |   0 What I meantInput2abba Output2a bb a
•  » » » » 4 years ago, # ^ |   0 In that case output will be the number of positions where S1[i]!=S2[i].
 » 4 years ago, # |   0 Why has C been tagged as two pointers and binary search? Isn't it misleading, when you just have to use the prefix sum?
 » 4 years ago, # |   0 For problem E Lemma 3: It should be f(i) is non-increasing for increasing i, for M(i) to have a maxima. If f(i) = M(i + 1) — M(i) is decreasing or non-increasing it implies M(i) has a minima. In the proof statement -f(i + 1) - f(i) ≤ 0, this means that f(i) does not decrease when i increases is simply wrong. It means f(i) does not increase.
 » 2 years ago, # |   0 Problem D. can be done using DSU. iterating from left to right (from i=0 to n-1), if s[i] and t[i] are of same set, then its useless to add them in the answer, since there already exists a path between them in that set, and that is s[i] to leader, and leader to t[i] (and that had already been counted earlier). But if both have different leaders/sets, then both sets have to be merged, increasing the final answer by 1, also save the leader of those two sets as a spell. See my submission.
•  » » 23 months ago, # ^ |   0 can you please explain it a bit more iam on the learning stages of dsu , tho' i got your point a lil more explanation is needed maybe thank you ...P.S -- this is my first dsu question...thank you!
•  » » » 23 months ago, # ^ |   0 Lol, he posted it 5 months ago
•  » » » 22 months ago, # ^ |   0 using dsu we are checking if both x & y are in same connected component or not if they are not in same connected component then we make them in same connected component by merging them together you can check my submission 86800226 i have added comments for you in my submission
•  » » » » 22 months ago, # ^ |   0 thank you for the reply bro ! i surely learned something:)
•  » » » » 22 months ago, # ^ |   0 bro i also want to learn dsu ....... can you share some resources to study DSU.THANXX IN ADVANCE
•  » » » » » 22 months ago, # ^ |   0
•  » » » » » » 22 months ago, # ^ |   0 thanxx a lot
 » 22 months ago, # |   0 how do we solve A?
 » 22 months ago, # |   0 How to solve A ? I realy dont understand
•  » » 22 months ago, # ^ |   0 We need to check whether a love triangle exists or not. To do so, it is sufficient to check for all i that whether the ith plane is a part of a love triangle or not. Let us say that the ith plane is A, f[A]=B and f[B]=C. if A is part of love triangle, then f[C] should be equal to A. Also f[C] = f[f[B]] = f[f[f[A]]] which should be equal to A, thus it is sufficient to check for all i that whether f[f[f[i]]]==i or not.
 » 20 months ago, # |   0 can someone help me with the process of visualisation for problem A ??
•  » » 20 months ago, # ^ |   0 NAHI
•  » » » 20 months ago, # ^ | ← Rev. 3 →   0 It's okay if you don't know the answer :) ;) There are other very helpful people from whom I might get a reply
•  » » » » 20 months ago, # ^ | ← Rev. 4 →   0 Yo what's up. I will try to give you a visual picture using mathematics.This problem can be thought as a graph problem and you want to find if there is a cycle of length (3).Lets assume that there is a cycle of length 3 and the corresponding indices are i, j, k. So this means that i->j->k->i, where x->y implies that an edge is there between index x and y.Now we have a cycle only if j == f(i) and k == f(j) => k == f(f(i)) and finally i == f(k) => f(f(f(i))).Thus we are done.
•  » » » » » 20 months ago, # ^ |   0 Ohh thanks, that was very intuitive... But how do you develop that thought process ?? I have been doing cp for more than 3-4 months now.. and my poor results pretty much say that I have had very wrong approaches.. what is the correct approach other than doing more practice? Like some smart tip using which I can learn better ?
•  » » » » » » 20 months ago, # ^ |   0 Look in my opinion, codeforces a, b, c are generally constructive or maths problems. So if you were/are good in maths at high-school level or have sit in some RMO or IMO you have a pretty-good chance to get to 1600 and above.Now how to develop thought-process is a very brilliant question to ask. I don't know exactly but maths is all about deductions, reductions and logical analogies.How to get better ? Take a problem and think about the possible directions that you can go into. Deep thinking in the initial 1 year in Cp is very needed as it paves a way to build upon the solid foundation that you have made by thinking deeply about problems and possible directions to go into. 
 » 16 months ago, # |   0 dang I created a graph and ran dfs on every node for problem A when I could have just used one if statement.