Tlatoani's blog

By Tlatoani, 7 weeks ago, In English

We hope all of you enjoyed the round! This round has been a long time in the making -- the oldest problem in it is H, which was actually originally proposed for the rounds that eventually became Codeforces Round #655 (Div. 2) and Codeforces Global Round 10.

The tutorial for E and implementations for all problems are now available.

A - Windblume Ode
B - Omkar and Heavenly Tree
C - Omkar and Determination
D - Omkar and the Meaning of Life
E - Moment of Bloom
F - Defender of Childhood Dreams
G - Omkar and Time Travel
H - Omkar and Tours
 
 
 
 
  • Vote: I like it
  • +349
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Thanks for the great contest and fast editorial!

»
7 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Thanks for the fun contest!

»
7 weeks ago, # |
Rev. 2   Vote: I like it +208 Vote: I do not like it

The bonus of D !

Asking $$$A=[1,1,\dots,k]$$$​​​​ in which $$$k=2,3,\dots $$$​​​​, when the first time get answer $$$0$$$​​​, there is $$$p_n=n-k+1$$$​​​ if this is the $$$k$$$​​​-th query. What's more, if the answer to $$$u$$$​​​-th query is $$$b_u$$$​​​, then $$$p_{b_u}=p_n+u$$$​​. Now we get the position of $$$b_n,b_{n}+1,\dots n$$$ and only make $$$n-p_n$$$ queries.

Then asking $$$a_i=n$$$ if $$$p_i$$$ is determined, $$$a_i=k$$$ if else, from $$$k=1$$$ to $$$k=p_n-1$$$. If the answer to $$$u$$$-th query is $$$c_u$$$, then $$$p_{c_u}=p_n-u$$$.

Now we get the position of all numbers and only make $$$n$$$ queries.

And here is my solution

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    great solution! I used similar way to find A[n], but I performed another n — 1 queries to determine other elements.

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    The solution 1 of D can also be optimized to omit $$$n-1$$$ queries.

    You can record for each $$$j$$$, the index $$$prev_j$$$ such that $$$p_{prev_j}=p_j-1$$$.

    When you set $$$y\to next_x$$$, set $$$x\to prev_y$$$, and vice versa.

    You can ask like the solution 1, but since queries only find smaller index of the two equal $$$s_j$$$, you can visit $$$j$$$ from $$$n$$$ to $$$1$$$. If the $$$next_j$$$ is determined by previous queries, you can omit the query of the first type(i.e. a query with all $$$1$$$s except that $$$p_j=2$$$). If the $$$prev_j$$$ is determined by previous queries, you can omit the query of the second type(i.e. a query with all $$$2$$$s except that $$$p_j=1$$$).

    Since for each $$$x$$$ from $$$0$$$ to $$$n$$$, the relative position of $$$x$$$ and $$$x+1$$$only requires 1 query to determine(when $$$p_j=1$$$, we should also ask about $$$prev_j$$$(which shouldn't appear), we assume that there's an $$$0$$$ which is $$$prev_j$$$, and the same to the index j that $$$p_j=n$$$), you can solve the problem with $$$n+1$$$ queries.

    My solution

    (I only know a little English; sorry for that.)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -34 Vote: I do not like it
    if(tot>n+n){
    		cerr<<"fuck";
    	}
    

    Nice...

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

Hello Codeforces! I'm having a problem when adding problems to favorites and that is that no more than five are added!!! ಥ‿ಥ I would like to have a selection of problems, which for my taste are interesting to solve, so I can give them a look in the future. Any comments about this?

Thank you very much in advance! (~ ̄³ ̄)~

»
7 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it
Spoiler

By the way, the girl is that "Hu Tao" in problem E.

»
7 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

Really a tough contest.. waiting for rating to go down....

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

Hi, Can someone point out mistake in my Submission. I feel I might have over complicated the problem lol. https://codeforces.com/contest/1586/submission/132264009

UPD: I passed the problem without segtree, turns out I was obviously Over complicating it :)

»
7 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

Nice problems! E and F should've been swapped imo. E was so tedious to formulate and code. Think F would have far more solves if it were in place of E. Took an hour on E and missed F by a whisker cause of one dumb typo ~>_<~

»
7 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

The editorial for problem D does not respect the requirement $$$1 \leq a_j \leq n$$$ on the queries. (But it is trivial to fix this.)

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

    Problem G is somewhat similar to 1552F - Telepanting from a recent CF contest.

    EDIT: They are not as similar as I at first thought. The processes are relatives, though.

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

    Good catch, should be fixed now.

»
7 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I am sorry but in problem E the editorial does proves only the fact that if every vertex appears even number of times, then answer is 0.

