gepardo's blog

By gepardo, history, 21 month(s) ago, translation, In English,

Tutorial for the tasks of the contest. If something isn't clear, you can write in comments :)

Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
 
 
 
 
  • Vote: I like it  
  • +82
  • Vote: I do not like it  

»
21 month(s) ago, # |
Rev. 3   Vote: I like it +17 Vote: I do not like it

Why contest announcement blog is missing? Edit: now it's back!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When should we use it = st.lower_bound(tmp) and it = lower_bound(st.begin(),st.end(),tmp)?

I know first one has logarithmic complexity and second one 'maybe' linear. But in some cases, we can use only second one. I have read this. What exactly is meant by non-random-access iterators?

AC using first

TLE using second

So I was expecting maybe this will give TLE. But it didn't.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    it = lower_bound(st.begin(),st.end(),tmp)

    for std::vector it is logarithmic complexity

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    it = lower_bound(st.begin(),st.end(),tmp)

    This is regular operations for vectors, arrays, etc. It only works in log N if you can "jump" to a random place in O(1). For example I can look at the x-th element of an array by using array[x-1] in O(1).

    it = st.lower_bound(tmp)

    This is special function for sets, multisets, maps, etc. It uses a special walk through the tree which C++ constructs for you which has log N complexity. If you use the first method, it will get TLE because you can't "jump" to the x-th element of the set in O(1).

»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Why in A is O(1)? I thought it is O(N), isn't it?

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

for problem E, it is possible that you can't decrease the diameter by 2, no matter how you paint the nodes.

Example:
14
0 1 1 1 1 0 0 0 0 0 0 1 1 1
1 2
1 3
1 4
1 5
2 6
2 7
2 8
3 9
4 10
5 11
6 12
7 13
8 14

the diameter of the tree is 5, and no matter which node you paint, the diameter can't be less than 4.

