GlebsHP's blog

By GlebsHP, history, 3 years ago, , New problems will be added as soon as the analysis is ready. Tutorial of Codeforces Round #363 (Div. 1) Tutorial of Codeforces Round #363 (Div. 1) Tutorial of Codeforces Round #363 (Div. 2) Tutorial of Codeforces Round #363 (Div. 2) Comments (93)
 » 3 years ago, # | ← Rev. 2 →   You r a little bit of shit
•  » » Be a person who first solves.
•  » » wrong site buddy. this is not facebook!
•  » » » oh what?? wait...let me check...oh yeah...
 » 3 years ago, # | ← Rev. 2 →   The first test data of B is too weak......
 » 3 years ago, # | ← Rev. 3 →   Wow! There is so much to learn from these editorials. I made so many mistakes while solving the problems. Lots to learn yet. :)
 » Is problem B could be solved using mode? So the basic idea is you count mode for V[] and G[] then simulate the explosion using that modes as coordinate. I'm curious cause when I validate that way I found some corner case that's really tedious if I tried to fix them all.
 » Does C++ really have builtin tools to work with dates? As far as I know, it could only deal with timestamps (which might only store 32 bits, so the timestamps of 1012 given in the problem were too much for it to handle).
•  » »
•  » » It looks like the g++ used in Codeforces is 32-bit, so time_t is a 32-bit integer which cannot store 1012 :(Why not support 64-bit compiler Q_Q?
 » 3 years ago, # | ← Rev. 2 →   ....
•  » » 3 years ago, # ^ | ← Rev. 2 →   .....
•  » » » my code was accepted,but the B 2 2 .* *. is YES 1 1
•  » » » » In fact.I saw wrongly.I saw wrongly.I saw wrongly.
•  » » » » » ???????
•  » » » » You can place the bomb on a '.', so (1, 1) is also a correct answer.
•  » » 3 years ago, # ^ | ← Rev. 2 →   I followed very similar thought process as yours during contest :). However noting that f(0) = pi simplifies things :). Btw aren't B coefficients always 0?
•  » » » Btw aren't B coefficients always 0? Shit. I knew it should be less complicated :)
•  » » » » I still don't understand:D
•  » » The main clue I cannot get is that probability has a limit when steps -> infinity.
 » Love this kind of graph from problem D :D (i call it flower graph because the components look like flowers to me and i never knew this name functional graph)Problems with the same kind of graph:Joining Couples from South America ICPC 2012 : https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=4151BFFs from Google Code Jam 2016 1A: https://code.google.com/codejam/contest/4304486/dashboard
•  » » I believe they are also known as Pseudoforests, if you are interested.
 » I always get hit by TLE when dealing with bitmask dp questions, can somebody please help and point out which part did I wasted all the computing power? Thanks in advance.This time's Div2-EA practice of 8C I have done a while ago, also a bitmask dp question
•  » » If i understood your logic correctly, you are not using the memo table to avoid recalculations, you are just storing values there but still computing the same state more than once
•  » » » 3 years ago, # ^ | ← Rev. 2 →   I just added a line "if(dp[prev|(1<
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Great! :)I don't think there is any special way. You just have to keep in mind that moving to a next state usually means setting a new bit (using bitwise OR with some power of 2). You can use some defines to create a interface, i think thats the best way to hide the bitwise operations in the code: #define bit(i) (1<<(i)) #define set(mask,i) (mask |= (1<<(i))) #define get(mask,i) (mask & (1<<(i)))
•  » » 3 years ago, # ^ | ← Rev. 2 →   And another problem regarding Div2-F, I get the approach and tried to build a code for it, yet my sorting function fails to complete its' job. I suspect that it could be floating point problems, but nothing seems wrong with the angle even when checking the angle with setprecision(20)The code with an echo testI have to applaud on the great illustration of the test cases though, it helped me a lot in understanding the problem and the possible approach to solve the question. =DUPD: OMG my brain must be rotten during the contest... I've made a dumb mistake in the sorting function.
 » Can some one please explain the dp we have to use in Div2-E LRU.
