Atcoder Beginner Contest 257 Discussion?

→ Обратите внимание

До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	maomao90	174
2	adamant	164
2	awoo	164
4	TheScrasse	160
5	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя iLoveIOI

Atcoder Beginner Contest 257 Discussion?

Автор iLoveIOI, история, 22 месяца назад, По-английски

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

Does anyone know how to solve Ex?

iLoveIOI
22 месяца назад
36

Комментарии (31)

Показать архивные | Написать комментарий?

ustaritz

22 месяца назад, # |

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

→ Ответить

harpreet1237

22 месяца назад, # ^ |

← Rev. 2 →

+16

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

→ Ответить

why_I

22 месяца назад, # ^ |

← Rev. 2 →

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

code

Your code here...

void myfunc()
{

            int n;
            cin >> n;
            vector<vector<int>>vv(n, vector<int>(3));
            for(int i=0; i<n; ++i)
                cin >> vv[i][0] >> vv[i][1] >> vv[i][2];
            
            vector<bool>vis(n);
            function<int(int, int)> dfs = [&](int cur, int s)
            {
                vis[cur] = true;
                int cnt = 1;
                int x = vv[cur][0], y = vv[cur][1], p = vv[cur][2];
               // cout << x << " " << y << endl;
                for(int i=0; i<n; ++i)
                {
                    if(vis[i])continue;
                    int x1 = vv[i][0], y1 = vv[i][1];
                    int dis = abs(x-x1)+abs(y-y1);
                    //cout << "SE " << x1 << " " << y1 << " " << dis << " " << p << endl;
                    if(dis<=s*p)
                    {
                        cnt+=dfs(i, s);
                    }
                }return cnt;
            };
            int ans = 2e15;
            for(int i=0; i<n; ++i)
            {
                int low = 0, high = 1e11;
                int res = 0;
                while(low<=high)
                {
                    int mid = (low+high)/2;
                    fill(all(vis), false);
                    if(dfs(i, mid)==n)
                    {
                        res = mid;
                        high = mid-1;
                    }else low = mid+1;
                }ans = min(ans, res);
            }
            cout << ans << endl;         

}

I have used #define int long long

→ Ответить

thatsramen

22 месяца назад, # ^ |

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

→ Ответить

Kartik1508

22 месяца назад, # ^ |

-6

explain your solution

→ Ответить

bashkort

22 месяца назад, # ^ |

rude

→ Ответить

ustaritz

22 месяца назад, # ^ |

With 4e9 it works fine. thanks.

→ Ответить

rgnerdplayer

22 месяца назад, # |

+12

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

→ Ответить

rgnerdplayer

22 месяца назад, # ^ |

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

→ Ответить

milind0110

22 месяца назад, # ^ |

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

→ Ответить

Zain

22 месяца назад, # ^ |

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).

→ Ответить

sksshivam007

22 месяца назад, # |

D was a nice variation of Floyd Warshall algorithm

→ Ответить

Dan4Life

22 месяца назад, # ^ |

BFS is a nice variation of Floyd Warshall?

→ Ответить

harsh__h

22 месяца назад, # ^ |

← Rev. 3 →

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

→ Ответить

Dan4Life

22 месяца назад, # ^ |

Interesting solution

→ Ответить

SummerSky

22 месяца назад, # ^ |

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

→ Ответить

lbntxdy

22 месяца назад, # |

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

→ Ответить

Dan4Life

22 месяца назад, # ^ |

I got WA in one test case in F smh.

→ Ответить

neelakshsh

22 месяца назад, # |

Problem C? Can anyone mention the approach? Thanks!

→ Ответить

spookywooky

22 месяца назад, # ^ |

← Rev. 2 →

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.

→ Ответить

llc5pg

22 месяца назад, # ^ |

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.

→ Ответить

Dan4Life

22 месяца назад, # ^ |

← Rev. 2 →

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

→ Ответить

ninjamayank

22 месяца назад, # ^ |

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

→ Ответить

adityagamer

22 месяца назад, # |

How to solve E?

→ Ответить

aspireboy007

22 месяца назад, # |

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 ?

→ Ответить

adityagamer

22 месяца назад, # ^ |

No. Read sample test case explanation

→ Ответить

codermaniac

22 месяца назад, # |

← Rev. 3 →

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

→ Ответить

Involution

22 месяца назад, # ^ |

← Rev. 2 →

Consider the case

3 2

0 1

0 3

Just add a line ans = min(ans, st + en + 2); and it should AC.

→ Ответить

codermaniac

22 месяца назад, # ^ |

Thanks!!!

→ Ответить

adityagamer

22 месяца назад, # |

← Rev. 3 →

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

→ Ответить

Spheniscine

22 месяца назад, # ^ |

← Rev. 2 →

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

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 19.04.2024 00:34:42 (i1).

Десктопная версия, переключиться на мобильную.

При поддержке