### vovuh's blog

By vovuh, history, 6 years ago, translation,

• +24

 » 6 years ago, # |   0 Auto comment: topic has been translated by danilka.pro (original revision, translated revision, compare)
 » 6 years ago, # |   0 I think I used a simpler method for C, this is the observation: Let M be the maximum of {b, d, s}; then the other 2 would be in the best case M — 1. So if b is the maximum, then (d >= b — 1 and s >= b — 1) always holds true. This is the code: http://codeforces.com/contest/732/submission/21550209
•  » » 6 years ago, # ^ |   0 "So if b is the maximum, then (d >= b — 1 and s >= b — 1) always holds true." In case {b = 6, d = 3, s = 3} your statement is wrong. In that case b is maximum, but d < b - 1 and s < b - 1. Or did I miss something?
•  » » » 6 years ago, # ^ |   0 No, I'm talking about the ideal situation. Lets say b = 6, d = 3 and s = 3. Then Vasiliy has 6 breakfasts, and the minimum number of dinners and lunches he would have had is either 5 or 6. In no situation can it be lesser. We want to find the minimum, so our answer would be (5 — 3) + (5 — 3). (Where 5 is the minimum d we could have, and 3 is the d given to us in the problem statement)
•  » » 3 years ago, # ^ |   0 Yeah, I used the same trick and it is quite easy than the one given in tutorial
•  » » » 2 years ago, # ^ | ← Rev. 5 →   0 For the case when b = 2, d = 3, s = 1 how is the answer 1 ? B 1 1 (0) D 1 1 1 S 1 (0) 0 Aren't the ones in the bracket the missed meals = 2 ? If you could help me out with where I am going wrong here .. Thanks!EDIT:Just understood, it could be represented as this too : B 0 1 1 D 1 1 1 S 1 (0) 0 Meaning only the one in the bracket is the missed meal.
 » 6 years ago, # | ← Rev. 3 →   0 managed to do a-e but, i need to read tutorials on problem F , im still a bit confused, can someone explain , what is : component connected component largest component thanks for your help :)
•  » » 5 years ago, # ^ |   0 just google it
 » 6 years ago, # |   0 can someone explain last line for f. with example? why orient (v,to) to (to,v)?
•  » » 6 years ago, # ^ |   0 Just think about it, if you are pointing from v→to, you are leaving the largest cycle pointing outwards.
•  » » » 6 years ago, # ^ |   0 ok understood it. That really made the whole question. Thanks bro.
 » 6 years ago, # |   0 Hi, I'm not understanding why my submission is getting TLE for Div2 F. can anyone please check it? Here's my submission, 21830666 I have implemented it exactly as given in the tutorial.
 » 6 years ago, # | ← Rev. 2 →   0 In Problem B, test-10: Input 5 2 0 0 0 1 0 Output 4 0 2 1 1 1 Answer 3 0 2 0 2 0 Checker Log wrong answer Jury answer is better. Obviously my answer is better?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 " Write a program that will find the minumum number of additional walks "I am pretty sure it is not obvious that 4 < 3.
•  » » » 6 years ago, # ^ |   0 Oh no, I am very sorry. I mixed up Answer and Output.
 » 6 years ago, # | ← Rev. 2 →   0 Div2D ExamsConsider the following test case 10 3 0 3 0 1 0 0 0 0 2 0 1 1 4 The following AC submission gives the answer as 9. I would like to know how is the answer 9 correct. Since subject 3 requires 4 days of preparation, which clearly isn't possible, shouldn't the answer be -1 ? #include using namespace std; int main() { int n,m; cin>>n>>m; int arr[n+1]; for(int i=1;i<=n;i++)cin>>arr[i]; int sum=m,x; for(int i=0;i>x; sum+=x;} for(int i=sum;i<=n;i++)if(arr[i]){cout<
