xyz2606's blog

By xyz2606, 3 weeks ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +113
  • Vote: I do not like it

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

Auto comment: topic has been updated by xyz2606 (previous revision, new revision, compare).

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

constructiveforces

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

Can you also provide codes for the above editorials?

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

Problem D: If we use dynamic programming to compute the shortest path from u with length k how can we be sure that we will come back to u after k steps?

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

    find the shortest path upto k/2 moves and then come back along the same path...

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

      I did the same thing still get wa on test 4 :(

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

      solved

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

        what was the problem in the 4th test? Do you have a test case?

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

          Basically I was miscalculating the edge cost from going right to left and down to up. But somehow that buggy code passed the first 3 test cases and not the 4th one

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

          Did you find your bug ! I've implemented the solution explained in the editorial , still somehow getting WA on test 4 . 114377482

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            yes. I used m instead of n somewhere. I think you should just reread your code. Its not some special testcase apparently

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

    When k is even, we need to find the shortest path from starting position by performing only k/2 steps. And then traverse back along this path to get the required answer for k steps.

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

    The shortest path is not with length k, but with length i. If k/i is even, we can go this path from start to end and then from end to start all the time. So finally we can return u.

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

Today's most of the questions was based on matrix

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

Was able to solve 3 in a Div1+Div2 chinese round yay!

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

Can someone help me with this

Screenshot-20210423-234101

According to what i searched this error means that comparator is broken but i tried my best to include all possibilities in comparator can somebody please help me out in this

Language java Problem B Code https://codeforces.com/contest/1517/submission/114037412

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

    Hey, your comparator isn't defining the equality condition, when will two pairs be equal? Try changing line 157 from "return 1;" to "return 0;", it will work :)

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

    You are returning 1 for this case:

             if (a.row == b.row) {
              return 1;
             }
    

    Ideally it should return 0. What seems to be happening is, when a=b and b=c then a=c but due to above case, a=c is probably not holding true

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

I understand it intuitively but can we rigorously prove that the graph is bipartite?

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

    You can think about it like this. Consider the sum of the 2 coordinates. Every step you take changes the parity of this sum. To return to your starting point, your parity can only change an even number of times, but it changes exactly k times. Therefore, k must be even.

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

    All the nodes a[i][j] will be connected only to the nodes a[k][l] if i+j and k+l has opposite parity.

    So the given graph can be divided into two parts, one with the parity of sum of indices as even and other as odd.

    Hence the given graph is bipartite.

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

    Graph is always bipartite when it has no odd simple cycles. Let's take any cycle in this graph. Let's add some vertices to it which still form a cycle with the past ones. Their count will be 3..5..7 and so on. Besides, we must remove one edge, because it's needed to make the cycle simple.

    Picture (sorry for Paint):

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

    Because any n * m grid can be converted to a chess board.

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

Are there any ways to optimize dijkstra algo for problem D?

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

    Can we solve D using Dijkstra? I was getting wrong ans, not sure if I'm missing anything... https://codeforces.com/contest/1517/submission/114047555

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

      I've got ML5 with not optimized dijkstra

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

      Consider a cell for which the distance is .......say number 'X1' and total number of edges to reach it is 'L1'. Lets say there is another path, length 'X2' and number of edges 'L2' such that L2 < L1 but X1 < x2 (remember the graph is weighted) . The problem with Dijkstra's is that it will always prioritise the path with lesser overall distance.

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

In problem D, my solution was if I am at $$$(i, j)$$$ then I can go to $$$(i, j+1)$$$ using an edge of weight $$$W$$$ (let's say), and find the shortest path of length $$$k-2$$$ that starts at $$$(i, j+1)$$$ and also ends at $$$(i, j+1)$$$ and then finally return to $$$(i, j)$$$ using the same edge of weight $$$W$$$. So,

$$$dp[i][j][k] = 2*W + dp[i][j+1][k-2]$$$.

Do the same for all of the adjacent vertices, the minimum is the answer.

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

    But how is this always minimum? What if we go out through a particular edge but return through a different edge?

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

      It's easy to prove that it's always ideal to go half way in one direction and then just return along that path.

      Consider a node in the graph V. Let's say you have found a random path of length k that begins and ends at V, and this path enters and leaves V from two different edges.

      This would roughly look something like a loop. Now since the length of this path is even, we can divide it into two halves.

      There can be two cases —

      1. The costs of the two halves are unequal.

      2. The costs of the two halves are equal.

      If the costs of the two halves are unequal, we can reduce the total cost of the path by just going forwards and backwards on the cheaper half.

      If the costs are equal, going forwards and backwards on any half will not change the total cost.

      Thus, it is always ideal to go half way in one direction and then just return along that path.

      Hope this helps.

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

        Yeah that is correct....the reason this works is because k is an even number

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

        Thanks for this!

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

        That was a nice proof, thanks for writing it.

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

        I am solving this problem but got WA on test 5. I can't figure out what's wrong. Here's my commented code, if you get free time then kindly help.

        Submission

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

    I found your solution very helpful. thanks I_love_Kim_Dahyun :)

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

Problem E: How can the case $$$(C/P)CC...CPCPC...PCPP...P(C/P)$$$ be calculated in $$$O(N)$$$? For me the definition of the state looks like this:

  • We have the C/P at the beginning or the end. This is a constant factor.
  • Then we have the CCCCC-Part, the PCPCPC-Part and the PPPPP-Part. To check the sum-condition for all cases we need to iterate over all 3 lengths. the 3rd lengths follows from the 1st and second since their sum is constant.

But that sounds like iterating two lengths and it amounts to $$$O(N^2)$$$? What is the observation that I am missing to make it $$$O(N)$$$?

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

    You iterate over length of $$$CC...C$$$ and the minimum acceptable length of $$$PP...P$$$ can be found using binary search or two pointers, because all the numbers in the array are positive, and function $$$\sum_P - \sum_C$$$ is monotonous.

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

    If you have some kind of alternating prefix sum array to quickly calculate the sum of P if some range is PCPCPC(let's call it $$$pr$$$ and if the range is between the $$$i+1$$$-th and the $$$j$$$-th element then the sum is $$$pr_j-pr_i$$$), when fixing the point where you switch from PCPCPC to PPPPPP(let's call it $$$j$$$), if the point where you switch from CCCCCC to PCPCPC is $$$i$$$, then the condition is $$$pr_j-pr_i+sum(j+1..n) \geq \left \lfloor{\frac{sum(array)}{2}+1}\right \rfloor$$$. You can find the maximum $$$i$$$ for which that condition holds using either binary search or 2 pointers.

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

      Where is $$$\left \lfloor{\frac{n}{2}+1}\right \rfloor$$$ from? I would assume there had to be $$$sum(1 ... i-1)$$$ instead? Maybe I misunderstand your formula.

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

    My solution is similar to dorijanlendvaj's for the part with alternate partial sum, but I used a data structure (e.g. fenwick tree, segment tree, treap) to maintain the number of i satisfying the inequality. For stupid people like me who can't spot the obvious property of monotonicity, it is a lot more intuitive. The code can also be pretty short if you are familiar with data structures, check my code here: 114032392.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please explain how we concluded that:

      "There can't be two i's such that ci−c(i−1)>2, or pi−p(i−1) won't be non-increasing. And there can't be two i's such that pi−pi−1>2, or ci−c(i−1) won't be non-decreasing. So for any 2≤i<m, ci−ci−1≤2, and for any 2≤i<k, pi−pi−1≤2."

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah, so ci and pi is indexes of array "a", not the elements of "a". Now I got it.

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

Can you provide a Chinese-version editorial? Maybe that way people can understand the whole editorial better.

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

dpforces

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

In D, is not not two dimension more complecated to think about the graph beeing bepartite, and hence does not allow paths of a given parity?

Instead, foreach step we do, we must do a step in the oposite direction. So the number is even.

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

please provide cpde also

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

Problem C is a simple dfs from each cell on the diagonal. For each cell first visit left cell , then down and then right. During this keep reducing the count and once it becomes 0 , return. This will pass all tests.

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

solved

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

In problem C could someone help in justifying the second construction ? How to prove that it will always work ?

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

    My approach is also similar to editorial.

    Consider a rubber attached to the point i,i. We want to stretch the rubber p[i] times. So the optimal choice is to stretch the rubber in the following order

    1-Strecth the rubber up

    2-Strecth the rubber left

    3-Strecth the rubber down

    4-Strecth the rubber right

    This ordering will always ensure that we don't have any empty space left. See submission for more details:114016611

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

Video Editorial for problem C: https://youtu.be/RVE8Xprwsfo

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

Hey guys, i found this very strange submission to problem D of this contest (114038234 belonging to the user pxsitivevxbess) and was wondering if anybody could explain to me the logic behind the excessive usage of "ashwet++".

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

Amazing editorial for problem G, the amount of details is simply astonishing

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

    The problem has two types of forbidden pattern: the "square" and the "parallelogram". the square corresponds to 1-0-3-2-1 while parallelogram to 1-0-2-3-1. On the surface, it seems you have to add two kind of edges between rows: 0-3 1-2 (vertical ones) and 0->2 1->3 (diagonal ones)

    But the key observation is that you don't need to, you only need to add edges 0-3 and 1-2. The reason is because to check for parallelogram, you can actually just use the same check: whether a path 0-1-2-3 exists. If such a path exist, then it must either be a square or a parallelogram, e.g.:

    ...10...01...
    ...23...32...
    

    for squares and

    ...10...01...
    ..32.....23..
    

    for parallelograms

    Therefore, we consider the acyclic graph where all "0" nodes have edge to "1" node, all "1" node to "2" nodes, and all "2" nodes to "3" nodes. in this acyclic graph, we want to cut fewest weight nodes so that no path exists from "0" to "3". This can now be done easily using min cut.

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

      What about a parallelogram that looks like

      ...10...

      .....32..

      It won't be covered by a 0-1-2-3 path, only a 1-0-3-2 path, so how do we take care of these cases?

      Ps. your second square case should be

      01

      32

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

        These kind of parallelograms are not meant to be forbidden as important tents are represented by "1" and this parallelogram is not breaking the given condition ( $$$|x_2 - x_1| = 2$$$ but it should be $$$|x_2-x_1| \le 1$$$

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

why in d you need k/2 only.suppose we go to next edge and its cost is 1 but after that costs are 10^6 so why shouldn't i go back and forth only to complete k steps rather than include 10^6 in my ans?

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

    It is not possible.

    Supposition: The optimal cost to travel k/2 steps is C.

    If you move k/2 steps with cost C and if there exist a returning path with length k/2 that has C' < C.Then you can move in the later path to get a cost of C'.But this is not possible because of the supposition.

    Hence we can always travel k/2 steps and return with the same path.

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

      i am asking if suppose i have next edge cost=1 and all edges after wards have cost of 10^6 then why should i go exact k/2 steps in forward direction why not jhust go b/w current vertic and next vertex whose edge has cost 1 and complete k steps in this manner ? why would u inlcude 10^6 in your ans?

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

        You misunderstood my statement.

        Suppose you are initially at $$$A$$$ and after completing $$$k/2$$$ steps you are at position $$$C$$$. So in order to get the minimum answer you must retrace the same path that you have to taken to reach to $$$C$$$ to $$$A$$$.

        That's why we only have to check $$$k/2$$$ steps.

        And steps doesn't mean you have to always move forward. You can also move 1 step forward then backward then forward and so on until all $$$k/2$$$ steps are exhausted.

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

implementForces :)

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

can anyone help me understand where my submission is going wrong. submission link

Error is : wrong answer the sequence is not identical (test case 1) TIA.

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

In Problem D, multi-source Dijkstra with a priority queue gets TLE: 114052809.
But if the priority queue is replaced by a normal queue, it gets AC in 405 ms: 114052881.

I think the solution with the queue should get TLE too. But I couldn't come up with an appropriate case. Can anyone try to uphack the solution? Or am I missing something?

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

    For Dijkstra's, the exit condition should be -

    new_code

    instead of

    old_code

    check out my submission, I just modified this line and it passses — https://codeforces.com/contest/1517/submission/114073092

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

      Actually, both are performing the same purpose here.

      dist[u.r][u.c][u.lv] holds the minimum possible cost for [u.r][u.c][u.lv] till now. So, obviously dist[u.r][u.c][u.lv] != u.w means the value of u.w is greater than dist[u.r][u.c][u.lv].

      Edit: Your submission is passing because of the compiler. I've submitted with != operator using "GNU C++17" compiler and got AC in 1856 ms: 114108137.

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

    By the way, can you explain your logic for Multi-Source Dijkstra's? Mostly why this holds true in this problem?

    Also, the queue solution should be incorrect, because Dijkstra's requires a priority queue for the same?

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

      Logic:
      For a cell (r, c), we need to find the minimum cost after h steps if we start from the cell (r, c). As the graph is undirected, it is equivalent to reach the cell (r, c) from an arbitrary cell after h steps. So, we can do it by taking every cell as the source and calculate the dist[r][c][h] for each cell. It is normal Dijkstra. The rest calculation part for the minimum boredness is quite easy.

      Queue solution:
      Dijkstra needs a priority queue (min-heap) just to reduce the complexity. Taking queue won't make your solution incorrect. In normal graphs, it will increase your complexity.

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

        So you are saying that -

        1. We can do Dijkstra's using queue OR
        2. Required implementation in this problem doesn't require a priority queue
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
          Rev. 2   Vote: I like it +3 Vote: I do not like it
          1. Yes, we can do Dijkstra using a queue. But the complexity will be bigger. In the worst case, it will be $$$O(VE)$$$.

          2. I'm not sure actually. But most probably, yes.
            Firstly, the way I've implemented Dijkstra, using queue in it almost makes it SPFA.
            Secondly, For a cell $$$(r,c)$$$, you need to go at most $$$10$$$ steps. So, the number of cells needed to traverse from a single source reduces a lot. It is quite a large restriction. With this restriction, there's a chance that making the worst case for $$$SPFA$$$ is impossible.

          Edit: I'm saying both.

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

            Thanks for the descriptive response :) I didn't know the queue solution looked like SPFA. That's nice observation.

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