How to prove that ANY spanning tree works if we wanna find out the minimum number of queries to be added? This is the hard part.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it
    A more rigorous proof for E
    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you just proved what the editorial proved. I was asking for the proof of the second part: when the answer is NO, and we have to find the minimum number of queries to be added. why does dp in any spanning tree work?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        The editorial is indeed incomplete in the part when the answer is NO, but in my opinion it is much easier than when the answer is YES.

        When the answer is NO, we just need to add queries so that all $$$f_v$$$ are even. The minimum such number is the number of values of $$$v$$$ such that $$$f_v$$$ is odd, divided by 2.

        We need at least that many extra queries since each query added can change at most two $$$f_v$$$ values. On the other hand, we can achieve this number of queries by pairing up the odd $$$f_v$$$'s (there are an even number of them since the sum of all $$$f_v$$$ is even).

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

          Wow, I didn't realise that there is no need for tree dp. Thanks a lot.

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

          Thank you. That's way better than the editorial

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Any (nonsimple) cycle in a tree visits every edge an even number of times.

    If every vertex is the endpoint of an even number of paths, the paths can be arranged into cycles: to form a cycle, take any path, say from $$$a_1$$$ to $$$a_2$$$. Then take any path from $$$a_2$$$, say to $$$a_3$$$. Repeat until $$$a_t = a_1$$$. This must happen, as the only vertices that an odd amount of paths start after the first $$$j - 1$$$ edges are $$$a_1$$$ and $$$a_j$$$.

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

      But this is the proof for YES case. I was talking about how to prove when the answer is NO, that is OK to take any spanning tree.

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

        The spanning tree is only used for the YES case. Read the solution more carefully.

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

          Actually in my solution, I used spanning tree for my NO case also. I did dp on that tree. So I was confused.

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

can anyone help me with solution C 132264422

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

    u only checked for indices which are "." but u should also check for "X" too a simple example is this XX XX your code will give YES for it but ans should be no as following will also produce same EN grid XX X.

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

      sorry ,I am not getting. please,can you elaborate?

»
7 weeks ago, # |
  Vote: I like it +127 Vote: I do not like it

My approach to F was different, and allows for a trivial lower bound proof.

Fix the number of colours $$$c$$$ you will be using. For every node $$$i$$$, define the array $$$LEN[i]$$$ such that $$$LEN[i][t]$$$ is the length of the longest monocoloured path of colour $$$t$$$ from node $$$i$$$. In a valid solution, we have $$$0 \leq LEN[i][t] < k$$$.

Take any optimal solution and consider these arrays. Let $$$t$$$ be the colour of the edge from $$$i$$$ to $$$j$$$. Then $$$LEN[i][t] \geq LEN[j][t] + 1$$$. This immediately shows that we must have $$$LEN[i] \neq LEN[j]$$$ for all $$$i \neq j$$$. Since there are $$$k^c$$$ different arrays, any valid solution must thus have $$$n \leq k^c$$$.

Also, given that $$$n \leq k^c$$$, we can construct a solution by assigning the possible arrays in lexicographically decreasing order.

»
7 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Although I failed this contest, I really liked the originality of problem B !

»
7 weeks ago, # |
  Vote: I like it +74 Vote: I do not like it

Great contest! For those who prefer video explanations, I explain solutions to all problems except I and G at the end of my screencast here.

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

My first time to solve an interactive problem! Stuck at E and tried G but withdrew...

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

my solution to D is working in my device properly but when i submitted it showed TLE on permutation {1,2} anyone kindly help 132260554

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

    The last (truncated) query would be "? 3 1". That violates constraint stated in the problem: $$$1 \le a_j \le n$$$.

»
7 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Here are the video solutions to the first 4 problems. solutions

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Why problems by hu_tao don't have omkar?

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

    My problems were originally a part of a standalone div2 round, but then we merged our problems into the same contests. You'll notice the same thing happened in round 724

»
7 weeks ago, # |
Rev. 2   Vote: I like it +62 Vote: I do not like it

My feedback on A-G:

  • A: The idea is fine but I don't like that we have to print out the subset (I can understand the reason behind this though).
  • B: This feels like a hit or miss problem for me. I almost thought that we could ignore the tree condition and construct a line instead. Fortunately, I took my time and tried to use the special condition.
  • C: This seems a bit difficult for its position. I would rate this somewhere between A and B in a Div 1 round. Consider that we have 6 problems after this and only 135 min, I would prefer an easier one.
  • D: Nice problem that allows many approaches. Mine was also to find $$$p_n$$$ but in a different way from the one above.
  • E: This one feels oddly crafted for me. You have to think why it's okay to just keep a tree (I tried to prove it but I doubt everyone would do, because printing out the paths would be too difficult if it's not true). I would rather be given a tree and asked to print out the paths in the "NO" case.
  • F: I love how simple yet elegant the solution for this is. Props to the author for such a great problem.
  • G: Harder version of 1552F - Telepanting but the overall idea is quite similar. The strong sample tests definitely help, too. I wish I went for this instead of F in the contest. 27 ACs seem to be a problem position effect instead.

