iLoveIOI's blog

By iLoveIOI, history, 7 weeks ago, In English

I couldn't find a discussion blog for this contest so here's one.

Does anyone know how to solve Ex?

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

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

For problem D, my solution with Binary Search + BFS works fine except for 01_random_03.txt. Any hint ?

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

    Did you binary search till 4e9 becauese I was facing same verdict till i realized cost could be 4e9.

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

      My solution also fails on the same test case. Is there anyone who could look into my code.

      code

      I have used #define int long long

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

        Overflow. P can be 10^9 10^11 * 10^9 = 10^20 which is too big even for long long.

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

        maybe you should use ceil div.(but not ceil(double) function, it'll lose at precision, use (A+B-1)/B $$$= \lceil\dfrac AB\rceil$$$.)

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

      explain your solution

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

    I get AC for binary search (over $$$S$$$) + bfs. Although I had to write it in C++ to make it pass.

    I searched over 0 to $$$\max(\text{dist}(i,j))$$$.

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

    With 4e9 it works fine. thanks.

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

Submission In problem G why picking the longest transition (by prefix function) works?

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

    Greedily removing the longest suffix of T that is a prefix of S seems to work as well.

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

      Yeah did so after the contest and it passed but I am unable to prove it why does it work.

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

        Because ans[i]<=ans[j] for i<=j because you can always construct a solution for index i from the constructive words of solution j by either deleting some characters of the last word (giving the same ans) or deleting some words then some characters (giving smaller ans).

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

D was a nice variation of Floyd Warshall algorithm

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

    BFS is a nice variation of Floyd Warshall?

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

      You can also solve it using a slight modification of floyd warshall by defining

      $$$ w[i][j] = \frac{|x_i-x_j|+|y_i-y_j|}{p[i]}$$$

      and changing + operation with max

      code

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

    I used this idea as well, but I think that binary search solution is also very nice.

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

I have failed on F because of a little mistake in my BFS :)

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

Problem C? Can anyone mention the approach? Thanks!

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

    We can multiply all w[i]=w[i]*2, then check all w[i]+1 and w[i]-1 to be the possible best answer.

    Each check can be done in O(logn) by sorting childs and adulds separate, then binary search the number of correct guessed ones for fixed x.

    Edit: Or use prefix sums. Atfer sorting w[], we can split w[] at any position, then the correct guessed number is the number of childs left of the split position plus the number of adults right of the split position.

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

    Keep track of score0 and score1. Use map to iterate the weights and move the border line of guessing 0 vs guessing 1 from left to right. I submitted a simplified version of the code at: https://atcoder.jp/contests/abc257/submissions/32757902

    I was unlucky to only solved it one minute after the contest ended.

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

    check for all w[i], then also check for smallest weight-1 and largest weight+1(Solution)

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

    just sort the children array and parent array and apply binary to get the ans. also check if we have only children or only adults

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

How to solve E?

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

    First find the maximum amount of digits, $$$nDigits = N / mn$$$ where $$$mn$$$ is the minimum over all $$$C_i$$$.

    After that, loop from the most significant to the least significant digit while greedily assigning the digit's number by taking the maximum $$$j, j \in [1, 9]$$$, where $$$n - C_j \geq rest * mn$$$. $$$rest$$$ is the number of remaining unassigned digits. After a valid $$$j$$$ is found, reduce $$$n$$$ by $$$C_j$$$.

    Submission

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

can any one help me with D , I think I miss understood the question . They are saying that : "Takahashi's objective is to become able to choose a starting trampoline such that he can reach any trampoline from the chosen one with some jumps."

some jumps means we can assume that he will be able to jump for each consecutive pair right ?

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

Hi Everyone, Can anyone help to find the mistake in my code of F? Link to Solution

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

can anyone please write editorial of all questions so that it will be helpful for all

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

For problem F, my solution is giving runtime error on 27 hidden cases. Why? https://atcoder.jp/contests/abc257/submissions/32791294

UPD: I have done the same thing as editorial except DFS instead of BFS, which I don't think should make any difference

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

    It makes all the difference, because the graph isn't necessarily a tree/forest, so there may be more than one simple path between nodes of different lengths, and DFS doesn't necessarily find the shortest of them