RetiredAmrMahmoud's blog

Codeforces Round #312 (Div. 2) Editorial
By RetiredAmrMahmoud, 9 years ago, In English

558A - Лалаландия и яблони

Let's divide all the trees into two different groups, trees with a positive position and trees with a negative position. Now There are mainly two cases:

  1. If the sizes of the two groups are equal. Then we can get all the apples no matter which direction we choose at first.
  2. If the size of one group is larger than the other. Then the optimal solution is to go to the direction of the group with the larger size. If the size of the group with the smaller size is m then we can get apples from all the m apple trees in it, and from the first m + 1 trees in the other group.

So we can sort each group of trees by the absolute value of the trees position and calculate the answer as mentioned above.

Time complexity:

Implementation .

558B - Amr и большой массив

First observation in this problem is that if the subarray chosen has x as a value that has the maximum number of occurrences among other elements, then the subarray should be [x, ..., x]. Because if the subarray begins or ends with another element we can delete it and make the subarray smaller.

So, Let's save for every distinct element x in the array three numbers, the smallest index i such that ai = x, the largest index j such that aj = x and the number of times it appears in the array. And between all the elements that has maximum number of occurrences we want to minimize j - i + 1 (i.e. the size of the subarray).

Time complexity:

Implementation

558C - Amr и химия

Let the maximum number in the array be max. Clearly, changing the elements of the array to any element larger than max won't be optimal, because the last operation is for sure multiplying all the elements of the array by two. And not doing this operation is of course a better answer.

Now we want to count the maximum number of distinct elements that can be reached from some element ai that are not larger than max. Consider an element ai that has a zero in the first bit of its binary representation. If we divided the number by two and the multiplied it by two we will get the original number again. But if it has a one, the resulting number will be different. So, for counting the maximum number of distinct elements we will assume ai = x where x has only ones in its binary representation.

From x we can only reach elements that have a prefix of ones in its binary representation, and the other bits zeros (e.g. {0, 1, 10, 11, 100, 110, 111, 1000, ...} ). Let's assume max has m bits in its binary representation, then x can reach exactly distinct elements. So, from each element in the array ai we can reach at most elements.

So, Let's generate the numbers that can be reached from each element ai using bfs to get minimum number of operations. And between all the numbers that are reachable from all the n elements let's minimize the total number of operations.

Time complexity:

Implementation

558D - Угадай, где выход! II

First, each query in the level i from L to R can be transmitted into level i + 1 from L * 2 to R * 2 + 1, so, we can transform each query to the last level.

Let's maintain a set of correct ranges such that the answer is contained in one of them. At the beginning we will assume that the answer is in the range [2h - 1, 2h - 1] inclusive. Now Let's process the queries. If the query's answer is yes, then we want to get the intersection of this query's range with the current set of correct ranges, and update the set with the resulting set. If the query's answer is no, we want to exclude the query's range from the current set of correct ranges, and update the set with the resulting set.

After we finish processing the queries, if the set of correct ranges is empty, then clearly the game cheated. Else if the set has only one correct range [L, R] such that L = R then we've got an answer. Otherwise there are multiple exit candidates and the answer can't be determined uniquely using the current data.

We will have to use stl::set data structure to make updating the ranges faster. In each yes query we delete zero or more ranges. In each no query we may add one range if we split a correct range, so worst case will be linear in queries count.

Time complexity:

Implementation

558E - Простое задание

In this problem we will be using counting sort. So for each query we will count the number of occurrences for each character, and then update the range like this

for(int j=x;j<=y;j++)
  cnt[s[j] - 'a']++;
ind = 0;
for(int j=x;j<=y;j++)
{
  while(cnt[ind] == 0)
    ind++;
  s[j] = ind + 'a';
  cnt[ind]--;
}

But this is too slow. We want a data structure that can support the above operations in appropriate time.

Let’s make 26 segment trees each one for each character. Now for each query let’s get the count of every character in the range, and then arrange them and update each segment tree with the new values. We will have to use lazy propagation technique for updating ranges.