•  » » DISCLAIMER: I AM ALSO NEW TO BITMASK DP SO WHAT I AM EXPLAINING COULD POSSIBLY BE WRONGSo, I believe that you have already understood why does the problem becomes "Choosing K items to be added at the end of the cache", so now we will need to use dp in order to find out the chances of picking up certain combination.In this bitmask dp, we store the states of each item: 1 representing it has been picked up and 0 as the opposite, then we combine the flags together. (That means, for n=3, if item 2 and 3 has been picked up, the flag could be 110 or 011, depending on implementation but I prefer using the rightmost bit as the first item).Similar to regular dp, bitmask dp also stores previously processed value for further processing to avoid reprocessing. In order to walk from state to state, we have to do some bitwise operation to set some flags active (i.e. picking up a new item). Remember to generate states efficiently and don't make the mistake I have made above.The answer for each item is the sum of dp[(k flags active)] which the item is also set active. At the end of the editorial it mentioned to take care of 0.0 probability (test case 13), and the chance of having not enough k items having non-zero probability (test case 17). Take care of these cases and you are done.http://codeforces.com/contest/699/submission/19267737My AC solution, again, I am new to bitmask dp so my implementation might be considered as unorthodox.
•  » » » I know what bitmask dp is. What is the recursive equation for the dp?? dp = what in terms of other dp
•  » » » » Let me try to explain: dp = dp*P/(P+P) + dp*P/(P+P) where P is the possibility of the first video, P is the possibility of the second video and P is the possibility of the last one. Note that the most significant bit is responsible for the last video, shows whether it is in the cache or not and the least significant bit is responsible for the first video similarly. If you still have any questions, please feel free to ask.
•  » » » » » I have a confusion. Isn't dp also not dependent on dp? you have 3rd and 1st video in the cache and then 3rd video is removed by the second video if second one is called? I am sorry I know I probably dont understand the state transitions clearly. Could you clear that up for me?
•  » » » » » » We are looking at the problem from the other end. Instead of finding out which videos are in the cache at the end, we start filling an initially empty cache with new videos until it's full.This way there's no removals since we stop processing once the cache is full.
•  » » » Thanks for your explanation. So, are we finding all possible sets (S) of size k from N elements (Removing 0 probabilities if present inside a set)? Then for each element v belongs to N, we find the probability as count(s belongs to S such that s has v in it)/Total possible sets ?So , to get all the sets of size k we use bitmaks? What information about the set is dp storing? Is it storing the probability of that set to occur?
•  » » » hi..any hints on how to solve div1d
 » 3 years ago, # | ← Rev. 2 →   Div1 C can also be solved by inclusion exclusion. We brute force for last occurrence of a[i] and then choose a mask of numbers which will appear on its right. This leads to a GP which can be trivially summed. We can use inclusion exclusion to remove overcounting. See my implemention for details
