jdurie's blog

By jdurie, history, 2 months ago, In English
Tutorial is loading...
Solution
Tutorial is loading...
Solution
Tutorial is loading...
Solution
Tutorial is loading...
Solution
Tutorial is loading...
Solution
Tutorial is loading...
Solution
 
 
 
 
  • Vote: I like it
  • +104
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it -111 Vote: I do not like it

С sucks

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Thanks for the fast editorial!

»
2 months ago, # |
  Vote: I like it -52 Vote: I do not like it

Fix picture for C please

»
2 months ago, # |
  Vote: I like it +112 Vote: I do not like it

Statement of Problem A was incomprehensible. These days, I feel that in cf contests it's not the problem that's hard but the way it's written which makes it harder to understand :/ Had to blindly solve it using the given test cases

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

Tough contest!! Great Explanation!!

»
2 months ago, # |
Rev. 4   Vote: I like it +45 Vote: I do not like it

Let $$$f[i][j][k]$$$ be whether there is a path whose end point is $$$(i, j)$$$ and the sum on the path is $$$k$$$.

We can use bitset to calculate this DP with a $$$O\left(\dfrac{nm(n + m)}{64}\right)$$$ complexity.

Submission: 161091846

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I am not able to get why is the time complexity divided by 64. Would be great if you could explain it.

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

      It's because of use of the bitset. I am not sure but I think each position contributes only 1 bit to the space complexity and not the space required for storing 64-bit integer (size of long long)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      The size of the bitset is roughly $$$\dfrac{(m+n-1)}2$$$. On 32 bit systems, bit operations on bitsets take $$$O(\dfrac{n}{32})$$$, where $$$n$$$ is the size of the bitset. This means each operation takes about $$$O(\dfrac{m+n}{64})$$$. Then, the loop makes it $$$O(\dfrac{nm(n+m)}{64})$$$.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    what is this line doing ?

    f[i][j] = (f[i - 1][j] | f[i][j - 1]) << a[i][j];
    
    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      In this solution the bitset is used as below- - If i th bit is 1 then sum i can be attained - If ith bit is 0 then sum i can't be attained.

      Let's take an example to understand logic behind f[i][j] = (f[i - 1][j] | f[i][j - 1]) << a[i][j];.

      Let's say we want f[i][j], and we have- - f[i-1][j] = 010010, note that 2nd and 5th bit are set i.e sum 2 and 5 is attainable at f[i-1][j]. - And, f[i][j-1] = 001011, i.e sum 1, 2 and 4 is attainable at f[i][j-1].

      We can reach grid[i][j] from grid[i-1][j] or grid[i][j-1]. So- - If grid[i][j] = 0, Then sum 2,5 or 1,2,4 is attainable here which can also be written as- 010010 | 001011 = 011011 - If grid[i][j] = 1, Then sum (2+1),(5+1) or (1+1),(2+1),(4+1) is attainable at [i][j], which is simply (010010 | 001011) followed by a left shift as all (i + 1)th bit will be set now.

      Hope you understood :).

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

    Same way with me and my submission is 161081121

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

    woc ,nong!

»
2 months ago, # |
Rev. 2   Vote: I like it +128 Vote: I do not like it

If the editorial for D doesn't make sense, you can check out this one over here on page 17.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks. Appreciated (I mistakenly downvoted you and now I can't change it.)

»
2 months ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

[submission:161072909]Why is it wrong?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    because k is initialized by a[x][y], that means k equals 0 ( k=a[x][y]; )

    but when all the values in the grid are negative the result will be incorrect.

»
2 months ago, # |
  Vote: I like it +23 Vote: I do not like it

There is a solution that does not require any observation in D2 from D1 — just re-root the tree.|

First, calculate the answer for any root.