Time complexity: where sz is the size of the alphabet (i.e. = 26).

Implementation

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

Comments Comments (98)
| Write comment?
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you for Fast editorial

→ Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

We have no rights to see the solutions. Please, change it.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, wouldn't a bruteforce on bits have a complexity of O(n*m) where m is the number of bits?

→ Reply
»
9 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I loved the round! No issues during the contest (not with the statements, not with cf), an engaging problem set, and if it weren't enough, a lightning fast editorial publication. This is how a round should be done. Keep up the good work! :)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can this solution work for Problem C:- For every element, find all the number that can be reached by applying the two operations between 0 and MAX and add one to each number's position in an array(lets say arr). Hence, we will have an array arr, which will tell us for each number i, how many elements given to us are reachable from i. So if we iterate over i from 1 to MAX and arr[i]==n, That means all the elements can be reached to i performing the operation. Then in n*log(n) complexity find the number of operations to convert all number to i and then print the minimum. Please tell me what is wrong with this approach.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It works.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    The problem with your code is it will never reach all the possible numbers. For example if you take a test case n = 3 and elements as 11 10 21 In this case your answer will give answer as 4 considering all the numbers to reach 5. But the correct answer will be 3 because you can convert 21 to 10 in 1 step and 11 to 10 in 2 steps namely :- 11->5->10

    So in the step when you are dividing by 2 i.e. p=p/2; you have to consider whether the previous p was even or odd. Since if previous p was odd e.g. if you have p = 11 then you will get different numbers by doing 2*(p/2). In this case 11/2 = 5 and 5*2 = 10. So you will have to find all the numbers <= Max in the step p = p/2 if p is even...

    Also just try to debug with the example case of n = 3 and elements as 11 10 and 21. Try to print all the numbers element 11 is reaching according to your code and you will find that it is not reaching 10. That is the mistake.

    I also did it in this way. You can check my AC code here. :- http://codeforces.net/contest/558/submission/12058744

    Feel free to ask something you didn't got in this comment.. Hope it helps :)

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Interesting round Waiting for your next :D Thank you

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Problem C can be solved in O(NlogN). Imagine it as a binary heap such that according to the given operations, we can either go up to the parent( divide by 2) or to the left child (multiply by 2). Using such imagination, it can be solved as follows :
For each i, let
L[i] = Number of active nodes in left subtree of i
R[i] = Number of active nodes in right subtree of i
H[i] = Number of times i occurs in the input.
where a node is active if it occurs in the input.
We can calculate the answer if all of them are brought down to 1 using the level of each node.
Hence, now we move from 1 to the direction of optimal answer in the following way : 


	bool up = false;
        LL mn = ans[1];
	for(int i=1;i<N;)
	{
		if(!L[i] && !H[i] && !up)
			i = 2*i + 1;
		else
		{
			if(R[i] || H[i])up = true;
			UP[2*i] += UP[i] + H[i] + R[i];
			i = 2*i;
		}
		if(i>=N)break;
		if(i&1)	//we went to right
			ans[i] = ans[i/2] - R[i/2];
		else	//we went to left
			ans[i] = ans[i/2] + UP[i] - L[i/2];
		mn = min(mn,ans[i]);
	}