•  » » 6 years ago, # ^ |   0 It was mentioned that the test cases are flawed and some wrong solutions managed to get an AC.
 » 5 years ago, # |   0 Why is complexity for Problem D O(mlogn)? For each guess, we want to take the subject at the latest possible day right? So we will need to perform a linear scan on the exam days so that we can find the latest day for each subject. So that should be O(nlogn) right? Is anyone able to confirm this?
•  » » 5 years ago, # ^ |   0 Did you find an answer for this?
 » 5 years ago, # |   0 can someone provide an explanation on why is the mentioned strategy of orienting edges in problem F optimal? i.e. why does it allow us to traverse from any vertex to any other vertex in an 'edge' connected component?
 » 5 years ago, # |   0 Test cases for D are very trivial. All of them pass through wrong solution also.
 » 5 years ago, # | ← Rev. 3 →   0 Can anyone provide proof of correctness for problem F ? I am not sure whether the solution in tutorial is correct
•  » » 21 month(s) ago, # ^ |   0 StatementThere will be at least 1 vertex which will has degree — $1$. ProofLet $d_1$ be the vertex which has degree — $1$. In directed graphs, if every vertex has at least degree — $2$, it means that graph is cyclic. But, in our situation (there is at least $1$ bridge) it is impossible. So it means that $d_1$ vertex can only travel in his own component. (for $d_1$ vertex the answer will be size of his own component). To maximize the minimum, it is optimal to choose the $maximalComponent$ as our $d_1$ vertex.
 » 3 years ago, # |   0 Can someone please explain the editorial of Problem F? I can't get why the answer is the largest component!
•  » » 3 years ago, # ^ |   0 For example take the following graph: 1----2---5 | | 8------9 12----| | | | | | | 3----4---6---------7------10--------11----13We have two bridges (6,7),(10,11). Now first without considering bridges we will direct other edges,and they will be obviously completely connected as there will be a cycle(because all the bridges already have been removed) Now come to bridges, if we direct 10--->11 then ri for (i=11,12,13) will be equal to 3 else if we direct 10<---11 then ri for (i=11,12,13) will be equal to 7 So we direct edge from smaller to larger ,to get 7 over 3 Similarly we will do this with 6<---7 else (7--->6) ri for (i=7,8,9,10) will be 4 (focusing on minimum ri)So largest component can reach only to the vertices which come in its component after removing all bridges.If we take direct edge from higher component to lower component (higher and lower is with respect to number of vertices in component) ,then minimum can't be maximize,therefore answer will be largest component.Happy Coding :)
•  » » » 23 months ago, # ^ |   +3 That was really a great explanation. Thanks!
 » 3 years ago, # |   0 In problem B, why the count of the new walk is 2 and not 1?
 » 2 years ago, # | ← Rev. 4 →   0 Problem D please someone Add this Test Case if possible 17 3 0 0 1 0 2 0 3 0 0 0 0 3 0 0 0 0 1 6 1 1 My Code Output12Actual Output17Still it got Accepted
 » 23 months ago, # |   0 I know it's easier to solve problem B with greedy but still out of my enthusiasm, I wish to do it using DP so please can someone suggest any recursive DP expression for this Problem B.Thanks for your valuable time!!
 » 14 months ago, # | ← Rev. 2 →   0 the test cases of problem D are weak.my solution is wrong but got ac. for the test case 16 3 0 0 1 0 2 0 0 3 0 0 0 0 0 0 0 1 2 4 7 ans should be -1 but mine gives 16
 » 12 months ago, # |   0 Actually we don't need to find bridges in problem F. For every edge $(u, v)$ in our DFS path, just orient it from $v$ to $u$. Refer to my submission: 117700144.
 » 11 months ago, # | ← Rev. 2 →   0 in B why don't we cater for dog's walk if number of days = 1 Example case 1 10 1 Answer according to me 9 10 Answer Found 0 1 
 » 8 months ago, # |   0 Can someone please explain D
•  » » 8 months ago, # ^ |   0 merko bhi batana :joy ans mile to