Can you explain the $$$n^2log(n)$$$ solution for problem F? Thanks.

  • »
    »
    10 days ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    I haven't yet tried, but I guess you can optimize the dp with some heavy-light decomposition trick. I guess, since the number of dp states at node v is of O(depth_of_subree_rooted_at_v), when dealing with node v, you can inherit dp states from the heavy child (child with the maximum subtree depth) and iterate the rest children. That way, you end up with a O(nlogn) dp per radius, then O(n^2 log n) for all radius.

»
2 weeks ago, # |
  Vote: I like it -72 Vote: I do not like it

hey anyone who can find whats wring in my code of problem B

include<bits/stdc++.h>

using namespace std;

define ll long long int

define el "\n"

define mod 1000000000

int main() { ll t; cin>>t; while(t--){ ll n,m; cin>>n>>m; ll a[n][m]; ll b[n][m]; ll temp=0; vector<pair<ll,ll> > v(m);

for(ll i=0;i<n;i++){
    for(ll j=0;j<m;j++){
        cin>>a[i][j];
        b[i][j]=a[i][j];
    }
  }
  //v[0].first=3;

while(temp!=m){
        ll c=mod;
   for(ll i=0;i<n;i++){
    for(ll j=0;j<m;j++){

        if(a[i][j]<=c){

            c=a[i][j];

           v[temp].first=i;

        v[temp].second=j;
        }

    }
  }
  a[v[temp].first][v[temp].second]=mod;

temp++; }

for(ll j=0;j<m;j++){
   swap(b[v[j].first][v[j].second],b[v[j].first][j]);

}

// cout<<el; for(ll i=0;i<n;i++){ for(ll j=0;j<m;j++){ cout<<b[i][j]<<" "; } cout<<el;}

} return 0; }

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

    Please use pastebin or use spoiler to share your code, directly pasting the code pollutes the blog :)

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