Here is a link of AC submission http://codeforces.net/contest/558/submission/12053885

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain how your code is working?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      The above picture shows the possible operations. Let ans[i] denote the answer if all of them are made equal to i. ans[1] can easily be computed using the levels of the nodes.
      Now, We need to go from 1 to the optimal answer.

      We can move from a node to its right child in search of the answer only if there is no active node outside the right subtree because there is no directed edge between from a node to its right child, hence there doesn't exist any path from outside the right subtree to inside the right subtree. Also, in such a case , we do not need to look for the optimal answer outside the right subtree because all the active nodes lie inside the right subtree and thus moving to right subtree must decrease the answer.

      If we cannot move to the right child, then we go to the left child and compute it's answer and compare with the minimum.

      Also, the answer of a child from its parent can be computed using
      answer of child = answer of parent — Decrease in no of times we need to traverse the edge between child-parent.

      Hope the approach is clear now. :)

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Really appreciate your effort! Thanks! :)

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Really cool solution :)

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Not able to understand this line in your code.
        Why are you using if(R[i] || H[i])up = true; ?
        I think using if(H[i]) up = true; should be sufficient.
        Please help me understand this line of code.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          H[i] represents the count only of that node while R[i] represents the count of the right subtree. Up is true if we can enter the subtree from anywhere "outside" it. Outside means not just the immediate parent (represented by H[i] ) but also anywhere from the right subtree (represented by R[i]).

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very nice approach, thank you.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's UP bruh?

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +32 Vote: I do not like it

C in linear time:

Let's create a binary tree with at least MAX_Ai nodes. With dp for every vertex we can say "what is a cost to move everything from its subtree to this vertex". Then from top to bottom we can do second dp — what is cost to move everything from outside of a subtree to this vertex? In my implementation rec(int,int,int) gets index of vertex, cost so far and number of elements outside of current subtree (cost increases by this number when we go to a child) Link: http://codeforces.net/contest/558/submission/12047835

and E without sqrt decomposition and lazy propagation: http://codeforces.net/blog/entry/19173?#comment-240849

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you visualize your algorithm? I don't really understand from your code. Thanks for your attention

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's say input is n = 3 and array 2,5,6. Consider a binary tree with 7 (in my code there are always 2^17-1) nodes where node number x has children 2*x and 2*x+1. Root has number 1. Now let's think about it as a graph. There is one "thing" in node number 2, one in node number 5, one in node number 6. What is a node minimizing sum of distances to these "things"? Draw it, it will help you to understand it.

      Do you see a solution if we could go to parent and to each children? It would mean that we can do operations: x=x/2, x=2*x, x=2*x+1. The last operation means going to right child. Here we can only go up to parent (by dividing by 2) or to the left son (multiplying by 2). There is a small 'if' in my code for that.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am not able to understand your code. Can you please explain what is stored in array res[]? I got that, the array ile[i] stores the number of elements in the subtree of vertex i.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          res[x] is a cost of moving everything in a subtree x to vertex x

          res[2*x]+res[2*x+1] is a cost of moving everything from a subtree 2*x to vertex 2*x plus the same for 2*x+1. Then we must move things from 2*x and 2*x+1 to vertex x. There are ile[2*x]+ile[2*x+1] things and we must move each of them by one (from 2x to x or from 2x+1 to x)

          → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please tell me why this solution for D does not work ? (leftt is the starting index of the leaves and rightt the the last node) 12052248

Tanks a lot! :-)

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

In problem D you may get rid of h * q part by doing single jump from level i straight to leaves (12051754).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    your code is what I call "code smart not hard". Nice code (Y)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell me why my code exceeds the time limit? Code

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't know exactly but there may be the case when while(1) will cause an infinite loop so be careful with it. Also when you iterate through invalid vector, then you call dissolve function which catches two itr and itr2 "pointers" and then you iterate through it, I think this may not always be O(nlogn) algorithm, also there can be cases when you don't remove any segment from set s, and just split one segments into two parts and increase its size by one.
        Anyway, keep going!

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the tips, I'll revise my code. As for the O(nlogn) part, I've noticed that the setter's code uses a similar sweeping algorithm though.

          → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Why is q=0 in D (and E) allowed? Both are pretty dumb problems with q=0, and passing q=0 seems to be largely a matter of implementation (e.g. whether you include a "null" query of the whole range to begin with), rather than actually thinking about this possibility — I'm interested to know how many people actually noticed its allowed.

Am I going to have to look at lower bounds as well as upper bounds now? :P