I think the answer is the radius of the tree and each operation can decrease the radius by 1.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why? In your tree, if I use paint(1), tree diameter will decrease by 4 (it was 6 and became 4). Or I am wrong?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the diameter was 5, right?

      12 — 6 — 2 — 1 — 3 — 9 (the longest shortest path)

      after you paint(1), the diameter is

      12 — 6 — 2 — 7 — 13 (the new longest shortest path)

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, got it, you are right.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, I was wrong :)

        But in your example the diameter CAN be decreased by two. Consider paint(2), the diameter becomes 12 — 1 — 3 — 9.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          Rev. 2   Vote: I like it +15 Vote: I do not like it

          node 1 and 2 are symmetric. paint(1) and paint(2) should be the same.

          the new diameter will be 9-3-1-4-10

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
            Rev. 2   Vote: I like it +8 Vote: I do not like it

            oh, you are talking about that specific tree

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think it is always possible to reduce the radius by 2, choosing the graph center, if the radius is even.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you must be talking about diameter, not radius. As I said before, it is possible that at one step, you can only reduce the diameter by 1, not 2. But you can always reduce the radius by 1.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, diameter, sorry. You need one step to make diameter even. After that, on each step, it`s always possible to decrease it by 2, so it will remain even. So the answer still will be (d + 1) / 2.

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          I didn't challenge the result. (d + 1) / 2 is absolute correct. (because that is also the radius of a tree). but the argument provided by OP is not entirely correct.

          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you, I'll fix it soon.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I am getting MLE. Can someone help? code

Thanks!

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think you don't need to save all the point, you only need to consider the nearest chess in eight directions.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved C using BIT by iterating over all second type of spells. BIT maintains the lowest value I can achieve to make potion using cost  ≤  some vale. code

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Has anyone solved problem E,using dp on compressed tree ?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Great tutorial. Thanks.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Darn I came up with the correct algorithm to solve C but could not implement it properly :(

»
21 month(s) ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

pretests of Problem F were a little bit weak... I even passed them all without checking the correctness.Sad story.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is the distance in Q4 defined as :

inline int dist(int x1, int y1, int x2, int y2)
{
	return max(abs(x1 - x2), abs(y1 - y2));
}

Instead of the normal eucliden distance function sqrt(pow(x1-x2,2) + pow(y1-y2,2)); ? I got wrong answer since I used eucliden distance and got an overflow. Why does this distance function work (the one defined in editorial : Q4 : dist function above)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In this problem it doesn't matter what distance formula you take. My distance formula is correct because if the two pieces are on one line (horizonal, vertical or diagonal) it can correcly say which one is further from the king (you can check it). As for me, I used this formula because it doesn't give an overflow.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To summarize: we only care about cmp(dist1, dist2). The precise value is not important.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    here we are only calculating distances which are diagonal to the given point. So instead of comparing a*sqrt(2) and b*sqrt(2) we are just comparing a and b;

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually you can change x1, y1, x2, y2 to long double. GNU++11 has sqrt and pow for long double. Not sure if FP error is tolerable though.

»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

In problem E, I still don't understand the meaning of "changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color". Could someone please explain how this operation works for me?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    To paint node u, let it be of color white. Then do dfs from u and cover all those nodes that are white and reachable from u. Do not dfs to black nodes. Finally as you traverse nodes, paint them to black.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      i did the same thing but by doing it , i get ans = 4 for test case 3 whereas it is 3, can u explain how is it 3?

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I ran into the same result at first. For me, it turned out that it is not enough just to count the connected components with the same color. You also have to account for solutions where a component is repainted multiple times, such that the component grows with each repainting. The tutorial is actually pretty good on this. Hope this helps.

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I got confused too and had to basically ignore this whole problem.

    The pitfall is, while the “such that” clause is intended to describe the selection of u, non-native speakers may confuse “such that” with “so that”, and interpret the clause as the result of the operation. Compare:

    • Change the color of all vertices u, where each u is a vertex such that all vertices on the shortest path from v to u have the same color.
    • Change the color of all vertices u, so that after the operation, all vertices on the shortest path from v to u have the same color.
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C: http://codeforces.com/contest/734/submission/22247048 Can someone help me understand why this solution fails ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It's gonna TLE anyways i think . Your solution complexity is O(m*k), when all spells of the first and second kind have cost <= s .

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Regarding WA , You don't consider the possibility when the answer comes from just using a spell of the first kind . remove if(flag==0)break;

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank u everyone..!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I really appreciate problem E, thanks for such a good problem!

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

In Problem E, please explain this " This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v and u) ". thanks

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In the last problem how do you go from "from where ..." To "Now it's not hard to find ai: ..."

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In (Problem C — Anton and Making Potions, what if we do not use the upper_bound function?

What if I instead sort the first array based on points (m log m), and use two pointers? (order m + k).

I felt this should also work, since the complexity is O(m log m + k), but it is giving me TLE.

Could someone please help me understand why this isn't working?

My Code — CODE

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    You are calling vector::erase in the middle, which takes O(len). If you filter vp and put the results in a new vector, this program should work.

    btw, you can keep those spells and still get the right answer, so why bother removing them? :)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much!!!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

It was hard to find a solution during contest, but after reading the editorial the solutions were pretty clear and easy to understand. Also implementation was not diffcult. This is the first round I was able to solve all problems. Thanks for really well-made problems, alex256.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is my solution giving WA for, it uses the same binary search logic as in the editorial ? http://codeforces.com/contest/734/submission/22262919

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Very well written editorial. Thanks!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for your editorial.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For F, why is complexity ? We have a loop over the digits, which takes . However, can someone explain why val is O(n)?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Yes, you are right, I'll fix it soon.

»
21 month(s) ago, # |
  Vote: I like it +32 Vote: I do not like it

Did anybody do E with dp on tree??

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Had to say — a perfect implementation of question C , learned a lot .thanks alex256

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

any idea what does test 43 in D do ? I keep getting WA in it

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

D. Anton and Chess when I run code in my codeblocks the answer is right for test 2. But when I submit the same code to the system. the system is run different result from me. Can someone help me? http://codeforces.com/contest/734/submission/22280387

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C: http://codeforces.com/contest/734/submission/22284393 Can someone help me understand why this solution WA ?

using greedy & two pointer

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem E where is my code is wrong http://codeforces.com/contest/734/submission/22295869

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi! Can someone help me to know why this submission give wrong answer! Problem D — http://codeforces.com/contest/734/submission/22316916

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's one of those days which you make dumb mistakes that makes you feel bad.

    2

    2 2

    R 1 1

    B 3 3

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      OMG!! big mistake! Thank u for your help :-)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! Can someone help me to know why this submission give wrong answer! Problem E — http://codeforces.com/contest/734/submission/22295869

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would you mind explain a bit about the logic behind your solution? It appears that you have a different approach compared to the editorial.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i apply the same logic as given in the editorial but in short way means first i find the leaf node using dfs1() than i find the diameter using dfs2() in such a way that if i go from node1 > node2 and both have diff color than increment in cnt and after this print cnt/2 (diameter/2) in ans.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Hmm, I don't think that's what your code means. What your code does is just selecting the last visited node in the first bfs rooted at 1, as the root, and search for the furthest node from the new root in the compressed tree. To my understanding that is not how you find the diameter of the tree.

        To find out the diameter of a tree, first assign an arbitrary node as the root, then for each node, check for the sum of the two children which has the maximum depth. The maximized value is the diameter.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How the complexity of problem c code is O(m.logK + k) ?

  • »
    »
    21 month(s) ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    foreach m first spells, binary search through a list of size k. O(mlogk)

    foreach k second spells, consider each individually. O(k)

    Edit: Formatting

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In D, why answer of test3 is 3? I found it is 4, isn't it?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain to me what the paint operation does in the problem E (Anton and Tree)? In particular, I don't understand this: We denote it as paint(v), where v is some vertex of the tree. This operation changes the color of all vertices u such that all vertices on the shortest path from v to u have the same color (including v and u). Does the color of v always have to change? In the example tree, why does after paint(3), all but node 6 get painted black? Take the shortest part from 3 to 6, is it also valid to make 5 white?

Thanks in advance!

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me figure out why is this WA for C problem? Went through all the comments , can't figure out what the problem is.Thanks!(http://codeforces.com/contest/734/submission/22342679)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C: I am getting wa in test case 3. How the result is 10 in this case????

»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Regarding Problem 379F — Anton and School, Why can't the correctness be checked directly by generating b & c using;

bi = (ai and a1) + (ai and a2) + ... + (ai and an) ci = (ai or a1) + (ai or a2) + ... + (ai or an)

If one doesn't derive the correctness formula as in the editorial, then does this naive approach result in time limit exceeded?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The correctness is checked exactly in this way.

    If you compute b and c in the naive way, just using the formula from the statement, you'll do that in , which won't fit in TL.

»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Regarding Problem 379E — Anton and Tree, the editorial shows a proof for upper limit on number of operations needed i.e. (d+1)/2, but which step of the proof states that this is exactly the number of operations needed?

Could anyone arrive at an iterative solution to the DFS instead of the recursive ones shown in the editorial?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was proved in the editorial that we can always paint the tree in operations, please read it carefully.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "Now, we'll prove that it's always possible to paint the tree in operations. Find such vertex that the shortest path from it to any other vertex doesn't exceed . Such vertex can always be found, because otherwise the tree diameter won't be less that d + 1, which is impossible. Now see that if we paint this vertex times, we will paint the tree in one color."

      I am afraid I can not really understand this explanation very well. Do you use a proof of contradiction? If you could please rephrase it a little or provide any external material to help me understand it better, I should be very grateful.

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the help, I was stuck on C.

»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

for (int i = 0; i < 31; i++) for (int j = 0; j < n; j++) if ((a[j] & (1LL << i)) == 0) bits[i][j] = 0; else bits[i][j] = 1;

Can someone explain me those lines for me from problem F??

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bits[i][j] means the i-th bit of a[j]

»
21 month(s) ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anyone explain to me why the answer to problem E is (d+1)/2? Thanks a lot :D

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F, why is it not sufficient that summation of d(i) be divisible by 2n and a(i) be divisible by n and non-negative i.e. why do we have to check for correctness ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    c[i] must be greater than b[i], because ai or ak >= ai and ak. Using d[i] you lose this property. If you swap b[i] and c[i] for a problem with solution you would obtain a problem without solution but same array d.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not only this. Consider this test case:

      4
      1 4 4 4
      7 4 4 4
      

      Answer is -1 but the solution without restoring the answer will output 1 1 1 1

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F: Is there a intuitive/combinatorial way to see that (a & b) + (a | b) = a + b ?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First you add all the powers of 2 once that occur in either a or b (a | b), but then you might have missed some that occured in both! So we add all the powers once more that occured in both (a & b)

»
20 months ago, # |
  Vote: I like it -8 Vote: I do not like it

For problem C : O(m*log(k)) solution

»
20 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Hi, could somebody help me figure out the problem with this submission for problem C: Anton and Making Potions.

Algorithm:

  1. Try minimum for only first spell — O(m)
  2. Try minimum for only second spell — O(k)
  3. Try minimum for both spells using a greedy search — O(m log k)

Here is the submission number 22677789.

  • »
    »
    20 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I updated some code and still it WA. Can anybody please help?

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Result could be assigned to a overflowed value (n*x)

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It still fails, though on another test case.22677978.

        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          100 1 3

          100 100

          1

          10

          1 90 95

          1 90 90

          Try this case, you will see why your binary search is flawed.

          • »
            »
            »
            »
            »
            »
            20 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ah! I somehow made the assumption that numbers will be unique. Thank you very much! AC now.

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting wrong answer in test case 6 of of Problem 734C. My submission

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! My code for problem E is getting RTE in test case 2. But the code runs successfully on my pc, including test case 2. Can anyone help me find out what's the problem? Code: http://codeforces.com/contest/734/submission/22926048

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F good problem!

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody explain problem D , test case is giving WA (5th test case) http://codeforces.com/contest/734/submission/23343680

»
19 months ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem C. Anton and Making Potions

this line gets WA in case 16

 int j=lower_bound(d.begin(),d.end(),s-b[i])-d.begin();

between editing it to

 int j=lower_bound(d.begin(),d.end(),s+1-b[i])-d.begin();

gets AC..why ?

also here the full submissions:

http://codeforces.com/contest/734/submission/23527242 (WA)

http://codeforces.com/contest/734/submission/23527311 (AC)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Its because lower_bound gives the first occurrence of the number to be found. It may be a case where there are multiple c[i] possible for the same money_left.

    We have to find the last occurrence for this money_left.

    Let's say the array c and d are:

    c=[1, 2, 3, 4, 5];

    d=[10, 10, 11, 12, 13];

    Now if the money left is 10 , then the max value in c will be 2.

    Using int j=lower_bound(d.begin(),d.end(),s-b[i])-d.begin(); will give 1.

    So to get the last occurrence we have to add 1 to the money_left which will return the last occurrence of the required answer.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain a dynamic programming approach to problem E -thanks in advance :) !

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F: Anton ans School: Can someone please explain why do we need to recheck the found the solution i.e array a by rebuilding array b and array c from array a. Can't we simply say that if all the a[i] found are integers then the array a will be a valid solution else even if a single a[i] happens to be a non-integer then there will be no valid solution? Thanks in advance!