chokudai's blog

By chokudai, history, 8 days ago, In English

We will hold AtCoder Beginner Contest 184.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +65
  • Vote: I do not like it

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

Solving D is the main target!!!!

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

good luck

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

Hope I can get at least 4 problems!

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

Good luck!

I hope I can solve E.(I'm too vegetable.)

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

..

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

In problem C, the third move in example 3 from (-247,253) to the destination point does not satisfy any of the three conditions! Does the problem setter have any explanation?

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

    -247-253=998244353-998244853

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

      Wow, I overlooked the difference between the two large numbers. Thanks for the explanation.

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

so tough :(

»
8 days ago, # |
  Vote: I like it -14 Vote: I do not like it

this is my first time, I am getting AC for the given inputs, but when I submit it gives WA — wtf.

»
8 days ago, # |
  Vote: I like it +37 Vote: I do not like it

C is not good for Problem C in ABC and I don't like it :(

But other problems are great and interesting.

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

    sorry

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

      I think the definition of everything is quite clear. Which part do you think is confusing?

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

        What is '.' doing in D?

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

          Where do you see that in problem D?

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

            Sorry, I meant 'E'

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

              It is just a character.

              A character a i , j describes the square at the i -th row from the top and j -th column from the left. Here, a i , j is one of the following: S , G , . , # , a, ..., and z.

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

Problem C isn't a ABC style

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

how to sove expected value questions

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

Why the answer to the last example in problem D is 91.83..?

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

Time limit for problem E(in Java) is a bit too strict.I have applied the fastest IO method with silly optimizations still it misses out on 4 cases.

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

    Or your solution's time complexity is too high XD

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

    I submitted in JAVA too and got accepted in 1491 ms, so definitely time limits aren't strict (3 seconds).

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
8 days ago, # |
  Vote: I like it +43 Vote: I do not like it

Aren't E and F classical problems?

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

    E looks like BFS problem

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

    how to solve f any hints ?

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

    I'd like to second that. E and F are way too standard problems if you have appreciable experience.

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

      Well, that is abc contest. The maintainers do not write editorials because the problems are so standard that its not worth it. You could also argue that A is to simple.

      Nobody said the problems in the abc contest were particularly original, why complain about it?

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

How to get rid of TLE in E(in Java)??

I have used fastest IO still it fails

My submisssion:-https://atcoder.jp/contests/abc184/submissions/18340875

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

Looks like I finally need to learn expected value

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

How do you solve D ?

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

    We can create a dp[a][b][c]==prob that that state happens. Then add up the propabilities.

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it -13 Vote: I do not like it
      Then add up the propabilities

      I think we need to add "probability multiplied by number of steps to reach a,b,c". Whenever you are helping someone , elaborate completely or don't do at all. Many a times it just confuses people more.

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

        Fuck you, idiot.

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

          Sure . I am not bad-mouth as you are. But then how am i wrong ? You have written "propabilities" , what the heck is "propabilities" ? Also if "Then add up the propabilities" was true then wouldn't be answer of every input be 1. Question is asking expectation and not sum of probabilities .

          People who have downvoted , please downvote , but again these are people who confuse beginners more in name of helping . I was once beginner and i understand that.

          spookywooky you keep complaining about contest problems and editorials whereas you yourself cannot explain properly .

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

            I love spookywooky's explanations , they're not deliberately explicit enough to become spoonfeeding which is great if you still don't want to miss out on the satisfaction you get after solving the problem yourself and this doesn't mean someone doesn't know how to get the point across. Again it's a personal opinion. Also I don't know many users here who document there thoughts in their contest submissions like spookywooky does which helps a lot sometimes.

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

That was again nice beginner contest. C was a bit clumsy to implement.

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

    how to solve C?

    • »
      »
      »
      8 days ago, # ^ |
      Rev. 7   Vote: I like it +5 Vote: I do not like it
      Observation
      What to do with this
      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        proof/intuition for 3rd point?

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

          Chess coloring.. each block with same color is reachable by 2 diagonal moves (i suggest you to draw out the same)

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

        Can you link your submission. It would be helpful.

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

        Your solution is wrong in after_contest case.

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

        You missed out on that you can reach a point in two moves if abs(a-c)+abs(b-d)<=6 as you can perform the third operation twice.

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

      I did some research on this problem. I will try to explain what I understood. Here is my code. Ok.

      step 0: When source and detination are same

      step 1: It will require 1 step to reach destination when it satisfies the 3 given condiitons.

      step 2: when

      -AA(it will take 1 step because it seems like it lies on the same diagonal)

      -AB(it is the case when 2 diagonals meet. so (a+b)%2==(c+d)%2. Correct me if its wrong)

      -AC(when 1st and 3rd conditions satisfy. Then check for(abs((a+b)-(c+d))<=3))

      -BB(it will take 1 step because it seems like it lies on the same diagonal)

      -BC(when 1st and 3rd conditions satisfy. Then check for(abs((a-b)-(c-d))<=3))

      -CC(when 3rd condition satisfy 2 times so instead of checking for 3 check for 6(abs(a-c)+abs(b-d))<=6)

      step 3: other than 0,1,2 it is said to be 3

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

        When 1st and 3rd conditions satisfy why should we check for abs((a+b)-(c+d))<=3 wouldn't it be always zero. Could you please explain

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

          yeah.. what It mean is it require 1 step to travel along the diagonal and 3rd condition is for checking if it lies with in squares. so A+C.

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

            Could you please tell the intuition behind checking the condition abs((a+b)-(c+d))<=3 if 1st and 3rd conditions satisfy. Thanks in advance.

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

              ok what i understood that I will exlpain. Its all my imagination. See in this 3rd condition abs(a-c)+abs(b-d)<=3. I felt like abs(a-c) is for rows and abs(b-d) is for columns. see c+d is the diagonal for destination point. so if the difference between these 2 diagonals are less than or equal to 3 then it means it lies within the squares of the destination only right!!. Even the logic is same for BC also. Hope you understood.

»
8 days ago, # |
  Vote: I like it +24 Vote: I do not like it

Lol C was more hard than E to me.

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

For F, how to know backtracking + meet in the middle has good enough time complexity?

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

    We can create the table of size 2^20 for first 20 items. Then do the same for the other 20 items, and combine each entry of the first table with the optimal one from the other in O(logn). ie binary search for the value.

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

      Thats exactly what I did but still got WA on 8 cases. Can you help me debug?

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

    The constraint on N is small, i.e, 40. So if we divide it in 20 and 20 and then compute subset sums for the right half and left half using recursion, it will have a time complexity of 2^20, which is doable.

»
8 days ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve C and D?

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

    C: Observe that all fields are reachable with 3 moves. This is, because all fields (chess coloring) with same color are reachable with two moves.

    So, check if dist==0. Then check if dist==1 by implementing the rules as given in statement.

    Then check if dist==2, that is same field color or manhattan dist<=6. Or if destination point+3 fields is on one of the diagonals.

    Else dist==3

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

      I was still wondering at the end of the contest why it is not reachable in two moves, yeah it is because of chess coloring :/

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

      How chess coloring is happening in the board ? There can be adjacent cells with same color ? Please explain what you really mean .And what is "dist" here ? You should define "dist" first.

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

        chess coloring is that cells sharing a border have different colors, like you know it from chess board.

        dist is short for distance, the result we are searching for. sorry for that ;)

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

          You are more confusing now .

          chess coloring is that cell sharing a border have different colors

          How does that answer my question : How chess coloring is happening in the board ?

          dist is short for distance, the result we are searching for

          But according to your explanation its number of moves.

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

            Just dont start to cry, I would feel bad about it.

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

              It was genuine doubt tbh . Don't know why you are replying in weird way.

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

      Nice idea in problem C. Can you explain me, why you use abs(a-c)+abs(b-d)<=6

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

        Well, its two steps. In one step we can go manhattan distance 3, so in two steps manhattan distance 6.

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

Why is F always wrong??I can't find something wrong in my code.

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

How to solve D??

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

    Dynamic Programming
    My submission should be self-explanatory
    Submission

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

    I thought about the reverse process, let's build state a, b, c from all possible final states. That way I can add 1 directly while computing expectation from successive states, probabilities of transition remain the same, but the expected value of answer is now expected value of states a, b, c. Transitions are namely (a+1,b,c), (a, b+1,c) and (a, b, c+1) multiplied with respected probabilities ,of course if its a valid state. Submission Link

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

I think there is a mistake in problem E... I wrote a simple BFS that should never visit a node more than once (and never try to visit a node more than 5 times due to teleport — using the fact that the closest 'a' character to the start should be the one that uses all of the potential 'a' teleports); so my algorithm should be O(m) where m is the number of edges in the graph, but it does not work because of TLE.

I wrote my code in C++

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

this is what happens when people complain about easy tasks in Beginner Contests.

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

How many of you missed C with WA on only a single test case? XD

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

D was the most toughest for me...could anyone share approach?

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

Only solved A, B! :')

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

My C solution passed all test cases except one. Anyone has any ideas on what it would be?

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

I m not able figure out why my code is giving WA for 2 testcases in problem C. Can someone tell me... Link to My Submission..

»
8 days ago, # |
  Vote: I like it -15 Vote: I do not like it

I think ABCs aren't good anymore :(

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

    I think you ain't working hard anymore :(

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

      Ok I solved up to E. I didn't solve F because I don't know meet in the middle. This contest was just about knowing or don't knowing algorithm. If you know you will solve, If you don't know so you can't solve. A and B were as always. C wasn't good at all as others say. D was just about knowing expected value. E wasn't anything more than one BFS. F was meet in the middle.

      For all of those if you know the technique you can solve else you can't. Is this contest good?

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

For problem E: using teleporters as edges got me TLE submission but when I added a simple check if the current teleporter letter was used before it passed submission. Can someone explain why is this happening, because I thought since the distance should be less it will not add it to the queue anyway. Is it just the loop that's causing me a TLE?

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

    No, the idea of keeping a visited array is a must to avoid tle, because lets say you are traversing the point with 'a' then if this is the first 'a' you have encountered then all other 'a' will be marked with their best distance (thats how bfs works) and hence when you next encounter a 'a', you dont need to again update the weights of other 'a' because they are already marked to their best.

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

Can someone explain solution for C.

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

    First check if you can reach the square in just 1 move by using all the conditions specified in the question. Next, see if (a+b)%2==(c+d)%2. If yes, you can reach c, d in 2 moves (if 1 move was possible you'd have already returned). Next, iterate on all the squares that can be reached in 1 move (I used 2 nested for loops, each going from [-3, 3]) and use the same condition you used to check if (c, d) is reachable in 1 move. If it is, print 2, as you spent 1 move in shifting around, else print 3.

    My submission https://atcoder.jp/contests/abc184/submissions/18338400

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

Can anyone please tell me why a simple BFS in E is giving me TLE in 3 cases. I am unable to think of any edge cases in my implementation.
My Solution.

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

    imagine a grid with full of 'a', this code would have the complexity of n^2 * m ^ 2 then

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

      Thanks, got AC now. I had implemented that initially but commented it later.. :facepalm:

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

    My first submission also got time limit exceeded so I applied this logic , look once visiting a particular character 'a' in minimum number of moves say 'd' then mark all the unvisited positions that has character 'a' as minimum distance = d+1. Now notice that this character 'a'(assumed here) is no longer use so u can erase it from your adjacency list. Mine such approach passed all test cases. Hope it helps and provide u the sufficient idea. My Solution Link

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

Can someone explain D like I am an idiot please. Thanks.

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

    https://sapphireengine.com/@/2ptnop You can refer this to understand

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

    Let $$$p[i][j][k]$$$ be the probability that we currently have $$$i$$$ gold coins, $$$j$$$ silver coins, and $$$k$$$ bronze coins. Initially, $$$p[a][b][c] = 1$$$ and otherwise $$$p[i][j][k] = 0$$$. We update

    $$$p[i+1][j][k] += \frac{i}{i+j+k}\cdot p[i][j][k],$$$
    $$$p[i][j+1][k] += \frac{j}{i+j+k}\cdot p[i][j][k],$$$
    $$$p[i][j][k+1] += \frac{k}{i+j+k}\cdot p[i][j][k].$$$

    For every such $p[i][j][k]$ where exactly one of $$$i, j, k$$$ is equal to 100, we simply update our answer by

    $$$((i+j+k) - (a+b+c))\cdot p[i][j][k],$$$

    where $$$(i+j+k)-(a+b+c)$$$ represents the number of turns needed to reach state $$$(i, j, k)$$$.

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

      I think your solution is wrong,

      I think the probability at i,j,k would be $$$p[i][j][k]= \frac{i-1}{i+j+k-1} * p[i-1][j][k] + \frac{j-1}{i+j+k-1} * p[i][j-1][k] + \frac{k-1}{i+j+k-1} * p[i][j][k-1]$$$

      Am I missing something???

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

        You're right, I meant to write $$$+=$$$ instead of an $$$=$$$ for each equation. As we go through the dp the updates will accumulate into the equation you wrote.

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

          Does this definition work for second example in the given for the question? I don't think it does, I raised the concern regarding this during contest but they said everything is correct... that's I was trying to think some other solution during the contest.

          Edit: It works, I was making to some horrible mistakes while calculation

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

      Thank you so much, I tried a similar thing but failed so I was really confused. Thanks for the clear explanation

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

where are the solutions?

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

[Problem E] This is the first time I successfully hardcoded a solution on AtCoder during the contest. I thought the test cases on AtCoder are invincible too.

I guessed random_32.txt to consist of all dots except the start and goal and hardcoded for that accordingly.

Before hardcode - https://atcoder.jp/contests/abc184/submissions/18340539 (I still do not know why this TLE)

After hardcode - https://atcoder.jp/contests/abc184/submissions/18341941 (This should break and TLE if I add a hex anywhere)

Readable version of the code - https://atcoder.jp/contests/abc184/submissions/18346808

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

Give me one corner case for this solution of problem C.

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

Can anyone please tell their approach for problem F. Using knapsack approach gives TLE

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

    Try to think about meet in middle, calculate all possible sum of weights of 2 equal parts of the input array and think of obtaining answer as combination of each value from first set with best value from the other. Ofcourse best answer might just come from one part only, so take care of that separately. Time Complexity will be O(2^(N/2)) with 2 pointers or with a factor of N if you're lazy enough :p

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

      Just curious would this approach be intuitive if we don't know about meet in the middle algorithm xD Thanks for your approach by the way.

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

      Yeah. But two pointer will work only if I generate the sum in sorted order. Can you tell how to generate subset sum in $$$sorted$$$ order.

      Edit: — Also how factor of N will not come? I have to go through the n/2 bits position right? so complexity will be $$$O(N2^{N/2})$$$. If I am wrong please point it out.

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

        Oops missed the sorting part, yeah its N * 2^(N/2).I meant factor of N over 2^(N/2) making it resulting complexity.

»
8 days ago, # |
  Vote: I like it +27 Vote: I do not like it

C was tougher than F for me

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

Well it looked like problem setters forgot to check availability of solutions on internet.

The F problem was the most basic example of Meet-In-The-Middle algorithm whose entire code is available here

P.S. — I figured this out after contest. Thus, getting 1 WA on my greedy submission.(LoL)

Other problems were cool. Thanks for such an amazing problem-set.

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

My video editorial. Uploading took a long time.

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

https://atcoder.jp/contests/abc184/submissions/18351753 please someone suggest me a way to get over TLE will be great help! problem E! c++ code

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

    // tele[c].clear();

    The above line is correct, uncomment it, and place it after the loop. Each portal letter need to be traversed only once.

    Otherwise consider N=2000 grid and all cells marked with 'a', it will result in O(n^4) runtime.

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

    My first submission also got time limit exceeded so I applied this logic , look once visiting a particular character 'a' in minimum number of moves say 'd' then mark all the unvisited positions that has character 'a' as minimum distance = d+1. Now notice that this character 'a'(assumed here) is no longer use so u can erase it from your adjacency list. Mine such approach passed all test cases. Hope it helps and provide u the sufficient idea.My Solution Link

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

why we don't get editorial after the contest what if some one not able to solve the problem where should we discuss.

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

Pre-req for solving E and F ??

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

Can anyone can notice me what is wrong point in my code of E

please help me. its python and i think i understand idea of this problem

https://atcoder.jp/contests/abc184/submissions/18354503

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

can anyone pls tell me why my code for problem E is getting RUNTIME ERROR? here is my submission

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

[Problem C] It seems that they added a test case of something like this, that made my wrong code fail after the contest

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

    Yes,you are right,Thanks a lot!

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

in problem C I am getting 3 WA. I tried but I am unable to find the mistake. The test cases are also not uploaded yet. I am getting WA at random_09.txt,random_10.txt,random_11.txt. Can anyone help me with this

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

Can anyone please help with my code from problem C. I do not get why it is failing two test cases. Link to submission: https://atcoder.jp/contests/abc184/submissions/18334803

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

Why I m not getting any output?? Submission:https://atcoder.jp/contests/abc184/submissions/18364662

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

Help! I got WA for the Task E and only because one wrong answer of the case "random_23.txt". I have no idea now Submission #18364982

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

Can someone tell me why my code, gives a TLE for the problem E.

LINK : https://atcoder.jp/contests/abc184/submissions/18365487

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

For Problem C: Please give me a condition where need three moves. I can't understand why I can't go to any destination in two moves.

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

    In the sample input, there is one that require 3 moves

    2 3
    998244353 998244853
    

    If you want a simpler example

    0 0
    0 7
    
»
7 days ago, # |
  Vote: I like it -8 Vote: I do not like it

Loda lassan contest bencho problem C to AC hi nahi ho rahi hai.

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

F is way too standard and even available on GeekesforGeeks. I understand that ABC are for Educational purpose but I don't think it's a good idea to give problems in ABC that are just a click away from googling.

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

Can anyone tell me when the Editorial will be available?

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

why is there no editorial ? It's been 4 days