If you want to change u to v, push all changes into a stack, recalc dp[u] to what it was before you added v, then recalc v as if it is the root. Then, do it recursively for all children son such that son != u. After you finished, roll back the changes to dp. It takes O(1) to roll back, O(1) to recalc, so it is still O(n)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I solved it in the same way (sadly after contest).

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

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

    not available for python? I entered my submission ID, it said python support disabled

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

    Hello, it generated a wrong testcase for problem C. Ticket We can only have 1 or -1 in the grid, but it showing a testcase with 2.

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

      Hi, the generated testcase is actually correct.

      The input format is the same as the problem, so

      1
      1 2
      -1 1
      

      means that you have one testcase, where the number of rows is 1, number of columns is 2, and the elements are -1 1. (Here, 2 is the dimension of the matrix, not the matrix element).

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

    Actually it wont work for python code as of now right?Anyway must submission id is 162665384 can u tell me where I made a mistake?

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

Can anyone tell the answer to the test case:

8
2 1 3 4 3 6 2 8

according to cf stress test it should be joe but according to me winner will be mike as in 2nd iteration 2nd element will be already 0 that was joes pile.

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

    Here the winner is Mike as you said

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I am really dumb there was a typo in finding the minimum value in my code and due to that i was not able to get ac on b and wasted a lot of time and i suddenly noticed it now.

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

    Huh, I think you got confused by the color coding.

    The expected output is displayed by a green bar, while your output is displayed with a red bar. However, when computing the difference, your output appears to the right, hence it has a green highlight, denoting that the correct answer was deleted and an incorrect one was added there.

    CF Stress prints the expected output as Mike for this testcase.

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

If anyone was curious, you can solve C with the bitset dp: https://codeforces.com/contest/1695/submission/161121586

»
2 months ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

Statement for problem A was hideous, the hard thing is to understand this problem.

Problem B bad sample tests which gives us nothing in understanding the problem also explanation of second test case was very weird and confusing.

Problem C is very weird.

Problem D also as in Problem B no sample tests and explanations.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I have some doubt about the solution to problem A. Consider following case:

1
4 4
0 -14 8 9 
17 -26 20 30 
21 5 -24 -19 
-7 -13 14 -4

Based on the solution, the answer is 12. But if we take a subrectangle with $$$(h, w) = (4, 3)$$$ and upper-left corner placing on $$$(1, 1)$$$, the maximum value inside is 21, which is not the global maximum value(30). So if Joe chooses this subrectangle, Michael will lose.

I think the answer should be 16. Am I missing something?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Michael can instead take a subrectangle with $$$(h,w) = (3,4)$$$. this includes the global maximum wherever the subrectangle is.

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

      Oh, I completely forgot Michael was the one who chooses h, w values... Thanks!

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

    the answer 12 is getting by choosing 3*4 ,not 4*3 (both are different as stated in problem)

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

161122420 what is wrong with this solution for C . i used recursion + memoization

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

    solution will be tle but for the wrong answer initiate dp with false then if the dp[i][j]!=false return dp[i][j] because if at some point we find a path we will need that

»
2 months ago, # |
  Vote: I like it -19 Vote: I do not like it

I'm not gonna argue about the quality of the problems (there's already much argument going on), however I think the pretests for A was pretty much garbage

  1. 161068768 a solution which scans from -32768 got through pretests. this means that pretests didnt even have a testcase with less than -32768 as minimum

  2. 161081758 a weird solution, and I dont understand how it even went through the pretests

  3. 161078731 what even is this

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

Is there any way of using dfs in problem C?i can make a graph for possible path from a cell and apply dfs to check whether the sum is zero or not?

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

    In the worst case(when n,m = 1000), there would be 1998C999(1998 Choose 999) different paths from 1,1 to n,m. (This because we need to make 999 right turns and 999 down turns, so total 1998 turns. Just need to select 999 out of these for a right turn)

    Which would exceed the time limit easily.

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I have done this contest with a really bad result and I think I need to say something. As a habbit, I always initialize the max = -999999999 and min = 999999999, my brain thinks 999999999 > 1e9 and actually I don't understand why I has not had any problems with this before. As you can easily guess, in this contest, I had problems with A.Subrectangle Guess and B.Circle Game. I should have solved A and B in under 15 minutes; I passed pre-tests of problem A, and I never think it will be terrible for me, until now. If I recieved WA in problem A, I would soon find the mistake(max = -999999999), because the idea is clear, I would not have to check the idea, I could concentrate on the code and find my mistake, I just lost 50 points, and next I would easily solve problem B and have over 1h30m to think promblem C or D1. But no, I recieved WA on test 3 in problem B, and although I could prove my idea is correct, I still spent the whole time to find the mistkae in my idea, until some last mintues, I found the mistake in my code, and I passed B on exactly the last minute, and did not have enough time to submit A. As a result, I did not pass the main test of problem A. Anyway, thank you for this contest, if I don't fail in this contest, maybe I will fail in the contests which are more important to me because of this mistake.

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