Help me out with A folks I don't know how to find sum of its digits in decimal representation.

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

    Well, you can prove to yourself that the last digit of "n" is always (n%10) = n modulo 10 (the rest when you devide n by 10. Now, you use a while and at every step you add n%10(last digit) and then devide n by 10 (that eliminates the last digit). You have to do this until n is equal to 0. When that happens you stop the iterration and that's the sum. Hope it was not a joke and I actually helped. :))

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

I haven't understood the editorial of problem E, can anyone explain it in detail?

  • »
    »
    12 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    C and P are two sets of all indexes of "a" (together — "n" elements). Indexes of C is growing wider left-to-right, and P — right-to-left. If for some ci-c(i-1) > 2 than there should be two P's in a row between them. And this means there can't be no more P's to the left from them, and to the right(max — 1), because pi-p(i-1) become 1, and to jump over C it need to become 2 — this breaks monotonic rule. And so on.

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

Can someone please help me out with What am I missing in B problem? My Solution

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

.

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

Can someone explain Problem B?

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

    Check this image out —

    click the image

    Basically, get the top m minimum numbers from the all the entries, and position them stategically such that the order of min elements is followed.

    As you can see the image, we want to permute each row, such that the min numbers(in red) are positioned one after the other.

    You can check my submission for more details — https://codeforces.com/contest/1517/submission/114011935

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

      Hi, thanks for the reply. I understood the basic idea. Could you tell me what is wrong with my submission? https://codeforces.com/contest/1517/submission/114070887

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

        You are modifying the modified elements in each row, you need to skip those positions, which have been modified.

        Like you might modify (0, 0) and then later you might check for an element(0, i) which matches at (0, 0), so might change the value.

        Keep a set of modified elements, which would want to skip, that might help

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

          .

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          hey, thanks for the visual explanation,

          in my approach, I used a set to store the smallest m elements and a dictionary to store all the indices pair.

          I set col=0 and iterate through all n path lists, then iterate through each path list (i<n and j<m) so paths[i][j] would be the first element,

          I check if paths[i][j] is present in the set and also (i,j) is not present in my dictionary, and also if col<m, if all these conditions hold true then i swap paths[i][j] with paths[i][col] ,

          i then add(i,col) to my dictionary and then increment col by 1.

          This algorithm seems like its correct but Im getting WA for TC 2 , can you tell me whats wrong in my algo

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

I dont really understand problem B.Can someone help me? (if u can give sample code its better)

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

Can anyone kindly help me to understand the Problem B? I didn't get the editorial...

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

    Hey, so try thinking it this way. In problem B, you're given a matrix, where every ith row represents the paths a runner can choose, to go from ith checkpoint to (i+1)th checkpoint. Now what does the question ask? The question asks you to assign paths to every runner, such that the sum of the minimum paths of each runner is also minimum. And, the number of runners = number of paths for each checkpoint = number of columns = m (as in the question). Now for every element in the matrix, you can't change its row cause that would mean changing a checkpoint and that's not permitted. But you can change its column, and at the end output a matrix where every column represents all the paths taken by a single runner. Now all you have to do is find the minimum of each column and take its sum. This sum should be minimal. When can it be so? When will the sum of m elements be minimum when you have m*n elements to choose from? When the minumums of each column (and there being m columns) are made by the m minimum paths of all the m*n paths given to you. So try finding the m smallest paths from all m*n paths and then make sure that these paths are placed in their respective rows and different columns, so that each of these is the smallest in its column. Then the other places in the solution matrix can be filled in any order, but make sure that you don't change the row of any element. Also be careful that you don't overlap the paths in a row. The rows of the output matrix should be permutations of the rows of the input matrix.

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

    nice Explanation

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

    Problem B videoEditorial (explained in detail) link : https://www.youtube.com/watch?v=mY8tcan90sQ

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

Can anyone help can't figure out what's wrong with my problem D solution.

WA on Test 5 114051343

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

can anyone explain number 2? I dont get the editorial since I'm new here ;-;

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

If problem "C" were in position of problem "B" then it could have been submitted by more participant during contest time. The implementation of "B" was quite lengthy and tricky than "C".

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

Problem B videoEditorial (explained in detail) link : https://www.youtube.com/watch?v=mY8tcan90sQ

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

1517B - Morning Jogging

Status : AC

My Solution Is Find The Smallest M Elements And Put Each Item In Different Column

My Submition : 114096708

Note : Must Be To Update Information When Swap 2 Elements

Because Is Some Cases Are Swap 2 Element Are Existing in Array With M Element And You will get substitutions for wrong items Not Existing in Smallest M Elements

»
2 weeks ago, # |
Rev. 3   Vote: I like it -18 Vote: I do not like it

I really liked the idea for the problem C & D.

»
2 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Problem C videoEditorial link : https://www.youtube.com/watch?v=w4XUoQScG90

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

In prob-D, Can anybody tell the number of states we will have while calculating the shortest path of length K/2 from some vertex u? I think its around K^2 because starting from vertex 'u' ideally, we will traverse in square of K*K size

Update: Got the answer

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

I did try to implement what you have said in B.But somehow its not passing all test cases. Can someone please tell what is wrong with mycode. https://codeforces.com/contest/1517/submission/114183214

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

HI! can someone explain Problem D. I have solved the problem using Dp, recursion during the contest. I wanted to understand the iterative solution.

thanks a lot in advance!.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

please give the codes as well

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial for problem H says: 'We will explain the precision issues later', but that part seems to be missing. Can somebody please add that part? In my attempts to solve the problem, I struggled with precious issues for quite some time, and I added several hacks until I finally got AC (114778549).