root8950's blog

By root8950, 9 years ago, In English

I am new to max flow type questions. In this problem, http://codeforces.net/contest/653/problem/D , if I use any max flow algorithm and find flow from starting node( ie 1 ) to its all neighbors.
Lets take an example if from node 1, four other nodes are connected with capacities 4 , 5 , 6 , 7 respectively and after applying max flow algorithm, say the flow comes out to be 3 , 5 , 6 , 6 (if we consider max flow) (these values are arbitrary here.)
And then I apply binary search. In binary search step, I am finding the total weight that all bears will carry and then dividing it by number of bears ( say I obtain k=2, the weight each bear will carry). Now if using the flows obtained earlier ie 3 , 5 , 6 , 6. I try to allocate bears (that will be 1 , 2 , 3 , 3) and see if allocation is possible or not. (by comparing the bears I allocated here 1+2+3+3 = 9 with bears I originally had)
Is this approach correct?

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By root8950, history, 9 years ago, In English

I am unable to find approach to this question. https://www.codechef.com/IOPC2016/problems/IOPC16Q The contest is over and there is no editorial. Anybody having idea how to solve it?

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By root8950, history, 9 years ago, In English

I have a set as
set<int> s;
I used lower_bound(s.begin(),s.end(),x)
It gave me TLE.
Then i used s.lower_bound(x)
My solution passed.
Whats the difference in both? I mean why is it happening?
First one is working in O(n) time while latter in O(logn).
Weren't both supposed to be O(logn) ?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it