codeprokeshav's blog

By codeprokeshav, history, 4 months ago, In English

Link : https://cses.fi/problemset/task/1670 is it a wise idea to think of recursion by making a function with 9 parameters there will be only two types: at the correct position, not correct position. Sometimes we will lock the numbers which will be at correct positions sometimes we will not and move it from correct to incorrect. so how to compute this problem

cses #game

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

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

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

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

There could be $$$9!$$$ such permutations. So you don't need to make a function with $$$9$$$ parameters, just storing the index of the permutations would be enough. And then just perform a straightforward dynamic programming.

Oh, you can also solve it using BFS.

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

    Sir I don't think 9! or dp approach will work because you can have base condition but what algorithm you will have below base condition. Sir can you please elaborate BFS approach Sir what I am feeling is that there is a small trick which can lead to a very simple and intuitive solution of this problem

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

      Yeah, you are right. Dp won't work.

      So just use BFS as spookywooky said. But you don't need to use string, instead, you can use the index of the permutations which will be faster as in that case you won't need to use map, but a simple array would suffice.

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

        right right we can just use max variable no need to use map it will decrease time complexity but how usage of index will reduce time

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

I did a brute force by bfs. The state of the board can be stored as a string, ie start with "123456789". Then there are 12 different swaps possible. So just store every possible state in a map with the number of swaps needed to reach that state. My code needs 0.9 sec to calculate all possible states, which gives AC.

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

    looks good doing it but Sir what I am feeling is that there is a small trick which can lead to a very simple and intuitive solution of this problem

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

    Your approach is fabulous. Can you share your implementation?

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

      Note that this is not very efficient. However, it looks like this:

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

        Thanks for this but I already wrote my own. However, I'm getting TLE

        How should I optimize?

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

          Easiest optimization is to BFS from both ends.

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

            Can you elaborate more?

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

              Essentially the answer isn't very large (I believe up to 16 for largest cases), so instead of doing a full BFS up to distance 16, only do a BFS up to distance 8 from both the starting grid and the final grid, and iterate over the "meetup grid".

              If we imagine BFS as a tree, the number of edges between depths increases roughly exponentially, so BFS'ing to only half of the depth is going to significantly reduce the amount of edges we check.

              Here's my submission that got 0.57 s on CSES. It's pretty basic with minimal optimization, so you can probably get it even faster.

              https://cses.fi/paste/5b823493d891d75d12d603/

              EDIT: Apparently there's a name for this: https://en.wikipedia.org/wiki/Bidirectional_search

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

                If for an arrangement that is (let's say 9 units from the start) and 7 units away from the goal. Ig the approach you mentioned wouldn't consider this case?

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

                  Yes, but that's ok, because there exists an arrangement that's distance 8 from the start and goal, so we'll use that instead.

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

                  So is there any certainty that this arrangement will definitely exist

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

                  EDIT: Image doesn't want to load so direct link: https://www.imageupload.net/image/bIGfa

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

          I made one which uses an array instead of hashmap for the dp values, which speed things up.

          https://cses.fi/paste/e40a153a2154cdee13d897/