The tutorial doesn't have any hints and I don't want to see the solutions directly

Can someone give me some hints for problem E?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    hint1
    hint2
    hint3
»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

In problem D, you make your queries first and then you get the distance values, altogether... I'm writing this because I somehow missed/overlooked that crucial point while reading the problem. I guess some others may have unknowingly made the same mistake.

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

0-1 BFS also works for C with a deque.

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

Can someone please explain why 161082582 got accepted but 161062638 did not in prob A UPD: got it

»
2 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

Hey jdurie!

Feedback as a low-ranking coder:
  • »
    »
    2 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I don't agree at all, problem A was very clear and sample test cases for B were just horrible.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem B sample tests were horrible. It was very easy to get them correct. For example, I submited 8 times before getting AC.

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

nice solutions

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

Can someone tell the proof written for Problem C in the editorial in simpler words stating that we can get the sum as 0 if the maximum and minimum path sum ending at (n,m) cover's 0 if the max_sum >= 0 >= min_sum

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

    Basically they are saying that we can change the path that gave minimum sum to the path that gave maximum sum and on each step of changing that , sum will change by 2,0,-2 .

    Since we know that number of cells in any path = n+m-1 (which is even)

    Hence both min_sum and max_sum is also even ,

    and we are changing min_sum to max_sum by +-2 , so we will definitely hit 0 given that 0 is in the range of [min_sum,max_sum]

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

      " so we will definitely hit 0 given that 0 is in the range of [min_sum,max_sum]"

      Thanks! I was not getting this.

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

      let's say min_sum is -4 and max_sum is 4, so there exist a path which gives me zero sum,but how can we sure of that diagonal swaps , it may be possible that we are only able to do negative swap 1 time(change sum at most by +2) resulting -2 or positive swap resulting 2, but we are not reaching zero. can you please help me with that?

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

        we will always reach zero because we can always reach from minimum to maximum by swapping diagonally and in each swap we can only do (-2 or 0 or +2) hence it will always be possible to reach 0 , which comes in between minimum and maximum given that ->

        • min <= 0 && max >= 0 .
        • both minimum and maximum are even numbers.

        i hope it Helped =)

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

I guess in problem C's solution the condition for no path should be 0>minnm or maxnm<0 and not 0<minnm or maxnm<0. Please fix ig this is a typo.

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Very understandable and clear editorial. Thank you! :)

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

I have written the recursive code for problem C. Can someone help me in memoising it. I know that the dp array will be 3D array as there are 3 states i,j, and sum at that point. Here's the recursive code for reference-Code

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I have not yet learned much, but i keep seeing dp in the discussions C and D. Can anyone explain what is dp ?

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

Can anyone explain the solution for E? Don't really understand why the order of dfs matters.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I would explain it in a slightly different way, which is similar to the editorial's solution.

    For any dominoes $$$(a,\,b)$$$ we have, add an edge between node $$$a$$$ and $$$b$$$. Merging the two solutions, we found out that these dominoes form cycles. Therefore we may think about finding the Eulerian Cycle of the graph obtained by two copies of the dominoes. If we successfully found it, the solution is the odd edges and the even ones of the Eulerian Cycles. However, these cycles we found may not guarantee that two dominoes from the different copies have different parity. It can be solved by letting the same dominoes from the different copies be adjacent in the adjacent lists and all the adjacent lists have the same order of edges. Note this is the same we do in the editorial's solution. For each cycle, if the length is $$$2$$$ then there must be no solution, otherwise, we arrange them in a $$$2 \times \frac{\text{length}}{2}$$$ grid. It is always possible since each connected component contains an even number of edges.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The proof part of problem C is brilliant and that's what made the problem a bit hard in my opinion.