Also just to give another idea for D — instead of keeping a set of segments that is good, you can keep a differences array — to make a segment [a,b] good, do val[a]+=1, val[b+1]-=1 — and take partial sums afterwards. Any good point is one where the sum there is q. (as a sidenote — it seems people who failed for q=0 did this idea without a null query)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Maybe there was no point in task E. But for task D those constrains will allow h = 1, q = 0 testcase which is interesting. :P

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    if (has[where]==maxn || val.count(has[where]+1)) can you please explain me second condition..

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We are only storing a few values in this map (since there are like 2^49 leaves and we cannot store them all), so if val[x]=q, then also we know that for every x+1,x+2,... until the first one that has a different value in val also should satisfy val[x+i]=q (basically if the answer is unique, it must have val[x]=q, and also val[x+1]!=q).

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone explain how we are updating the segment tree in E? EDIT: Got it :)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used the same way in problem C as the Editorial but I wasn't sure that there was no optimal answer above the max element ... my solution passed pretests but got TLE in test 21 ... i want to know why the number can't be greater than the max number

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    If you multiply the largest number by 2, you must multiply the other numbers at least once, right? Now suppose that you multiplied all the numbers by 2, you can get rid of that multiplication and improve the answer ( minus n moves)
    If a*2=b*2=c*2=......=z*2 then a=b=c=...=z

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

12061940, working perfectly on my system but WA at #1. Please help

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Should the following input have an output of "cheated"?

1 2
1 1 1 0
1 1 1 1
→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I Wrote the same damn code and it gave me wrong ans in A.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If l and r is the same, you can instead use b[i]+a[i-1]. That's why your answer is slightly smaller than jury's answer.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

My solution for E is to deal with buckets.

First, count all the characters in the range.

If you have to count the whole bucket, use the precalculated counts(the one you use in counting sort). If you have to count individual alphabets in a bucket,

1) if sorted, use counting sort to pick one.

2) if not sorted, use the table(the naive one).

Now you have to recalculate the table.

If you have to update the whole bucket, use the idea of counting sort.

If you have to update individual alphabets,

1) if sorted, use the precalculated counts to write the table(the naive one). and do (2).

2) naively write the alphabet in the table(the naive one).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C: I don't get the statement "From ai we can only reach elements that have a prefix of ones in its binary representation, and the other bits zeros." Say ai = 1101, then can't you reach 11010, 110100, etc.?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C, setter's code, line 58. Why is it x > 100003, and not x>100000 only?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In div2-C tutorial :

Clearly, changing the elements of the array to any element larger than max won't be optimal, because the last operation is for sure multiplying all the elements of the array by two. And not doing this operation is of course a better answer.

can this thing be proved ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    All numbers can be written in the form n*2^k, where n is odd. For every number to be the same, they clearly need to have the same value of n. The only way to change the value of n is to divide by two. So this is the only operation we should do until all numbers have the same value of n. Once this is done, we need to make all the k the same. This is done optimally by finding the median number and making everything equal to that. So anything larger than the median, we divide by two until it is the same as the median, and multiply by two for anything smaller than the median.

    When we make all n the same, clearly all numbers are decreasing. When we make all k the same, clearly all numbers are moving towards the median (which is less than the max). Hence, we never need to exceed the maximum number.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't get the C at all. Could you write that more formally? So many solutions here, but with so vague descriptions! Argh :(

"assume ai has only ones in its binary representation" — What do you mean by that? What if ai = 5?

Also, what do you mean by "ai has elements"? What are the "elements"? And why then ?

Thanks in advance!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Okay, at last I got it. Thanks everyone for sharing ideas :)

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Editorial enhanced. If there is any problem tell me.

    "assume ai has only ones in its binary representation" that's only for analyzing running time, not the solution.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To solve Problem E, making a balanced binary tree that each node discribe some same character which located contigeously is much better than 26 segment trees, though both of their time complexities are O(sz*q*logn). It must because of the quantity of balanced binary tree is usually much less than segment tree. However, if it is sorting a long substring, balanced binary tree would delete many nodes and insert no more than 26 nodes; but the quantity of segment tree would not reduce.

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