•  » » Can you give a detailed explanation please?
•  » » » » My solution was exactly the same.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   Can you explain this part in your code? ~~~~~ for(int l = 0;l+ln
 » For Div2 problem B, whichever cell we plant the bomb, it can destroy at most n+m-1 cells (the current row, the current column, minus the bomb cell which is counted twice). How about checking if( cur > n + m-1 ) before looking over the cells to find cur = cnt? Since the bomb can never destroys more than n+m-1 cells, computations needed can be reduced for test case where n=1000, m=1000, and the whole field is full of walls.
•  » » Correct. After counting all walls, if cur is 0, we can print out YES 1 1 and return. If cur > n+m-1, we can immediately print out NO and return.
 » 3 years ago, # | ← Rev. 3 →   For div2/C, I think there's a more straightforward greedy solution.If possible, then Vasya will not rest. So now we define pre = a, now = a,ans = 0.Let's iterate from i = 1. if pre == 0 : Vasya will get rest, ans++. if pre == now && now != 3 : Vasya will get rest at the i day, don't forget modify a[i] to 0 after increases the ans. if now == 3 : change a[i] to 1 if pre == 2, or 2 if pre == 1. if pre == 3, doesn't matter, Vasya absolutely will not get rest at the i day
•  » » Same solution here. For more explanation, here's the cases to consider by observation. When a[i] == 0 it's pretty clear that Vasya can do nothing but rest. When a[i] == 1 or a[i] == 2, the only concern is that Vasya wouldn't do the same task in the consecutive day, so a greedy solution here is that we can see it's always better to do the specific task in the first day and rest the other day and then work and then rest and so forth. To deal with a[i] == 3, if it's not 1(a bunch of 3)2 or vice versa, you can just turn 3 into anything you want without any rest. Next, we take a look at this sequence, 1212212, no matter it's the 4th or the 5th day Vasya chooses to rest, the answer remains the same (in fact Vasya rests at most 1 day to deal with a pair of consecutive task collision of any form), so for 1(a bunch of 3)2 and 1(a bunch of 3)0 and the identical sequences with 2 at the beginning, the greedy solution is that we change every 3 to the opposite task Vasya did from the previous day iteratively. Hope this is clear enough. Here's my submission by the way, 19243726
•  » » My Greedy Solution for problem C /Div 2 19276210
 » problem c div2 has a greedy solution also, here is my submission[submission:19270426]
 » I met a problem with Div2.E (Div1.C). When I calculate the value of dp[mask], it seems that I need to use dp[mask] itself to calculate dp[mask].For example, if there are 4 videos and the size of the cache is 3. dp means the probability of the first and the second videos in the cache. If we choose the first video again, the mask will still be 1100. It seems to be a "self reference". How can I deal with this problem?My English is not good. Sorry if my question is hard to understand.
•  » » Since we are considering the possibility after a googol of query, we would only like to consider the last chosen k items. Choosing an item again could be considered as skipping a query, which has an insignificant effect due to we are considering a googol of query.
•  » » Thanks haleyk100198 for the answer. But personally I think it's not the case.My solution for this problem is to solve an equation. For example, in order to calculate dp in my previous post, I will solve this equation:dp = _p1*dp + p2*dp + p1*dp + p2*dp(_p1_ means the probability the first video is chosen, p2 means the probability the second video is chosen)So the answer is dp = p1/(1-p1-p2)*dp + p2/(1-p1-p2)*dpBut actually it's incorrect. The correct answer should be dp = p1/(1-p2)*dp + p2/(1-p1)*dpI can't understand why my solution is wrong.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   I understand your doubt, but the problem is about the last K distinct items chosen.Consider that we are trying to fill the cache with 3 items and infinite moves. For state , choosing items 1,2 again doesn't mean that we have the calculate the value of  and  recursively due to there are (p1+p2) chance of reaching the state  again. Instead, since there is infinite moves, you should consider that choosing these option 1 and 2 as invalid, because we are not going to move on to the next state until we choose something that is not chosen yet — this is why that we could completely ignore p1 and p2 in our calculation.
•  » » » » I don't think you can ignore choices this way, you can do it only if p1+p2 is 0.
•  » » » » » 3 years ago, # ^ | ← Rev. 5 →   Well, I don't have a strong proof for ignoring the choices, but I think that since we are getting back to the state until we have chose something different, and we have infinite moves, all the recursive calculations could be treated as p1 and p2 are not here. UPD: Consider sum of GS to infinity, the chances of reaching  from  equals to p3*p+(p1+p2)**p3+.... = (p3*(1-(p1+p2)^inf))/(1-(p1+p2)) = p3*/(1-p1-p2). Same for any options and other states, thus p1 and p2 could be ignored here.... Maybe it's just not the word I should use. (Well unless p1+p2=1, but we had handled the case of p3=0)UPD2: Rethought about this... Yeah... it's my bad to use the word "ignore" here, it's kinda misleading.
•  » » Let's say that mask has t set bits — (V1, V2, ..., Vt). Now let's fix the next query, denote its index with F. Now we need to add dp[mask|(1<
 » 3 years ago, # | ← Rev. 2 →   I have a question about my solution to div2 E. See #65 and #36, n is the same and #36 contain many 0 probabilities, but my solution do about the same amount of operations for both, however, #36 costs much more time than #65. It seems that time cost of mul/div operations on double type depends on the values. so strange.http://codeforces.com/contest/699/submission/19276677UPDATE： change dp[l | (1 << i)] += dp[l] * p[i] / sum; to if (sum > ERROR) { dp[l | (1 << i)] += dp[l] * p[i] / sum; } and the time is ok, seems that division by 0 on double doesn't cause runtime error but costs more time.
 » - Problem D__ - I don't understand what if there's no cycles in given graph?
•  » » It is impossible. The graph containing n vertices and n edges must have at least one cycle.
•  » » » got it, спасибо)
 » In Div2-E, why is f(mask) divided by (1-sum of probabilities of all videos whose bit is set in mask)? I mean it should just be sum of p[i]*f(mask^(1<
•  » » Check out my comment above, the formula can be proved by sum of GS.
•  » » » I doesn't understand your comment. We need ith video to be one of the last k different videos. So it doesn't matter what videos are being requested for in previous requests. So we can multiply 1 for those videos. Why are you summing on how many times no. of videos not in mask are requested? f(mask) = probablilty of bits set in mask to be in cache. f(011) should be equal to p*f(010)+p*f(001) but why its equal to (p*f(010)+p*f(001))/p
•  » » » » Choosing videos that are requested before DOES matter.Again, I am going to try to explain the idea with "filling the cache". This is what we are considering:[blah blah blah 123212] + [k distinct items] (a total length of one googol)You can agree that our problem now becomes finding the chances of each latter sequence appearing regardless of its' length, and sum the probability to the chance to the corresponding flags, right? Great.So since we are counting the probabilities regardless of the sequence's length, choosing an item repeatedly effectively increases the length of the sequence by one, and it should be considered as a different sequence. This is why we have to consider choosing it repeatedly, and the probability of moving from state [mask] to [mask|(1<
•  » » » » » Thanks for the great explanation for the problem.However, I have difficulty in understanding because I think below formula can hurt final precision. Could you please correct me if I'm thinking wrong? sum of all possibilities of choosing previously chosen items in mask equals to infinity power of "probability sum of chosen items" For example, if we consider 2 chosen items, I can find the probability of choosing 2 times sequencially(p1*p2) in square of their sum. However, it is (2*p1*p2) which is more than what if we calculate correctly.
 » This division was the first I participated in officially. After I tried to hack someone's code, I have two questions.I saw that someone used lower_bound, which can trigger runtime error.And I copied it and figured out some data which can make runtime error in visual studio. So I tried to hack by using that data. But after hack, it didn't lead to error and output normally. Why this situation happenend? Can't we hack runtime error code? Secondly, when I tried to hack Div2-A for O(n^2) code, I couldn't hack because of limitation of text file size. Then, can't we hack TLE code which needs a big data?Anyway, it was good experience and specially thanks for hacker who hacked me :). It helped me be the "BLUE" for my first trial.
•  » » 2) You may use generator — program that prints test to stdout 1) Yes, you can, but you should understand that usually runtime is not guaranteed and it's actually UB that may work and return right answer
•  » » 2) for large tests you can send generators. Example generator I hacked with#include using namespace std; int main() { cout << 200000 << endl; for (int i = 0; i < 200000; i++) { cout << 'R'; } cout << endl; for (int i = 0; i < 200000; i++) { if (i) cout << " "; cout << i * 2; } cout << endl; }
•  » » » Wow, I didn't know that. Thanks for great tips!
 » Now that's a nice editorial(or truly said 'analysis'). Good job and thanks!
 » Hey, guys! Could you please share some interesting and small test cases for div2 F ? I got WA and I can't seem to find my bug..:(
 » 3 years ago, # | ← Rev. 6 →   I felt the a standard solution for B where you would sum walls per column and row was too tricky with corner cases. I made another solution. The idea is too add the walls one per one while we design the solution filtering the reliable coordinates (x, y) to put the bomb. We will define a queue of coordinates (x, y) . This queue contains all possibilities for the bomb in a particular moment. But, there are cases where there this queue may be too big. For example at the beginning (with no wall processed) all places could be used thus the size of the queue would be (N*M). So, to simplify the solution, we'll say x =  - 1 or y =  - 1, two values out of range, if any place could be used in that stored chance as x or y. We start with only one value on queue, (-1,-1), cause at the beginning any place is reliable, and then we process for each wall, each bomb possibility to be reliable with this wall. If X =  - 1, then we add to the new queue (W.x, Y) as the possibility must be modified as now with this chance, X value is fixed, not variable. If Y =  - 1, then we add to the new queue (X, W.y) If X = W.x or Y = W.y then we can add the same possibility to the new queue, as the bomb possibility won't be changed by the wall. We destroy the old queue and replace it with the new queue for the next wall processing. In the end we will get a queue with all the possible coordinates for the bomb.The total complexity is O(N * M * J) where J is the time to process the queue in wall processing. I feel it is not very big as the possibilities filter very fast by my intuition. If you want you can do the analysis of J complexity.The nice thing of this algorithm it is that is so general that we can avoid to analyse the tricky cases :) Code: 19309915
 » F? :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   After so many days F is still not out. (and the problem seems interesting O_O)
 » Well,I am confused about LRU. I don't understand what is the exact meaning of dp[mask]. My confusion is:after a long time(10^100) in this problem,the probability of all mask(or status) will converge to a fix number.However,when considering the limit of probability of status less than k bits,the probability must be 0(unless n
•  » » got it
•  » » » Hello! How did you manage to understand this problem? I couldn't.
 » A simple explanations for LRU problem, please? I don't get the whole "we consider the process backwards". Is somebody kind enough to explain it, please? :D
 » Could anyone please help me to solve div2.F? my_submissionI couldn't figure out why my simple solution doesn't pass for TC#7.Here's my approach, Distribute lines from each teleportspot to other monsters. The line parameters are normalized by absolute gcd of its parameters (L = Pk X Pn). So, a line contain one or more monster(point) within. And these monsters(points) are sorted by distance from teleport-spot. Search for all permutation of k(by dfs) and check every line within the teleport-spot and take maximum one monster for a line at front. If the front monster can reachable from the other teleport-spot visited before, then ignore them) The final result is the maximum number of reachable monster among all permutation of k.
 » In Div 2D (or Div 1B) is the graph directed or undirected? Or does it not matter which way we assume it to be? Because if it is undirected then there can be multiple edges between a pair of vertices.How to solve the problem then?
•  » » Both interpretations are fine. Choose the one you understand better. If it's undirected, two edges between a pair of vertices form a cycle of size 2.
 » When will we see the tutorial of problem F(div 1.). It seems like a very interesting problem. I know how to deal with the case that Pi=0 (for all i). But my program may be wrong sometimes when some gap has been filled. It seems a little bit complicated. Can anyone help?
 » why is it that problem D's page is not showing its description, and its tutorial is also not available.
 » I don't understand why 21387180 is failing :( Can anybody help?
 » Sorry for necroposting this, but where's the editorial of Div2F ? How to solve Div2F ?
 » somebody explain me solution for div2 D??http://codeforces.com/contest/699/submission/19245369
 » Can anyone explain div2-C DP approach
 » hey can someone explain me the Div2 C problem ?... thanks in advance ....
•  » » My submission I think the code is pretty self explained, but i will also add here my ideaWhat to do in each day: 0 — just rest 1 — if you participated in a contest last day, is a free day, otherwise mark that today you participated 2 — if you went to the gym last day, is a free day, otherwise mark that today you went to the gym 3 — if last day you participated in a contest, today you will go to the gym; if last day you went to the gym then you will code; if you did nothing last day you can do both, but we can mark this as doing nothing without counting it as a free daydays 0 1 2 are pretty clear, but the last case of the day 3 maybe needs to be explained more, consider we have: 3 1 — we will consider first day as a 2 day 3 1 — we will consider first day as a 1 day 3 3 1 — we will consider first day a 1 day, second day a 2 day 3 3 3 1 — we will consider first day a 2 day, second day a 1 day, third day a 2 daybut we will do something regardless of what day will be tomorrow
•  » » » thanks @DysKode
 » How can we do the VACATION Problem C , by dp, without taking opposite problem.(i.e taking min no. of days the took rest)? Is there any solution or explanation for that, Plzz
 » can somebody explain logic , how do we arrive at this dp solution of Problem 699C — Vacations??
 » I actually wrote the editorial for 698D - Limak and Shooting Points three years ago in Polygon but it still isn't updated in this blog. Let me paste it: SpoilerThere are $k$ places and $n$ monsters. For each of $k$ places let's sort monsters by angle. Thanks to that, for each pair (place, monster) we will be able to know which monsters don't allow us do directly hit this monster from this place.Let's iterate over monsters and for each of them independently check if it can be hit. We want to get the complexity $O(n \cdot k!)$ or $O(n \cdot k! \cdot \log n)$.We fixed a monster $m$. We want it to be hit in some moment. So, let's iterate over places — considering which place will eventually hit a monster $m$.We fixed a place which will hit $m$. Thanks to the preprocessing (sorting by angle at the beginning), we are able to check if the fixed place can directly hit $m$. While we can't hit directly we find any blocking monster (it may be e.g. the first monster in this direction, looking from the fixed place). Let's call it $m2$. If we want to succeed then some place must hit $m2$.Iterate over which place will hit $m2$. Again, check if it can directly hit now. If yes then mark this place as used and $m2$ as killed (and go back to checking $m$, but with monster $m2$ killed and thus not blocking us anymore). Otherwise, find any monster in this direction and again, iterate over a place to hit it in the future.While checking if a monster may be directly hit by some place, remember that some monsters may be already killed and thus they don't block anything.The above should give you the rough understanding of the solution. Let's talk about the details and the implementation.Iterate over a monster to check and over $k!$ permutations of places. Create a recursive function rec(int monster_to_kill, list & permutation). Take the first place from the list and remove it for ever from the list. This will be a place to eventually kill monster_to_kill, maybe not now. While there are any alive monsters between the fixed place and monster_to_kill , choose any of those alive monsters and run rec(that_monster, &permutation).Don't treat permutation as the order of teleportation stones to use. It's only the order in which we take them from some stack/list. It only allows us to nicely simulate iterating over a place from which we want to get rid of some blocking monster.Some words about the correctness. Is it possible that the described solution isn't able to find a way to kill a monster while there exists a way? In such a way there is some place from which Limak will hit the monster. We simulated iterating over such a place. We can't hit directly at the beginning only if there are some blocking monsters between the place and the monster. Each of them must be hit from some place. We don't assume anything about the order of monsters or about the order of places from which we hit. In the "optimal" way, every monster initially blocking us must be hit in some moment by some place so we can (and must) iterate over a place from which it will be hit. If there are some new blocking monsters then again — in the "optimal" way some place hits it and we iterate over it.
 » 699C — Vacations Solution using XOR properties in JAVA(no dp)import java.util.*; import java.io.*; public class Main { public static int func(int n ,int arr[]){ for(int i=0;i=0 && arr[i-1] !=3){ arr[i] = arr[i] ^ arr[i-1]; } if(i+1 < n && arr[i+1] ==3 && arr[i] !=3){ arr[i+1] = arr[i+1] ^ arr[i]; } } if(arr[i] == arr[i+1] && i+1 < n && arr[i] !=3){ arr[i+1] = 0; } } int count =0; for(int i=0;i