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

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

We will hold AtCoder Regular Contest 152.

The point values will be 400-500-600-700-800-1000.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +109
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will participate. Give me 2 Dan.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    May not get 2 Dan, but the problems are very interesting!!! Thank you, writer!!!

    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I'm so proud that I've solved ABD and I'm sure to get positive delta :)

»
16 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

What the hell are the samples? They're so weak

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

I'm so sad right now. Here is why.

Why
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Any hints for C?

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    +1

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think the idea behind problem C is quite inspiring, although I still can not understand the editorial. I have realized that selecting some value s means a mirror symmetry, but can't go further. Waiting for some other hints too.

»
16 месяцев назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

What a weird contest. Difficulty to me was A<E<D=C<<<<B.... I did not prove B too, just convinced myself that its ARC B so guessed some lower bound and it worked.... was also very scared to submit E. Thought I misread but it is strangely that easy.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    E is more of a statement parsing problem but in a good sense. I don't think it's an easy problem for most participants because you need good skills in constructing math models and understanding what is important.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    B is quite easily solvable if you notice that if they need to pass each other twice, they might as well start at the point where they passed each other for the first time.

»
16 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

That was so hard that I only solved A. :(

»
16 месяцев назад, # |
Rev. 2   Проголосовать: нравится -39 Проголосовать: не нравится

What the hell was that ??? I'm 1667 Elo on codechef and 1132 Elo on codeforces and unable to solve problem A. It's ridiculous.

And Editorial provide no explanation of the formula.

I basically solve nothing and learn nothing.

I Will no more do Regular Contest for a long long time...

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Go and do more ABC problems. They are much easier.

    When you are likely to solve problem E~F in ABC, then back to ARC. I am sure you can enjoy the problems.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain what needed to be done in problem A? and why was it to be done this way!?

I don't understand the editorial to a good extent, maybe someone can help here.

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Ordering of the group matters like they will come in the order given there so you just need to let the group sit like upcoming can't seat so here only two kind of group make exists (i.e. size of 1 and 2) so group of size 1 can sit anywhere, ans can be "NO" only when a group of size 2 arrives! with some condition.

    So we just need to let groups sit so that it can occupy one or two more space than their own sizes which will lead to not make a sit for upcomers.

    Remember group of 2 only will face difficulty always!

    My Code

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My approach is to simulate the worst case that each arrived group will pick a position one unit away from previous group if possible. i.e. x group1 x group2 x group3 ... where x is empty seats.

»
16 месяцев назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

Thank you for your participation!

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone prove the solution of B problem, I solved but I can't prove it.

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain C in detail? I can't understand the solution...

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    Consider a sorted sequence and arbitrary two operations with $$$s_1$$$ and $$$s_2$$$. The sequence changes by $$$+2(s_1-s_2)$$$, the order of elements is unchanged. Here $$$s_1 = a_p$$$ and $$$s_2 = 2s_1-a_r$$$ for some $$$p,r$$$, so $$$2(s_1-s_2) = 2(a_r-a_p)$$$. Obviously then, if $$$g$$$ is the GCD of all elements, then their remainders modulo $$$2g$$$ can't change. In an even number of operations, it's clear that the smallest possible value of the first element is $$$a_1$$$ modulo $$$2g$$$.

    The remainders modulo $$$2g$$$ won't change in one operation either, since $$$2a_p-a_i = 2(a_p-a_i)+a_i \equiv a_i$$$ modulo $$$2g$$$. If the number of operations is odd, all that matters is that the order of elements in the sorted sequence is reversed, so the smallest possible value of the first element could be $$$a_N$$$ modulo $$$2g$$$ instead. (Since $$$g$$$ is the GCD of differences, each $$$a_i = b_i g + r$$$, only parities of $$$b_1, b_N$$$ matter.)

    Finally, it's always possible to construct a sequence in which the smallest element is $$$a_1 \% 2g$$$ by first adding and then subtracting some 2*differences, see Bezout's identity. The rule on non-negative elements isn't broken then.

»
16 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Why this is wrong for B?

constexpr int N = 200005;
int a[N];
set<int> s;
signed main(){
    int n, l;
    cin>>n>>l;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int ans = inf;
    for(int i = 1; i <= n; i++){
        s.insert(l - a[i]);
    }
    int mi = inf;
    for(int i = 1; i <= n; i++){
        set<int>::iterator it=s.lower_bound(a[i]);
        set<int>::iterator it2=it;
        if(it!=s.begin()) it--;
        if(it2==s.end()) it2--;
        mi = min(mi, abs(a[i] - *it));
        mi = min(mi, abs(a[i] - *it2));
    }
        ans = min(ans, mi * 2 + l * 2);
    cout<<ans<<endl;
    return 0;
}