There is soltuion in E. It's similar to this solution. The difference is that we have only one set, each element of it describes a segment [l, r] with letter c.

Because of using only one set we get rid of multiplier sz in complexity.

Solution works pretty fast on testcases (186 ms).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In your code, each query you need to insert a node into "set <pair <pair <int, int>, int> > s" at most 26 times. So why your complexity is O((n+q)(sz+logn))?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, thanks, you're right, I had slow implementation of this moment.

      You can notice that elements we want to insert are in sorted order. It allows us to insert it in with second method from here.

      You can find new code here.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you, I got it. I didn't not stl set can be used like this before. I can only write a splay tree so that realize O(logn+sz)....... Till now my program is the fastest in this problem, but a little long.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did what Errichto explained but it was difficult atleast for me to implement in Java. But after some non-AC submissions, here is my submission: 44188936. I hope it helps.

    But I still have one doubt about its complexity. It is amortized and range gets bigger as we do queries and hence query time reduces after every query. Is this the reason or is there some better/other reason?

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Problem D (558D - Угадай, где выход! II) looks like an exersize on compressed segment tree.

Let's tree(x) = 1 if an exit can be in x's leaf node and 0 otherwise. Segment tree will count sums of segments of function "tree". Initially tree(x) = 1 for all x in [2 ^ (h- 1); 2 ^ h- 1]. If the next query's answer is 1 then we need to assign tree(x) to 0 for all x in [2 ^ (h- 1); l- 1] v [r + 1; 2 ^ h- 1] where [l, r] — the segment on the h'th level of current query. It can be done with 2 queries to segment tree. And if answer is 0 then we need set tree(x) to 0 for all x in [l; r], we can do it with one query to segment tree.

Eventually sum of tree(x) for x in [2 ^ (h- 1); 2 ^ h- 1] will give the result.

Time complexity: O(q * h)

Memory complexity: O(q * h)

Implementation: 12067778.

There were some problems with memory, becaure each query to segment tree can add up to 2 * h new nodes in tree and each query with ans = 1 creates 2 queries to segment tree. Let process the queries with ans = 1 at first, we just need to intersect all segments of these queries. [L; R] is the result of intersections. After that we can build segment tree on segment [L; R] and process the queries with ans = 0. They creates one query to segmeng tree only.

Implementation: 12068161

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

For D, the second part can be done easier (without dealing with stl:set / range deletion) with an offline approach — just sort all queries with ans=0 by left coordinate and then sweep from left to right, computing the number of possible exits.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody help me?

why my code for problem C is wrong?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my solution is O(N.logN) and i saw many people that thay solved like me but i get WA in test 7.

    why?

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to get where I am doing wrong in solution for problem A. Here is my solution. Can anybody please help me. http://codeforces.net/contest/558/submission/12052565

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I want to mention that editorial code for problem D doesn't have really good decomposition and it makes it hard to understand how it solves the problem. Anyway, problems were really interesting and tricky a little. Thanks!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem D, Is the exit always on a leaf in the last level? I don't think it's specified in the problem statement, but correct me if I'm wrong. Thanks

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "exit from the tree is located at some leaf node" this is clearly written in the editorial.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone tell me where I am going wrong for C? My code fails on #7 http://codeforces.net/contest/558/submission/12073898

My approach: - Find the max value - For all number in the array, divide until 0 is reached and multiply by 2 until max is reached. Record every possible number that can be formed in pos[] and record how many steps it takes to get that number in moves[]. - Now select moves[i] such that moves[i] is a minimum and pos[i] is equal to n.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Consider if number is 7. You multiply by 2 and hence form :

    7 14 28 56......

    Then you divide by 2 and form:

    7 3 1 0

    However once you reach 3 you can also form :

    3 6 12 24

    once you reach 1 you can form

    1 2 4 8 16 32 64...

    I don't think you've taken these numbers in consideration.

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In D if there are two ranges with yes=1 but do not intersect, then will answer automatically be "Game Cheated!"?