I was unsure before submitting my solution and got gently surprised when it got accepted.

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

Come on, I didn't even try to implement O(n^3) solution, since I thought it would be too slow. Turns out that it is under 1s even in java..

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

Why not just set $$$\sum n\times m \leq 10^7$$$ or else everyone will pass with $$$O(\dfrac{nm(n+m)}{w})$$$???

see this : https://codeforces.com/contest/1695/submission/161085118

I thought of this kind of way to solve in square time complexity, but i still decided to write the code above. However, you can just make the constraints much bigger, and maybe there will be most people coding the tutorial's solution.

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

    I don't think this solution should be hacked. At least it showed an important way to improve the time complexity($$$O(\frac{1}{\omega})$$$). In my point of view, various solutions are also important and inspiring.

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

For problem D1 Div2, in the editorial, can anyone explain the benefit of having this condition: we can assume that either v or some vertex not in the subtree of v has already been queried while calculating the answer.

Also D2 Div2, why is this statement true: The way we compute values in the DFS ensures that at least degree[root]−1≥2 subtrees of the root will have at least one query.

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I think Problem A has a subtle detail and would like to share it here.

We are not choosing a minimum area such that any rectangle >= that area covers the maxval.

Instead, we are choosing a minimum pair (h, w) such that any h*w rectangle covers the maxval, and by saying "minimum pair" I mean the pairs are ordered by the areas that they form.

Those two are different! For example, consider the following case.

1  2  3  4  5
6  7  8  9  10
11 12 99 14 15
16 17 18 19 20
21 22 23 24 25

If we follow the standard answer we get the pair (h, w) = (3, 3) such that any 3*3 rectangle covers 99. But it is not "a minimum area such that any area >= 9 covers 99", for example you can consider the following area.

1  2  3  4  5
6  7  8  9  10

It has an area 10 >= 9 but does not cover 99.

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

    It's not minimum area, it's minimum value for h and minimum value for w.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Though my rating dropped after the contest, I think it's a pretty good round.

Because it made me realize my poor ability in dp on tree :)

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

    That's a good example of positive mindset. I see a lotta people perform bad and start trolling the authors, problems or Codeforces itself.

»
2 months ago, # |
  Vote: I like it +60 Vote: I do not like it

Why the timelimit of E is 8s?

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

Hey everyone! Can someone please explain the solution for problem C? I do not see how does this proof in the editorial conclude there exists a zero path. Thanks in advance!

Statement from editorial I am confused about:

Therefore, because both minnm and maxnm are even, and minnm≤0≤maxnm, at some point in this sequence of operations, the sum of the path must be zero.
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's just like the intermediate value theorem.

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

    Oh I get it now. Lets say your min sum was -10 and max sum was 10. You will only move from -10 to +10 in increment of +2 because at an point in time the sum has to remain even. This way we will always cross the 0 mark. Hence it is possible.

    Ingenious proof! loved it. I am new to codeforces and I am loving it here! (for now :P)

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

      The part I'm not convinced with is the fact that, given a path P with sum less than 0, there exists a path P' where the sum is sum(P) + 2.

      Otherwise, yeah, the proof is dope!

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

