Problem analysis of Codeforces Round #401 (Div. 2)

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

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:54:05
Зарегистрироваться »

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

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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

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

Всё →

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

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

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

→ Прямой эфир

Детальнее →

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

Problem analysis of Codeforces Round #401 (Div. 2)

Автор GlebsHP, история, 8 лет назад, По-английски

Tutorial is loading...

Разбор задач Codeforces Round 401 (Div. 2)

GlebsHP
8 лет назад
37

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

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

GlebsHP

8 лет назад, # |

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

→ Ответить

Sazzon

8 лет назад, # |

← Rev. 2 →

In the problem C I used a map to store previous queries to pass on the 100th test case. It worked, lol

→ Ответить

luodianUp

8 лет назад, # ^ |

← Rev. 2 →

and main program?Are you using the is_sorted() function in stl?

upd:sorry I'm bit naive

→ Ответить

Sazzon

8 лет назад, # ^ |

No, actually I precomputed the answer as said in the problem explanation.But my algorithm runs on O(k*m), Because it checks every column, it's pretty easy to repeat queries just to slow it down. Só I used a map to store previous queries. Here is a link: 24986527.

→ Ответить

luodianUp

8 лет назад, # ^ |

you are so clever.

→ Ответить

NGUYEN_THANH_LOI

8 лет назад, # ^ |

I saw your solution, the key here is using "pref" dynamic programming, not the map. No need to store the previous queries, I can pass all test without map and faster two times yours. 25166547

→ Ответить

Sazzon

8 лет назад, # ^ |

What I meant was that I didn't need to quite do what the editorial said and it worked. Later I did what the editorial explained.

cheers

→ Ответить

NGUYEN_THANH_LOI

8 лет назад, # ^ |

:) But they are similar!

→ Ответить

-wolfie-

8 лет назад, # ^ |

nice....haha...

→ Ответить

Jori

8 лет назад, # ^ |

Seems distinct queries are very needed

→ Ответить

Jori

8 лет назад, # |

← Rev. 3 →

There may be a mistake in prob E's solution.

ans[i] += opt[i].height; should be ans[i] += r[i].height;

opt.back() should be opt.top()

Is it right?

→ Ответить

GlebsHP

8 лет назад, # ^ |

Yes, fixed now. Thanks you!

→ Ответить

mo7amed_a7med

8 лет назад, # |

for problem E can't we use modified longest increasing sub-sequence in O(nlgn) ?

→ Ответить

lukecavabarrett

8 лет назад, # ^ |

← Rev. 2 →

i did something similar to LIS, but in the end it's not so far from the solution proposed above

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
int II(){int n;scanf("%d",&n);return n;}
void II(int n){printf("%d\n",n);}
typedef long long ll;
void LL(ll n){printf("%lld\n",n);}
typedef pair<int,ll> il;

struct ring_t {
  int inner,outer,height;
  bool operator<(ring_t b)
  {
    if(b.outer==outer)return inner>b.inner;
    return outer>b.outer;
  }
};

#define MAXN 100000

ring_t V[MAXN]; ring_t *vend=V;

int main()
{
  int N=II();
  set<il> dp;
  while(N--)*vend++={II(),II(),II()};
  ll H=0;
  sort(V,vend);
  for(ring_t *x=V;x<vend;x++)
  {
    //printf("adding %d,%d,%d",x->inner,x->outer,x->height);
    ll myH=0;
    {
      auto it=dp.lower_bound({x->outer,-1});
      if(it!=dp.begin())
      {
        it--;
        myH=it->second;
      }
    }
    myH+=x->height;
    H=max(H,myH);
    {
      auto r=dp.insert({x->inner,myH});
      if(r.second)
      {
        auto it=r.first;
        auto prv=it;prv++;
        while(prv!=dp.end()&&it->second>=prv->second)
        {
          dp.erase(prv);
          prv=it;prv++;
        }
      }
    }
    //for(auto y:dp)printf("[%d|%d] ",y.first,y.second);putchar(10);
  }
  LL(H);
}

→ Ответить

Dewdis

8 лет назад, # |

← Rev. 2 →

In problem C, should be a[i, j] <= a[i + 1, j] instead of a[i, j] < a[i + 1, j].

→ Ответить

timus19

8 лет назад, # |

+19

When CF round #403 begins?

→ Ответить

Lance_HAOH

8 лет назад, # |

I see that there is a binary search tag for problem C. Did anyone solve this problem using binary search? Please enlighten me on how to use binary search for this problem.

→ Ответить

-wolfie-

8 лет назад, # ^ |

If you just store the indexes which are greater than the next number in an adjacency list for each column. Then for each query you could apply binary search within that range and see if no such element exists even for one column, then Yes. But there seems to be some kind of optimization that I have missed. Plus, the approach is way slower than that in the editorial. This might help

Please let me know if I'm wrong.

→ Ответить

noelnadal

8 лет назад, # |

Here are two submissions for problem D.

26348627

26348633

These two submissions contain exactly the same code. Yet, I didn't use the same compiler. The first one got TLE, and the second one got Accepted. I would be thankful if anybody could explain me why.

→ Ответить

kingosak

6 лет назад, # |

can someone provide me dp solution for B

→ Ответить

sultan_01

5 лет назад, # ^ |

I have used hashing instead of dp and my solution works in O(n). 67647151

→ Ответить

HMS_Warspite

5 лет назад, # |

-7

DDangr coongj sanr vieetj nam muoon nawm >u<

→ Ответить

Hd7

5 лет назад, # |

Editorial for problem C should be:
* $$$up(i,j) = up(i+1,j)$$$ if $$$a[i][j] \leq a[i+1][j]$$$
* $$$up(i,j) = i$$$, otherwise.
I think it is more suitable with your explanation.

→ Ответить

Verdusk

5 лет назад, # |

← Rev. 3 →

I think I got E in O(n log n) time.

Sort rings by outer radius first, then inner radius. Sorting should take O(n log n).
From the end of the array (biggest outer radius), do the below for each ring:

If the ring would fall through the ring that is on top of the current stack, get rid of ring on the top of the stack, repeat until fall is no longer detected. Then add the ring to the stack, since you can do so without the ring falling.
Keep track of the sum of height of rings in the stack: when adding a ring, add to the sum, when removing from the stack, subtract from the sum.
When adding a ring, update the "maxHeight" variable with the current sum of height, that is, maxHeight = max(maxHeight, currentSum), this variable will be the answer by the end.

Knowing that each individual ring can only be added and removed to the stack one time each, this part of the program takes O(n) time.

The whole algorithm thus takes O(n log n + n) = O(n log n) time.

Code: https://codeforces.net/problemset/submission/777/71466945

Feel free to try and prove me wrong.

→ Ответить

SLIMSHADYNICK

5 лет назад, # |

Problem E can be solved using Fenwick tree and coordinate compression! First compress the values of a and b. Sort the rings first based on b,then on base of a in decreasing order. Fenwick tree will store the max height account so far till the value 'a'. We start iterating from 0 to n-1, and the for the max value in the fenwick tree till b[i]-1 call it qmax, and update fenwick tree at index a[i] by h[i]+qmax, and max height so far by h[i]+qmax!

→ Ответить

towrist

5 лет назад, # |

← Rev. 2 →

I think that the editorial proof of D is unnecessarily involved. We can just prove by induction that at the $$$mth$$$ step, the length of string $$$s_t$$$, $$$t=n-m+1$$$ is maximum as produced by our algorithm. Can anyone prove me wrong?

→ Ответить

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

Время на сервере: 22.11.2024 09:40:56 (j1).

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

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