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

Автор vovuh, 9 лет назад, По-русски

Здравствуй, Codeforces!

5 августа 2015 года в 19:00 Мск состоится Codeforces Round #Pi для участников второго дивизиона. Участники первого дивизиона традиционно могут поучаствовать вне конкурса.

Это мой первый раунд на Codeforces. Надеюсь, что задачи вам понравятся и это даст мне стимул для подготовки новых раундов! Желаю всем быстрых Accepted и успешных взломов!

Хочу поблагодарить Михаила Мирзаянова (MikeMirzayanov) за замечательные платформы Polygon и Codeforces и за помощь в придумывании задач, Максима Ахмедова (Zlobober) за помощь в подготовке соревнования, Марию Белову (Delinur) за перевод условий на английский, а также моих друзей Данила Сагунова (danilka.pro) и Виталия Кудасова (kuviman) за прорешивание задач.

Участникам будет предложено 6 задач и два с половиной часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

UPD: Разбалловка: 500-1000-1500-2000-2500-2500.

UPD: Разбор

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I don't know about others, but I don't have any idea why the round name is "Pi". Would you make it clear please?

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

    Maybe because it's round 314.

    As a remainder PI = 3.1415...

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится -7 Проголосовать: не нравится

      Oh, it seems so :) I thought that round #314 will be held after Pi-round, but I was wrong.

      P.S. Thanks for clarifying. Perhaps, I would not participate in this round because Pi-round sounds like a Math-round. And I'm weak at math :P

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

        So, next PI round will be at 3141 th contest ... about 3000 rounds later :v :P

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

          Looking forward to participate in that Round :)

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

            Well, that would be more than 50 years from now. So, I don't want to miss today's Pi round. Let's hope that, we can see our grandchildren participating in a CF Pi-round :P

»
9 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Hopefully there will be interesting and original math problems!

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

    What is the point of hoping for something like this; this is not IMO. Instead, you should be hoping for an interesting and varied problem-set — one consisting of other things as well.

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

nezt PI Round #3141 ?

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Hello! Should I pronounce your name as Pi-kachu?

»
9 лет назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

"В раунде ожидается 2*Pi задач. Так как это число меньше семи, то проведение раунда для обоих дивизионов невозможно, only div 2. Но так как это число больше пяти, то на решение задач будет дано два с половиной часа."

»
9 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

I think I'll skip this one and wait for Codeforces Round #Tau

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Is it a rating round?

»
9 лет назад, # |
  Проголосовать: нравится +240 Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

W<...

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

Maybe there will be a problem about circles ? :-)

»
9 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Maybe there will be a problem about circles ? :-)

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

So this contest will be all about math problems? (#Pi)

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

I think that this round shuld be irracionally long. Lets say 3h 8m 30s or 3.14h :)

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Здесь: Участникам будет предложено 6 задач и два с половиной часа на их решение.

Оповещение на почте: Продолжительность соревнования — 2 часа.

Где правда?

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

i'm thinking what will a Codeforces Round #i be like... i'd be imaginary for sure :D

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

"Wish you quick Accepted verdicts and successful hacks." — interesting combination. To hack successfully, I need to lock a problem. Then someone hacks me (according to your wishes) and I can't correct my solution because I've locked it before. Very sad scenario.

Anyway, have fun everybody :)

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

why 2:30 ??????

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

why 2:30 ???

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -86 Проголосовать: не нравится

ВСЕМ УДАЧИ НА СЕГОДНЯШНИМ СОРЕВНОВАНИИ!!