Edit: Finally AC.Answer is yes.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anybody explain to me the complexity for E? For count sort, even if the count of each letter is given, isn't the complexity of building the string O(|N|), where N is the size of the string? I didn't think that was fast enough, as if each query takes N at least, then the complexity is O(N * Q), no?

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

In problem B Div.2 how to break ties if we have same j-i+1.Here's my solution.Got a tle. Solution

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    This part gives you O(n^2) complexity: for(int in : ind){ ... for(i = 0;i<n;i++){

    You should calculate first and last occurrences of numbers at once for all numbers.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I cant understand editorial to problem C, can anyone explain it to me in detail? Thanks.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    For every number A[i] marks all the points less than 10^5. marking should be like this:

    • mark all the multiples of A[i] (i.e x=A[i]. while(x<1e5) mark[x]++; x=x<<1;)

    • repeat the process for A[i]/2,A[i]/4 until A[i]/2^c>=1.

    • for every value of i(1..10^5) check if current i is reachable from all A[i] (if mark[i]==n yes otherwise no) (if yes , find the number of steps and compare it with the current minimum) ( These all values are pre-computed )

    • print min

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A can be solved in constant time, no need to sort the list of coordinates.

As you read in the values, keep count of those on the left (values are less than 0) and those on the right (x > 0).

1)if the left count is equal to the right count, return the left+right.

2)return Min(left , right) * 2 + 1

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We must calculate sum of some values, not only count elements. min(left,right)*2+1 is ok for calculating maximal number of apples, not maximal sum of their values.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E, we could just keep a Segment Tree for interval [1..n] and update for each query the "order" of the interval [i j]: non-decreasing, non-increasing, unchanged. While updating, in case we reach on a path from the root an internal node that is already marked with some particular order, we can just mark its two immediate descendents with that order, unmark that node itself and continue. Time to process queries is therefore O(q * log n).

After we are finished processing queries, we can just do a preorder walk of the segment tree and determine for each position in the string [1..n] what kind of sort-order it belongs to.

Finally we would start walking the input string, counting the number of occurences of each character. Everytime the sort-order changes (or we reach end of string) we just output the characters we counted in the proper order and reset the counters. Time to output is thus O(q * sz + n).

The total running time is O(q * (log n + sz) + n), slightly better than the one in the editorial.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think your solution is correct. You won't be able to know which character is where after a sorting operation.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hmm... Yes, you are right. Didn't think this through... Thanks for noticing it!

      Still feel like we could get rid of a sz factor. I will post if I figure out how and maybe implement that time also.

      Best, Mircea**Hmm... Yes, you are right. Didn't think this through... Thanks for noticing it!** **** Still feel like we could get rid of a sz factor. I will post if I figure out how and maybe implement that time also. **** Best, ** Mircea**Hmm... Yes, you are right. Didn't think this through... Thanks for noticing it!

      Still feel like we could get rid of a sz factor. I will post if I figure out how and maybe implement that time also.

      Best, Mircea

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For problem D, Why don't we just simply divides "Yes" and "No" queries to solve this problem in O( Q ) complexity?

For example let me explain how it works by dealing with "YES". First we set l=2^(H-1), r=2^H, which means that the exit might located in range [ l, r ). Then we get a query like x, h, "YES", we update [ l, r ), like l = max( l, x<<h ), r = min( r, (x+1)<<h )

Then we deal with "NO" in a similar way, but let variables l and r means the exit might located in [ 0, l ) and [ r, 2^H ) instead, just like above we got l = min( l, x<<h ), r = max( r, (x+1)<<h )

At last we just check out whether the ranges we inferred from "YES" and "NO" queries have an intersection on not, and answer the question respectively.