got an FST on div2 A :(

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

In D2, how does querying any vertex with degree >= 3 will ensure the answer to be minimum. Why don't we need to do it for all vertices with degree >= 3?

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

    The $$$ans[v]$$$ can be understood as "the answer of an subtree with root $$$v$$$ if there are at least one query vertex not in this subtree." The condition that the degree of top most vertex $$$\ge 3$$$ is to guarantee for all the subtree, there are a least one query point not in it.

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

Can someone recheck the test cases for C ? Even the code given in editorial gives wrong answer for the last test case.

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

The Solution Given for "C", does this kind of algo have some name(belong some where like div & conq etc) or just plain problem solving

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

    Intermediate Value Theorem

    Other IMVT problem: https://www.codechef.com/problems/B01T

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks bhai!

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

      I thought the intermediate value theorem was for continuous valued functions only? This is why I'm still not convinced with the proof for C. How can we say that just because

      $$$min_{nm} < 0 \text{ and } max_{nm} > 0 \Rightarrow \exists \text{ a path } p \text{ such that } \Sigma p = 0?$$$

      Can we prove that for every value between min and max there exists a path whose sum equals that value?

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

        The conditions which you're assuming is not sufficient. You are missing the change at every steps. Change at every step is 2, -2, 0. Previously it was negative even number and later positive even number and everytime there is a change of 2, -2, 0. So you'll get 0 for sure.

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

          Don't we have to prove that it's always possible to find a path with change +2 or -2?

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

            Its already proven in the editorial bro.

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

              Hm so the proof is done by saying that you can swap two adjacent "but different" squares. However, they don't show that there always exists an adjacent different square, which I think would be required, no?

              (Thanks again for your responses + help)

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

        The idea is that suppose you already have a path to achieve the max sum, and a path to achieve a minimum sum; the claim is that any sum (of the same parity) in between the max and min are achievable.

        Now, why should this hold true? The intuition here is that because paths only go right and down, you can convert the two paths between each other by a multiple operations of flipping a "turn" (i.e. if a turn goes right then down, make it go down then right). In particular, we note that each time we flip a turn, it can change the sum by at most absolute value 2. This happens when we step on a -1 instead of a 1 (or vice versa) as a result of flipping. (Note that a single flipping operation changes exactly one cell on the path.)

»
2 months ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

.

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

Learnt a new thing which I was doing wrong for years.

#define inf 1e9 + 7

int val = -inf;

Here val is not -(1e9 + 7) but -1e9 + 7

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

    That's beacuse inf is not an integer variable. It's just the substitution of 1e9+7.

    So when you write int val = -inf; it is actually parsed as int val = -1e9 + 7;.

    Could be avoided using something like const int inf = 1e9+7;.

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

Good Question on DP+Matrices => https://codeforces.com/problemset/problem/429/B

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

Although it is not required, Problem A can be solved using Sparse Matrix as well. See my submissions

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

did anyone know why D2 only dfs a vertex more than two sub is ok, but not dfs all vertex which has more than two sub. i think the answer didn't say clearly

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

How does considering any node of a tree with a degree greater than or equal to 3 as the root in 1695D2 - Tree Queries (Hard Version) always result in the minimum number of required queries?

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

Problem C was a good one.

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

Does anybody know what's wrong in my C-Problem Code

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

Can someone please explain the proof for C? I'm not convinced how if there is a min path and a max path with sum less than 0 and greater than 0 respectively, how we can assume there exists a path with sum = 0.

Thank you.

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

    since the sum is changing by 1 unit its always possible to get all the sum in between minSum to maxSum

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

For problem D, what is the smallest k(the worst situation in any possible hidden-X with an optimal strategy) if we are able to use online query, instead of quering all the node at once?
Are they the same?
If not the same,what is the best optimal strategy?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Let's try the following reasoning — root the tree at u — that is our first ask. For every ask concerning two sons, we can answer no as long as there are some other possibilities. This is very similar to our offline dp — we cannot toss out more than all sons by one query. So I think that the answer is the same.

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

For Problem-D2, why is it that performing our greedy DFS for any of the nodes with degree greater than 3 works?

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

Problem-B

https://codeforces.com/contest/1695/submission/161367637

Can someone kindly explain why my submission is hitting WA in pretest 2? Or provide a case where it fails?

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

How to Solve Problem C using BFS algorithm?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D is a known concept in graph theory called Metric dimension: https://en.wikipedia.org/wiki/Metric_dimension_(graph_theory)#Trees

»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

D has appeared in previous competitions: https://atcoder.jp/contests/apc001/tasks/apc001_e