ПУСТЬ У ВАС БУДЕТ БОЛЬШОЙ РЕЙТИНГ И ВСЕ ХОРОШО!!!

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

    Не думаю что на CF у всех проблемы со зрением.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -80 Проголосовать: не нравится

      ОПЯТЬ ТЫ))))) На кодфорцезе у всех проблемы с логикой а не зрением))))) а большими буквами потому что искрени от всей души!!!!!

      УЧАВСТВУЙ СЕГОДНЯ НА СОРЕВНОВАНИИ ПОСМОТРИМ КТО ИЗ НАС БОЛЬШЕ РЕШИТ ЗАДАЧЕК!!!!)))))
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    сегодняшнЕм

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -26 Проголосовать: не нравится

      Какая разница кто как пишит???

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        да уш какая разнитца кто-как пишит
        

        Грамотное письмо радует глаз, делает общение намного интереснее, улучшает мнение о собеседнике

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

          лучше рейтинг себе подними а не чем на грамотность внимание обращай!!!!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -44 Проголосовать: не нравится

    СПАСИБО! И ТЕБЕ УДАЧИ MAXIMAN!!!

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

    Неужели на CF появился более упоротый человек, чем я 6 лет назад?

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

      Ты был зарегистрирован 5 лет назад. Судя по твоему комментарию, ты должен быть в CF минимум 6 лет.

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

        Вообще-то, нет. То, что я был упорот, не означает, что я был зарегистрирован на КФ. Не все упоротые регистрируются тут, знаете ли. Однако, действительно, спасибо за исправление)

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

So i guess in each of the problems today we have to be introduced with the person "Mr. PI" :D :D :D

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

when you are wishing for some body successful hacks you are wishing for some body else unsuccessful

submits!!! i don't think it's a good wish!

thanks ;)

»
9 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

2.5 hour = 6 problems? So I guess P1kachu prepare a nice problem F for us to solve...

»
9 лет назад, # |
  Проголосовать: нравится -50 Проголосовать: не нравится

define in_round_#pi ++

int RP;

int main(){ while(RP)RPin_round_#pi; return 0; //By the way,thanks to writer }

»
9 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

Round #404 will be declared as round #Error or round #NotFound

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

That proud moment when a blue coder prepares a CF round :D
Hats off !!! keep it up :D

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

This is the first contest i join ever on codeforces :)

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

Автокомментарий: текст был обновлен пользователем Zlobober (предыдущая версия, новая версия, сравнить).

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

It has been a long time since the last Div2 contest.. It's obvious that the number of registrants is very large this time and people are eager for such an event.. Let's enjoy

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

So since there are 6k+ participants, on a scale from Google.com to contest.Bayan.ir, how down is Codeforces.com going to be ?

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

6278 people registered which is more than 6274 people registered for good bye 2014

out of 6278 registrants 935 people are unrated

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The first round was written by Expert user that I have ever participated!

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

What on earth is pretest 19 in Problem E?

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

    I guess you're not finding the bridges correctly. I got WA 19 because of a caveat in my solution, I only check for edges that definitely are on the shortest path ONLY from the start and the end, but there could actually be bridges in the middle of the path too. An example edge formation , start = 1 , end = 8 : 1 2 1 3 2 4 3 4 4 5 5 6 5 7 7 8 6 8

    The edge 4 5 is definitely on the shortest path since it is a bridge in the shortest path graph. Hope it helps .

»
9 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Problem E with modulo based hacking was pretty funny.