Is there anything wrong in my solution? Tell me if you found it, thanks.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For dealing with 'yes' queries, you're right.

    The problem is, for every 'NO' queries, the 'YES' segments will be cut into pieces. So we have to find which 'YES' segment should be removed or contracted, which needs the log complexity.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 7   Vote: I like it 0 Vote: I do not like it

      In my opinion, we can "ignore" the "YES" questions and deal with "NO" questions independently.

      Maybe it can be known more easily if I draw a picture, consider the following picture when we have to "combine" two "NO" questions together.

      ( So sorry that I cannot upload the picture for some reason ) http://image17-c.poco.cn/mypoco/myphoto/20150719/22/17831074120150719220100041.png

      In a word, when I deal with "NO" questions, there is radically nothing to do with "YES" questions.

      And finally we got the ranges that predicted ONLY from "YES" questions or ONLY from "NO" questions then find their intersections. Sincerely looking for your comments!

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Yes, you can combine NOs and simply invert them to get possible ranges. As NO queries can be intersecting(like 1-5, 3-7) or separated(like 1-3, 5-7), we'll have to combine intersecting ranges so that there are only 'unique'(and separated) ranges. It can be achieved by two ways:

        1) For each range, find appropriate place to insert current range. We can implement it with std::set or such, taking O(Q lg Q) time.

        2) Use prefix array; if the range is [L, R], add 1 to a[L] and subtract 1 from a[R+1]. Finally take its prefix sum b[i]=a[0]+...+a[i]. If b[i]>0, i-th position is in NO range. Using this, we can achieve O(Q) time. But the indices should be normalized(coordinate compression), so O(Q lg Q) preprocessing is needed.

        If I didn't got your point or missed something, please tell me.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I got your point.

          My algorithm cannot combine 2 separated ranges like ( 1, 3, "NO" ) and ( 5, 7, "NO" ) because it will produce 3 possible ranges but not 2!

          Sincerely appreciate your great help!

          → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Div 2 problem c : i tried solving it like the editorial, and i got TLE, can anyone explain to me why ? here's my submittion http://codeforces.net/contest/558/submission/12195929 and i tried calculating the complexity, like the editorial, it's O(n*m^2) but maybe it's too slow ? i mean m=15 and n=10^5 in worst case ... maybe i got something wrong. thanks in advance

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are getting TLE because of the calls to memset here :

        for (int i = 0; i < n; i++) {
        memset(visited, false, sizeof visited);
        memset(operations, 0, sizeof operations);
        bfs(nums[i]);
    }

    Instead of that, try coloring the vertices with a new color on every call to bfs

    Also this can get you RE since you are accessing the element in the array before checking for the array boundry

    if (visited[v] || v > maxnum || v < 1)

    A better way to do it is :

    if (v > maxnum || v < 1 || visited[v] )

    Hope this helps you.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have implemented the same solution as mentioned in editorial for problem "Amr and Chemistry" in python but it is giving me time limit exceeded. Any thoughts? My submission: http://codeforces.net/contest/558/submission/12208553

Also can anyone please tell me about how much the time limits vary based on language(e.g. C++ vs python)?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

LOL

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E can be solved using Square root decomposition also . Here is my accepted solution : http://codeforces.net/contest/558/submission/33019142

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

558B what is wrong with my submission 65573215 ? Why WA8?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, I've found mistake. it was r[i]-c[i] instead of r[i]-l[i]

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I found a very weird bug while solving E. My solution using lazy propagation to sort the string. This is my initial code which gave tle: code.

I thought my implementation might be wrong, but it was correct. I just removed the line with the while(st<r) ( just before the sorting block ) and it got aced.

My st is the start of the block and en is the end of the block where I will put my characters. It shouldn't be a problem because in the end the st becomes r....

( i thought that it might not be the case so I used this code to verify, and it was true that st was becoming r code you can see that I added an if condition in the end, the same as termination of while loop ).

Another weird submission, wierd submission 2 because of the while loop.

I am not sure what the problem is so any help would be appreciated.

→ Reply