UPD: added G

»
7 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Another way to construct a coloring for F is to think about the indices $$$0$$$ to $$$n-1$$$ in base $$$k$$$. Color the edge from $$$a$$$ to $$$b$$$ by the position of the most significant digit that changes. There is no path of length $$$k$$$ with only one color as the most significant digit that changes can only increase $$$k-1$$$ times.

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

This might be a stupid question but could someone please clarify B for me? If a , b, and c are distinct then (a,b,c) can never eliminate paths which consist of one edge for example 1, 2 or 1, 3 so why would this solution where you root the tree at 1 not work? For example, for the first test case with 7 nodes and 4 restrictions couldn't we make paths, (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) since the restrictions don't apply to such paths?

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

Wow, how beautiful the solution to F is!

»
7 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Thanks for the interesting problems and +114 rating!

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can I asked for a solution in problem B if (m >= n)?

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

    can think of m<2*n

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

      Can you show your idea :D?

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

        actually when i wrote that comment i thought the wrong way but after thinking a lot i concluded that for m>=n there exists such an input for which solution is not possible ex: suppose n=m=6 consider the following 6 constraints {(1,2,6),(1,3,6),(1,4,6),(1,5,6),(1,6,2),(2,1,6)} here considering first 4 no node can be between 1 and 6 so u are forced to connect 1-6 if done this u cannot add 2 to either side as it will always violate the either of the last 2 constraints,,,,, may be there is a solution for some special cases for m>=n

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Here's a solution sketch for $$$m \leq n + 1$$$.

    m = n
    m=n+1

    It may be possible to push this idea a bit further, but it seems likely to get hairy fast.

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

      Thanks, I can understand your idea. When I first saw this problem, I was confused before reading its constraint.

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

I'm curious about the special judge for problem B.How to check an output is valid or not quickly(I can only thought about a data structure which is O(n log^2 n))?

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

    Notice that $$$b$$$ lie on the simple path between nodes $$$a$$$ and $$$c$$$ if and only if $$$dist(a,b)+dist(b,c)=dist(a,c)$$$.

    So all you need is a method to get LCA of two nodes.

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

Thank you , Hutao , for this fantastic contest . The division degree is good.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

In problem H,I have a different way on maintaining the information.

After off-line the queries,it requires us to find out the maximal toll on the road to the reachable cities with the maximum enjoyment value.And the maximum enjoyment could be saved on Link-Cut-tree with set maintaining the maximum value of each node subtree,while the maximal toll could be found at the same time.

Unfortunately,I would have thought that 3 seconds were enough for n log^2 n.It took me more an hour to get the program faster and faster.In the end,I control the size of each set no more than 3,because there is no edge cutting operation,with the time complexity O(n log n).