I had a generator that generates a input for any mod. Some guy from my room sent his solution in the last moment to make sure that I can not hack him. :)

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

    Is there a solution without modulo calculations?

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

      What is a solution with modulo calculations?

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

        @ikbal can you show how you made the generator?

        Also I used doubles to calculate number of paths. Paths can be at most 10^500 which fits in a double.

        With modulo calculations, you just mod this number continuously.

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

        We build DAG where there is a directed edge (u,v) if there is an edge (u,v) in graph and dest[s,u]+dest[u,v]+dest[v,t]==dest[s,t]. Then we say that edge (u,v) is a bridge if number of ways (s,u)*(v,t)=(s,t). But this values are large, so I took them by modulo

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

          Instead of counting number of ways you can change this DAG into undirected graph (all edges become bidirectional) and just find all bridges in this graph.

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

      Yes, there is. And not only one.

      1) You can find all edges that can be in shortest path and then find bridges in this graph.

      2) Find all edges that can be in shortest path. Then realize that we are on this edge in fixed interval of time. Edge is in all shortest paths if its interval doesn't intersect with other intervals. (It's my solution, you can read it).

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

    Was my solution also hacked because of modulo? It would be quite strange since I used both overflow hash & modulo. I even changed modulo after getting hacked, but still got WA (on your hack).

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

      Just create two paths one with 10^9+7 and one with 2^64 ways. If we merge them together from their ends by an edge new long path would have (10^9+7 * 2^64) ways.

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

    What sense not to be hacked if solution is wrong?

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

    I'm wondering if his code gets accepted after all. :/

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Finally solved C with 2 seconds on timer :( That's embarrassing.

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

How to do Div2 c Geometric progrssion?

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

    You can support 2 maps, left and right. When you iterate over the sequence, you should add left.get(a[i] / k) * right.get(a[i] * k) to the answer, and then add current element a[i] to the left map and remove it from the right one.

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

Spent 30 minutes trying to find the problem with this attempt at problem C. Can someone lend a hand?

http://pastie.org/private/mmg81uzwfniinmxabqa2rw

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Я уже и забыл, как дооолго запускаются систесты.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What was test case 5 of D? I used a solution that kept track of valid intervals where battleships could be placed: if bob's shot interrupted an interval, then I split it into 2 intervals, and for each interval I calculated IntervalSize / SizeOfShip. If this was less than NumberOfShips, then I printed that index and stopped the program. At the very end I printed -1 and ended to catch the case where it is undeterminable. What is wrong with this approach?

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

What's the intended solution on D?

I tried keeping a sorted vector of pairs, representing all uninterrupted segments where you can place ships. Every time you fire a shot, you find the segment that shot is in and split the segment in two. Used binary search to make the segment searching faster, but my solution was wrong on case 5.

Is the idea wrong, or did I mess up my implementation?

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

    How do you calculate the number of ships that can be placed into one interval?

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

    Idea is ok. Alternative solution is to do binary search over result.

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

    I processed the queries from last to begin and kept a disjoint set for the connected parts and instead of splitting merging.

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

    Apparently, you can't have 2 ships RIGHT next to each other, so when calculating number of ships possible in an arrangement, you had to make sure you left 1 space in between each(so you had to add extra logic for both inside the interval, as well as between consecutive intervals.

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

    My solution was binary searching for the answer. You fix the amount of shots fired then you mark those cells. Once you've marked some cells as shot you can get the maximum amount of ships that can be placed in O(N) using greedy approach.

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

    1) Let's find the asnwer by binary search (answer — k) 2) Each iteration of search we will check by function CHECKING that says TRUE if we can't place all ships with k turns and FALSE if we can. If True, you should make left_border=k, and if False — right_border=k+1 3) How does CHECKING work? Make a vector of field and fill it by 1(free place) and 2(place where Bob shooted). Then in cycle just greedy fill it by ships from left to right and calculate its total. Return total<number_of_ships 4) PROFIT!

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Eh, I believe the "two weapons cannot touch" part in D should have been explained more clearly... I was thinking it just meant a cell cannot belong to more than one weapon (and I guess so did everyone getting WA on pretest 5).

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

    The same thing happened with me. I spent 2 hours making numerous test cases and my code was working for all of them.
    So , after the contest , upon asking adurysk I realized that two ships could not "touch" meant they couldn't be adjacent . Facepalm

    Needed to change (N/K) to (N+1)/(K+1) to get it Accepted :P

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

      It was written both in statement and in input section. How could it be explain more clearly?

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

        It just said "the ships cannot intersect and even touch each other"- it would be better if the problemsetter explicitly mentioned that you cannot place two weapons right next to each other.

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

          The author separately mentioned intersecting and touching, shouldn't that be a hint that these describe two distinct situations?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

The round was awsome. I enjoyed a lot E and F. Congrats for the round. Also , was F a dp in O(N^3*K) ?

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone help how to solve C ?? :(

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    two maps

    m1[x] = y <=> count of subsequence of length one finishing at x equals y

    m2[x] = y <=> count of subsequence of length tho finishing at x equals y

    So, we getting num a. Then ans += m2[a/k]; m2[a] += m1[a/k]; m1[a]++

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

      sorry but i didnt get u ??

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

        If we've got num a, how many subsequence of length one finishing at a? As many as subsequences of length two finishing at a/k. So ans += m2[a/k]

        Analogycal, how many subsequences of length two finishing at a? As many as subsequences of length one finishing at a/k. So m2[a] += m1[a/k]

        m1[a]++ because we've got new subsequence of length one finishing at a.

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

What was the idea for keeping track of the number of shortest path? Does it use Dijkstra?

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

Can anyone who solved F explain a solution? The problem seemed like hell to me :D

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

    DP; you put the pairs from largest to smallest. States are "the blocks you put so far are in the interval [i,j]". There are just 3 possible transitions from any state and you just need to check if any in/equality becomes invalid for each of them.

    The simplest implementation is O(KN3), which definitely passes.

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

    dp[left][right] — in how many ways can we fill blocks 1... left and right... 2N with small numbers (numbers lower that those left for interval left + 1... right - 1. We must consider 3 cases: adding two new equal numbers in left + 1, left + 2, or in left + 1, right - 1, or in right - 2, right - 1. For all 3 cases we must check is everything would be ok for them — those two places are equal to each other but lower than remaining places in left + 1... right - 1.

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится -7 Проголосовать: не нравится

OMG i forgot to remove debugging code and the stderr flushes made me TLE on problem D.... ;(

for(auto i:my)cerr << i.first <<":"<<i.second<<endl;

http://codeforces.com/contest/567/submission/12367438

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

    use tab indent to understand your bug!!

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

      There are no bugs there, its just that i'm writing a bunch of endl's to cerr (which i used while working in the problem), and i didn't remove them before submitting....

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain me how to solve problem D??

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

    One way is to find result by binary search. Then, we mark some cells as blocked and we need to count maximal possible number of ships. Say if you need more explanation.

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

      Yeah can you elaborate it more??

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

        which part?

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

          Here binary Search will be applied on what?And then How cells can be marked as blocked??

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

            Binary search on result — size of prefix of given blocked cells. Cells can be marked as blocked with array of booleans. Then we iterate from 1 to size_of_grid and calculate number of ships we can have.

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

    The rough idea is to maintain the maximum number of ships you can put on the board.
    Notice the fact when you hit a spot, you are splitting an interval(between 2 previously-hit spots) into 2 intervals. With that, you can calculate how many ships can be put on the original interval and on these new 2 intervals, and update the number we're maintaining.
    Use std::set to store previously-hit spots.

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

    Let's use a some set, which will keep disjoint segments.

    Also let's keep some value T which means what is the maximum number of ships we can arrange on a board.

    When we add a segment to the set, we must increase T by some value x, which means the maximum number of the ships we can arrange on current segment. This number is equal to (len + 1) / (a + 1) where len is a length of the segment and a is the length of the ship

    At first let's add segment (1, n) to the set.

    So, when the cell c is coming, let's find a some segment(l, r) which keeps c (l <= c <= r). We decrease T by (len(l, r) + 1) / (a + 1).

    Then we add segments (l, c - 1) and (c + 1, r) to the set and increase T by appropriated values.

    If we processed current operation and T is less than k, answer will be equal to the number of operations we processed already.

    For keeping segment we can use a simple set of pairs. My solution: 12365410

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

      Wow, I used to write a segment tree in that problem, but your solution is much more simple than mine, thanks!

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

        Of course, you can use segment tree, but I think set is the simplest one.

»
9 лет назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

Nice problems vovuh! I like C and F especially. Hope to see more rounds from you.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I got stuck (kept failing test case #13) in problem B. Embarrassing, but this was my first contest. Here is my solution:https://ideone.com/G5fuEl Can some one give me any ideas? I can't sleep, keep thinking about it :|.

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

    You can view small inputs after the contest. Scroll to the end here: 12373900

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

    In the if at line 29 you should add :

    p[abs(arr[i])]-=arr[i];
    

    This is because the person left, but you never marked him coming in. So in the beginning of the iteration you added arr[i], marking him leaving, once you understand that he's been in all along you should make up for his coming.

    Feel free to ask questions :)

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

      Just one question I had in mind.. did you guys used some debugger when you were starting out?

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

        Debug output is usually the fastest way. Just add some safeguards to your template to prevent it from working on the server side:

        #ifndef ONLINE_JUDGE
        #  define LOG(x) (cerr << #x << " = " << (x) << endl)
        #else
        #  define LOG(x) ((void)0)
        #endif
        

        ONLINE_JUDGE is defined in the Codeforces environment.

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

    Your if "if(p[abs(arr[i])]<0){" should be done at most once for every arr[i]. You have WA for test

    3
    - 5
    + 5
    - 5
    
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the idea of E?

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

    My solution is to dijkstra 2 times, one from s and one from t

    for each edge u->v if dist(s->u) + c(u,v) + dist(v, t) == dist(s, t), u->v may be a "sure" edge

    Take all those edges and eliminate the direction, we can find the bridge by simple DFS.

    Note that there may be multiple edges between two vertexes. I failed E during the contest because of that :(

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

In problem C, what would be the answer if k=1 ??

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

    You could easily count how many times a given numbers repeats using a map, then it's basically C( [amount of repetitions of this number], 3) which is equal to [reps * (reps-1) * (reps-2)/6] when you simplify the formula.

  • »
    »
    9 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится
     for(int i=0;i<n;++i)
            {
                scanf("%d",&t);
                if(k==1)res+=(a[t]*(a[t]-1))/2;
                ++a[t];
             }
    cout<<res;
    

    For k=1 this program gives correct anserws. PS.a is map<long long,long long>

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

public void solve(int testNumber, InputReader in, OutputWriter out) { int n = in.readInt(); boolean[] t = new boolean[1000010]; int cap = 0; int cur = 0; for (int i = 0; i < n; i++) { String s = in.readLine(); String[] ar = s.split(" "); if (ar[0].charAt(0) == '+' && !t[Integer.valueOf(ar[1])]) { cur++; t[Integer.valueOf(ar[1])] = true; } else if (ar[0].charAt(0) == '-' && t[Integer.valueOf(ar[1])]) { cur--; } else if (ar[0].charAt(0) == '-' && !t[Integer.valueOf(ar[1])]) cap++; cap = Math.max(cap,cur); } out.print(cap); }

my code above for problem B is incorrect, because the bold line, without that line, the code is correct. But the number assigned to people is unique, why can someone take same number twice?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо balalaika, можете не обращать внимания.

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

    lower_bound(Value) — первый элемент item >= Value

    upper_bound(Value) — первый элемент item > Value

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

      Да я знаю про это.

      Можете дать тест, в котором они дают различные ответы?

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        10 2 4
        3
        5 6 1
        

        Этот тест из задачи на котором ваша программа и валится

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

        Не знаю, чем Test#8 не устроил, но я вижу такую ошибку:

        Допустим, есть интервал (x, y). Вы стреляете по x. Тогда (x, y) должен превратиться в (x+1, y). В неверном вашем же коде представим себе ситуацию следующую: есть интервал (1 N). Стреляем по 1. Тогда у вас итератор будет указывать на несуществующий элемент, ибо вначале вернется итератор на (1 N), который есть begin(), а потом вы его декрементируете и работаете с несуществующим итератором.

        Надеюсь, что помог.

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

    забьем на it-- пока. тогда в 1 случае итератор будет указывать на элемент, поле first которого строго больше x, во втором — не обязательно.

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

Рейтинга долго нет. С кодэфом что-то не так или опять бан читерам роздают?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    рейтинга всегда долго нету видимо они по несколько раз его пересчитывают что бы не ошибиться...

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

      а то что его компьютер считает это ничего?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится -10 Проголосовать: не нравится

        Я же сказал что точно не знаю но думаю именно поэтому. Даже суперкомпьютеры иногда дают сбои а у кодфорцез обычные. Выводы делай сам!

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

Wow the problemsets are really nice. It's hard to believe that it's prepared by a blue coder.

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

    That's because, this rating shows the measurement of competitive programming skill which is different from problem inventing skills. There are many cases where enough knowledge doesn't help the subject to do better in competitive programming.

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

Was this contest Unrated???

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

Я, наверное, тупой, но в чем косяк? http://codeforces.com/contest/567/submission/12376471

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

    там 2 * 100 * 1000 клеток. если исправить то проходит.

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

      Да, спасибо, я уже увидел. Пойду в глаза чего-нибудь закапаю.

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

Can someone point out the mistake in this code?

Problem D

Thank you in advance.

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

    it=s.upper_bound(mp(mov[i],-1)); should be it=s.upper_bound(mp(mov[i],n+1)); in order to find the intersecting interval after decrementing it. If you have an interval that starts at mov[i], upper_bound will return it and decrementing will miss it.

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

While solving E, i had to keep track of number of shortest paths passing through a particular edge. But this value can exceed 10^18. I used hashing modulo 2 large primes to keep track.

Is there any other (deterministic) workaround to this?

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

used coordinate compression in c :P

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

It's just div 2, but I'm very happy anyway. Nice problems! :D

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

It's just div 2, but I'm very happy anyway. Nice problems! :D

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

Thanks for a great contest!

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Hello, this is my first contest. I'm just curious about one thing : when does the rating change after a contest?

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

    Hello, dear newcomer! You should now that right now Mike Mirzayanov, Zlobober and others are sitting at the round table and hotly-debate everyone's rating change. It takes a lot of time, you know. It was my not serious thought of things when I took part in my first contests. Now I think, that the question of looking for cheaters is hardtime. Maybe anyone know another 'why'?

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

      Thanks for the answer, I expected it to be more automatically updated. Great to know that they look for cheaters.

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

    Mia rating

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

Your problems are really amazing. Thank you :)

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

Подскажите, пожалуйста, в чем ошибка?
http://codeforces.com/contest/567/submission/12378484

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    Посмотри на свой ответ и на ответ жюри. По нему очевидно, что у тебя переполнение. Замени все на лонги.

    P.S. при том очевидно, в каком месте нужно заменить

»
9 лет назад, # |
Rev. 5   Проголосовать: нравится -7 Проголосовать: не нравится

Thank you for the contest. Can you update top 5 contestants as well :D ?

Update: Down voters, so you don't want to see your name when you are in top 5?

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

Can anybody help me check my code of problem E: http://codeforces.com/contest/567/submission/12382102

Thanks!

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

Could someone explain this testcase (which is the 37th) of Problem E?

10 10 1 10
1 5 178
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157

The output is NO for all edges except the two that lie on the unique shortest path of length 378, for which the answer is YES. What I don't understand is why the answer for all other edges is NO. Let's take for example the path (1 — 5 — 3 — 10 ) of length 470. The first and the last edge could be reduced by 93 to give a path of length 377 in which case they lie on the unique shortest path. I probably misunderstood something in the problem statement. Thanks in advance.

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

    I had the same problem.

    In the statement it says The road is directed from city ai to city bi. In this test case you can't go from 5 to 3 and therefore the path (1 — 5 — 3 — 10) doesn't exist.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

It's my first contest in codeforces and I enjoyed it very much. Wish your next round,and I hope I can do better then.

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

could someone tell me why this solution gives TLE for problem D? It's run in O( m log(m) ) 12387839

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

Кто-нибудь может объяснить мне, в чём смысл предварительной регистрации?! Из-за неё пропустил соревнование :(

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

    Здесь был тупой комент

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

      Ерунда. Предварительная регистрация нужна для распределения по комнатам. В контестах по правилам ACM (давно же их тут не было) регистрация часто не прекращается даже после начала контеста.

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I am not from the top 5, but I love to see the winners' names in the updates :)

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

Подскажите пожалуйста, а в раундах только индивидуальное участие допускается? Команда может участвовать или нет?

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

    Смотря в каких раундах. В обычных только индивидуальное участие, в специальных иногда могут соревноваться и команды.