I have only solved A and H,and I have known I'm doing wrong.Now,I'm learning how to use binary search.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    3 seconds are indeed enough for O(n log^2 n).
    I just solved problem H (as practice), and I used DSU on tree to bruteforcely merge the cities with maximum enjoyment in two sets.
    The time complexity is O(n log^2 n) with a big constant from vector operations, and it runs surprisingly fast (<500ms).

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

      With set,maybe LCT has a larger constant and the complexity is more than O(97 n log n)(Top-Tree's complexity).I'll use these data structures more carefully next time.

      And thanks for solving my puzzle.

»
7 weeks ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

A stupid $$$O((n+q) \log^2 (n+q))$$$ solution for H:

First find out the answer to the first question using dsu. Then do centroid decomposition to find out the second answer. Let $$$mx_u$$$ and $$$mi_u$$$ respectively be the maximum toll and minimum capacity from $$$u$$$ to centroid, and $$$bel_u$$$ be the subtree within which $$$u$$$ lies. Then, we just have to find out the following:

  • $$$bel_v\ne bel_u$$$.
  • $$$\min(mi_u,mi_v)\ge V$$$. ($$$V$$$ is the number of vehicles in the query)
  • $$$a_v=ans1$$$. ($$$ans1$$$ is the answer to the first question)
  • among those $$$v$$$, the maximum value of $$$\max(mx_u,mx_v)$$$.

By maintaining a segtree independently for each $$$a_v$$$, the whole task can be solved in $$$O((n+q) \log^2 (n+q))$$$. (without any observation)

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

Thanks for Editorial

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

Why is this giving TLE on 2nd test case whereas it runs just fine on other IDE

my solution

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

    violating the condition that 1<=aj<=n i also did same mistake though

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

      arre thanks a lot bhai..i have been struggling in this for a long time

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

        however it should give wrong output format rather then TLE if so i would have done d too

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

How to solve B? if m may not be less than n

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

    that,s mean the problem may not have solution if every node appeared at least one in B

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

      If it's given that Solution always exists for given testcases

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

Thanks for the Java implementation.

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

I really like the way D was made. It was easy but little trick at the same time. Thanks for this

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

Can someone help as to why am I getting a wrong answer on test 3 though I did same thing as the editorial?? Any help will be greatly appreciated. 132350668

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

In problem C, I can not understand the meaning of "This includes the cell itself, so all filled in cells are not exitable".

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

    I got WA cause' I misinterpreted this line, for a single column subgrid XXXX the output was supposed to be Yes but I was printing No.

    • »
      »
      »
      7 weeks ago, # ^ |
      Rev. 2   Vote: I like it -9 Vote: I do not like it

      I hope the authors would make the problem statement more easier to understand next time. For subgrid 2x2: [.X] [XX] I printed out YES, but the answer is NO

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

        How it is No? HuyHoang

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

          Because [.X][X.] also gives the same output. The bottom last cell is not exitable so they put an 'X' there. They say, "all filled in cells are not exitable" which does not imply "all non exitable cells are filled", so you could get a '.' there and still the resulting answer would be the same. There is clever wordplay here. If you still don't understand, watch this explanation by SecondThread for problem C (timestamped video) : here

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

The thicken words for B is really useful! :)

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

I think the proof of F doesn't seem so right....How can the necessity be proved like that?

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

Editorial Solution in c++ for 1586C? Anyone?

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

.

»
7 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

[solved]

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

The editorial of G is very long and I had to be patient enough to read it carefully. However, I didn't understand the sequence "Specifically, we can represent a valid set v as the set u of intervals that aren't implied to be in v by any other element of v" after reading it again, again, again, again, again and again. Though I asked many other people, I still found it hard to realize what it exactly mean... So is there any people who is good at English explain about it? Thanks. Sorry for my poor English:(

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

    It was described earlier that if you have segments $$$[a_i, b_i]$$$ and $$$[a_j, b_j]$$$ such that $$$a_i < a_j$$$ and $$$b_i < b_j$$$ then the presence of $$$[a_j, b_j]$$$ in set $$$v$$$ "implies" the presence of $$$[a_i, b_i]$$$ in set $$$v$$$.

    That's why, if $$$v$$$ has both $$$[a_i, b_i]$$$ and $$$[a_j, b_j]$$$ then you say that $$$u$$$ will contain only $$$[a_j, b_j]$$$. In other words, $$$u$$$ will contain only $$$[a_i, b_i]$$$ from $$$v$$$ that don't have any other $$$[a_j, b_j]$$$ in $$$v$$$ with $$$a_i < a_j$$$ and $$$b_i < b_j$$$.

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

      Oh, what a great explanation! Thanks for your help!

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

How to solve B if number of restrictions is not necessarily less than n?

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

can anyone say why test case 2 is not getting passed https://codeforces.com/contest/1586/submission/133734067

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

thank u so much

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

Problem B is really really amazing.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
We can also solve the problem D using the binary search. We can first try to find the value of pn i.e. the last element of the permutation. We can query the maximum diff such that p[n] + diff would exist twice in the array. For example lets say p[n] is 5 and n is 7 then diff would come out to be 3 because 5 + 3 will occur twice in the array (5 + 3 and 7 + 1) if we chose our array a to be [1, 1, 1, 1, 1, 1, diff] and 3 is greatest amongst all such diff values. Then pn can be easily computed as n - diff + 1 i.e. 5. It would require aroung log n queries to find the value of diff.

Then we can do the classic n - 1 queries to find the remaining n - 1 elements. 

Total queries: log n + n - 1.
»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Never mind, figured it out!

Regarding this one: 1586C — Omkar and Determination, can someone explain how this is not determinable?

10 10
XX.XX...XX
XXXXX...XX
.X.XX..XXX
XXX.X...XX
..........
..........
XXX....XXX
.XXX..XXXX
XXXXX.X.XX
XXXXX.XXXX
1
9 10


XX  NN
XX  NN
XX  NN
XX  NN
..  EE
..  EE
XX  NN
XX  NN
XX  NN
XX  NN
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

there is a solution for A using DP , it's something like knapsack and then print path that knapsack take it to get optimal solution https://codeforces.com/contest/1586/submission/137350208