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

Автор cookiedoth, история, 5 лет назад, По-русски

Привет, Codeforces!

Рад пригласить вас на Codeforces Round #526, который пройдет 10.12.2018 19:35 (Московское время). Раунд будет рейтинговым для обоих дивизионов.

Задачи были подготовлены мной, TheWayISteppedOutTheCar, xoxo, Egor.Lifar.

Большое спасибо ismagilov.code, Kuyan, 300iq, alexey_kuldoshin, Jatana за тестирование задач, arsijo и vintage_Vlad_Makeev за помощь в подготовке раунда, а также MikeMirzayanov за системы Codeforces и Polygon.

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

UPD:

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

Разбалловка в Div. 2: 500-1000-1500-1750-2250-2750

UPD: Поздравляем победителей!

Div. 1:

  1. Radewoosh

  2. DearMargaret

  3. Endagorion

  4. ksun48

  5. Um_nik

Div. 2:

  1. Muffinhead

  2. Usu

  3. arjunsanjeev7

  4. IAmNotGood

  5. tyler

UPD: Разбор

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

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

у вас время сломалось

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

I think the date is wrong

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

I am confused.

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

Aww, new codeforces round, new chance to fall!

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

I am very interested in knowing what vintage_Vlad_Makeev is planning to do??XDD

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

Time is always a severe problem for us Chinese fanatic.

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

    yes!Next regular time is 9:45pm, I think this is ok,but too far.

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

      Sounds like u have long awaited for that aha

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

        oh!There will be no class tomorrow morning,I am ready gang tonight,after i'm ready the first question,the registration channel is closed.

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

        I'm not sure i will join this contest,so I haven't register advance!!! no, the The prophecy is coming true.(唉!真的要等到23号才能打)

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

“Is this rated?” hURr DuRR

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

i hope that problems will be graduated in terms of difficulty ^^

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

yey i cant wait for all of you to lose rating! :D

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

2300

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

Again a new chance to restart coding...

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

does cf stops producing 5 problem Div2.s ?

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

Wish for 2400.

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

how many problems are shared between the divisions ?

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

Yes I wont lose rating

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

Сколько вам заплатил Vk?

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

Div2A was such broken english that I couldn't comprehend the problem statement. After reading the statement multiple times I reached an understanding which was in conflict with pretest 1 answer. I submitted a question and nobody answered it. So I guess I'm just gonna skip this round then.

Please don't google-translate russian problems into english. If you can't write english problem statements, ask help from someone who speaks english. If you can't explain a simple problem (such as div2A level) in an understandable way, please don't write problem statements at all.

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

    I was confused by Div1A not mentioning that you can choose u,v freely and talking about 'the city u/v' and 'the path' (not a city/path).

    So I asked 'what are u,v, they are not in the input' — answer: 'Yes'

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

    Problem statement in russian was very unclear too — I doubt we should blame google-translate here.

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

How can i register now?

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

Give more explanation for Div2C. Really bad english.

»
5 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

RIP problem statements

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

Lol. C was harder than D and E. How to solve C?

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

    Use a segment tree to quickly calculate, for any segment [l, r], if there is a path that contains all values in [l, r].

    Each node should store a pair representing a path, but combining pairs requires a lot of casework and isn't fun :(

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

      Nice.

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

      Actually restrictions were rather kind, so something like checking for all pairs of endpoints of two paths that all other endpoints lie on a path between them still passes. So you could do it without any casework.

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

      What does this comment has to do with problem C?...

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

        The l and r are the interval of node i in the DFS traversal of the tree. So we can store the l[p - 1[i]] in a max segment tree, and the r[p - 1[i]] in a min segment tree, then all values 0, 1, ..., K lie on an ascending path iff ltree.query(0, K) < rtree.query(0, K).

        EDIT: I was working on this at the end of the contest but there was too much casework glueing together two paths and my code was a mess so now I only got problem B, RIP :(

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

How to solve DIV1B?

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

    for each prefix, calculate the maximum string you can make, then add it to the answer.

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

    The characters being 'a', 'b' allows for a pretty easy solution that is barely programming. You can consider s and t as binary strings and iterate through their prefixes. While the prefix difference is less than k, you add it to the sum and when it grows larger you add k instead.

    → Reply

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

Was the intended solution to E convex hull trick? If so why is it after C and D in the list? :Dd

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

can someone explain div 2 C problem and its solution?

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

    We have to find the no. of index sequences where in which all the string elements at those indexes are equal to 'a' and between every two adjacent indices there must be atleast one 'b'.

    So, we divide the string into pieces, where each piece contains those "a's" which are preceded by same no. of "b's". e.g. : "aabaabbaaabab: is divided into "aab" "aabb" "aaab" "ab".

    Now, from each piece, we have the choice of taking either 0, 1, 2... till count of "a's" in that piece. So, total "count of a's in that piece + 1" choices.

    Now, to find the total required sequences, we multiply the no. of choices from each piece. But, since we want to choose a non-empty sequence, we subtract 1.

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

      Sorry I'm facing problem yet to understand the problem. Help me please:

      For the example you given, "aabaabbaaabab, [0], [1], [0][1] are also valid sequence. Right? But, how do they satisfy the condition that there must have at least one b between two adjacent indices?

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

        [0, 1] is not a valid sequence as the first two a's don't have any 'b' in between.

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

          Why [0], [1] are valid?

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

            Yes, 0 and 1 as two different sequences are valid as they contain only one 'a'.

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

              I failed to relate this with given conditions of the problem please help me to do so.

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

                Okay,

                The problem statement says to find the no. of strictly increasing sequences p1, p2, ..., pk such that:

                This means value of string at all these indices of sequence must be 'a'.

                • For every i, except the last one in sequence, there must be a 'j' such that and .

                This means, for any two consecutive elements of sequence, there must be a 'b' in between those two indices of the string.

                Please let me know if you get it now.

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

              The two given conditions should be met at a time or else?

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

    Problem — Count number of subsequences of the string which consists of only a's and every two a's should have at least one 'b' between them in the original string.

    Solution — Pretty standard approach. Iterate over the string. Maintain a counter. When you get an 'a' increment the counter. When you get a 'b' multiply the counter to answer and set counter to 0. Do not forget to multiply the counter again for trailing a's.

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

    It's a classic dynamic programming problem. The first thing is that you should save the position of 'a' beforehand. Okay, so f[i] is the way to choose the array with the positions of all elements are not greater than the position of ith 'a'.
    f[i] = f[i-1]; f[i] += 1 (Should take care of the case that the array contains only one 'a'). Now if we choose ith 'a', we should find the previous proper 'a' that has the largest index, which means that between that 'a' and the ith 'a' contains a least on 'b'. This can be done by binary search. The overall complexity of this sol is O(nlogn)

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

Коротко о том как потерять 40 позиций.

https://codeforces.com/contest/1084/submission/46866248

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

That feeling when you spent nearly 1h to think about 1A but finally realized that the condition that one should have enough gas to pass through a road is useless.

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

    Well, you also may consider it and honestly push maximum possible sums in two dfs, one for pushing them to the root and another one for pushing them from the root.

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

    What? How?

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

    can you please elaborate why that condition is useless?

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

      Because that condition will always get satisfied,when you take two maximum sums among its child.

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

      Because if for any path, at some edge the condition isn't satisfied, then by erasing the path from the starting vertex to that will yield a path with a better result. Thus we only need to find the maximum answer without considering the condition, that is, the optimal answer we find in this way must satisfy the condition.

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

      Here's a little more elaborate proof that I wrote.

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

how to solve C without seg tree??

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

Div2D test 7 anyone please?

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

early system testing nice ^^

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

For div1E, is it enough to use long double?

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

    why you used double dude? i am sure there is no fraction needed

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

      I used convex hull. To determine if a point is to be deleted, I needed a check which could go like till 10^27.Well, I used an int128 library for this check.

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

C and F were very good problems! (Too bad I didn't solve any of them :(.)

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

i think div 1A should be easier (people usually leave the contest after they think the first problem is too hard for them, or at least it need a long time to solve it).

the number of participant in this contest is less than 400.

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

Why are constraints so tight in E? My solution worked 1840ms/2000ms on pretests (I don't know if it will pass, although I'm 100% sure idea is fully correct) and it had 64-bit integer overflow issues. So why did you do so? Am I obliged to prepare very fast CHT beforehand to pass on this problem?

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

    Maybe they wanted to block O(nlogn) CHT. But it is poor because there is a sort involved already.

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

      It seems neither possible nor reasonable in such constraints...

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

        This is so sad that someone didn't prove it but got acc and you didn't prove it too but you didn't get acc :(((

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

          Wtf are you talking about?.. I got AC. My complaint is that solution works in 1918ms which is very close to TL and constraints are very tight without any proper reason.

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

    Maybe they were overly paranoid of n2 dp?

    You wrote the blog about li chao tree, so I'm surprised you don't have a fast CHT implementation :O

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

      I used implementation from my article, it didn't turn out to be very fast, haha.

      Although I used offline version because thought that Li Chao would use memory.

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

    why overflow? isn't the answer always within long long?
    Update: sorry my implementation is probably different from yours.

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

can someone please share their approach to Div2 D ?

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

    DFS, where each node returns the best path in its subtree that ends at this node. Do this while maximizing the answer among the sum of best 2 children of each node with each other, i.e sum the paths returned from the best 2 children and check if they're better than your answer, they resemble the best path passing through this node, also try taking the best path alone, or just the gas of the current node.

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

    dp on tree.

    first, make the tree rooted. dp[u] = maximum gasoline that can be starting from u and ending to node that have u as its ancestor

    for each node, you can find the maximum of the path passing that node by finding the best two children of that node.

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

      what about the constraint on the minimum amount of gas to cross a path?

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

        nah. doesn't need it. they ask you to maximize the minimum gasoline that can be achieved. not the minimum gasoline spent

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

    Centroid decomposition — force the centroid to have a depth of 0, and find depths of subtree accordingly (add weights, subtract lengths of edges).

    Then add in the w[centroid] when considering the answer.

    Unfortunately,

    I put for (auto e : arr) ARR.insert(e); in the wrong layer of looping causing it to do nothing at all! :(

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

    First notice that an edge and a vertex only comes into the picture along with some other vertex when w(vertex)-w(edge) is positive. In this case it will only increase the gasoline upon reaching some vertex. You need to maximize this.

    The way to do it is calculate (in) value for the vertex which denotes answer if you start with this vertex and travel down...Also calculate (out) for each vertex which denotes max answer you can get starting from the node and not traversing the children of it.

    As wewark says keep 2 best children for it to do it in linear time.

    It is the in-out dp trick. Sad it is for I wasn't able to complete its implementation on time.

    Below is the link to its video tutorial. https://www.youtube.com/watch?v=Xng1Od_v6Ug

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

Last week I was mocking .ckodser. for using "ll" no matter what , even as a loop variable. And today I got two wrong answers in the whole contest , both due to the above issue :|. Guess that's the universe slapping in my face ... :O

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

I don't want to make int128 library only for codeforces(why codeforces working on 32bit????)

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

Can we solve DIV2 D using in-out dp ? for every node , taking max value in inside subtree and max from outside subtree , and now curnodeval+max(inside_value,outside_value) ! we will check this for every node and taking out max of all ! P.S : value in a subtree is sum of values of nodes — sum of values of edges !

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

Fast judging, pretty good.

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

And btw, apart from C and F being good problems which I mentioned before, there were a few annoying things. I see that TLE in C was pretty tight (I currently see 1 AC and 2 TLEs on 100/112 tests among my friends) and it seems TL in E pretty strict as well and in E we needed to check whether ab>=cd where these products could be as large as 1027. Why weren't the constraints lower so that it could fit in LL? It took me something like 5-10 minutes to solve this problem and code it apart from doing this check which took me 26 minutes xDDD. CF doesn't have int128 (ノಠ益ಠ)ノ彡┻━┻, long doubles are shaky and all other ways are troublesome and require a lot of care.

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

    Wait where did E require that check? I didn't have it and got AC

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

      Depends on implementation, I guess. Check is needed if you reduce CHT to convex hull of points.

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

      I just copied not mine code for convex hull (which is great btw) and it had such check. Many people here talk about it (yosupo and comfi) and Radewoosh had this problem as well, so this problem definitely exists and I'm not the only one. Maybe you used some other idea.

      In my code 46871036 that is line "return (x->b — y->b) * (z->m — y->m) >= (y->b — z->b) * (y->m — x->m);" which is commented and replaced with ugly functions Wrap and Gr

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

        I got AC using long double to do that 10^27 multiplication part (in practice submission). Maybe weak testcases?

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

          I am not surprised by fact that it gets AC, but it may be risky. It may be hard to create testcases against this. You can't be sure.

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

        You can use __float128 instead of __int128, as it has enough bits of mantissa precision to store integer numbers of order  ≈ 1033 exactly and exists on the Codeforces.

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

    Also I dont see any point in characters in B being 'a', 'b' instead of 'a' to 'z'.

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

      The characters being 'a', 'b' allows for a pretty easy solution that is barely programming. You can consider s and t as binary strings and iterate through their prefixes. While the prefix difference is less than k, you add it to the sum and when it grows larger you add k instead.

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

        Of course, this solution could be adapted to a larger alphabet, but it only serves to make the implementation difficult.

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

          In my solution it would only the matter of replacing 2 with 26 and b with z...

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

        OMG YOUR CODE IS INGENIOUS

        But in your description you missed most important part — why you can don't care about overflows here which is why it is so clean and ingenious.

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

          Thanks :D

          Still managed to fakesolve Div2B, though. Yes, to avoid overflows you just notice that k is not large enough to overflow and that you stop updating the difference after a certain point.

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

            I don't understand how does your program survives a possible case where both strings are bbbbbb... and bbbbb.. Your variables a and b will for sure overflow because the difference will be 0 at all times. Weird. Maybe weak tests, or maybe I'm missing out on some bit logic.

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

              Notice that even if the variables overflow, they will do so to the same value.

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

              Couple this with the fact that the variables will only overflow when they are equal, and notice that this means that even cases such as

              bbbbbbb...ba bbbbbbb...bb

              will work due to the difference remaining accurate through overflow.

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

              Another curiosity is that dues to multiplying by two being equivalent to a left-shift it "overflows" to  - 1 when it multiplies to the sign bit and after that point it will not overflow again if the strings of b-s continues due to 2 * ( - 1) + 1 =  - 1.

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

How about Div 2 C?

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

    it's hard for me to explain but I can give the hint to forget about all characters that are not 'a' and 'b', and count number of adjacent 'a's and store it in vector. Then find formula for it. Check my submission for maybe more info about formula.

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

    It's simple combinatorics.

    You need to have atleast a 'b' if you consider more than 1 'a's of the sequence. So, what you can do is count 'a's in each segments seperated by a 'b'. Now, suppose for some segment you have x a's. So, you have x+1 choices(select 0, 1, ...x) to select 'a'. Multiply each segment's (x+1) values. Now, you need to subtract 1 as you need to have a subsequence of length atleast 1.

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

    hey i used a dp approach: consider there are x continuous segments of b's in the string which divide the string in (x+1) parts. Let the no of a's in the (x+1) segments be a1,a2,......a(x+1). Then DP[i]=(a[i]+a[i]*DP[i-1]+DP[i-1])%Mod, DP[i]->no of ways considering first i 'a' segments. Base case: DP[1]=a1 and final answer would be DP[x+1]. Also you would need to check separately when the string would contain no 'a' or no 'b'.

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

Div1A, statement "Nut can't choose a path, which consists of roads, where he runs out of gasoline" does not affect the answer? Interesting.

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

    That's pretty easy to see since if you would have negative amount of gasoline after some prefix, you can just disregard this prefix and get strictly better answer.

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

Cheaters 46874750 46876196 ,I suppose that you will not do anything as always MikeMirzayanov ?

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

KAN MikeMirzayanov cookiedoth

You better have developed plagiarism checker. Check some codes and they are almost the same. No doubts most of them are copied from sites like "ideone". For example, two same submissions:

https://codeforces.com/contest/1084/submission/46875019

https://codeforces.com/contest/1084/submission/46876091

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

Huh, it took me approximately 5 years and 5 months (since the first c++ code), but this moment is worth it, even if it's just a moment :P

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

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

2 sysfails today :( but at least i got a christmas candy cane :)

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

Congratulations Radewoosh.Number 1 on both rating and contribution.

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

This Code of Problem B: while (sum < s){ sum += n; num[0]--; } I check is case: 1 999999999 1000000000 It's running for 2000ms on my computer,But gets an Accept in system test....

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

Can anyone provide a proof why this 2B passes??
Tried around 10-15 tc but It didn't fail.

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

E was solvable in 10-15lines with just sorting+deque without cht.46878899

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

Thank you, Good contest, Great problems, Nice pretests.

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

can anyone explain me div 2 c with example

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

    Ways to choose some subsequence(not necessarily continues) of ‘a’ that between 2 element of this subsequnce there exist a ‘b’

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

      can u explain with an example by telling subsequence ?

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

        aaaaggbbaaadddaa The subsequences of length 1 are every a = 9 The subsequences of length 2 are pair of 4 first ‘a’s and 5 other ‘a’s becuase there has to be a ‘b’ between every two ‘a’s that we choose so = 4 * 5 = 20

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

          Solution: all you have to do is have the number of ways you can do this before the last b then for every a till next b answer is that sum + 1

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

          in aaabbaaaabbbaa the answer should be 9+3*4+3*2+4*2?

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

      But Pi and Pi+1 are subsequences, so what does Pi < j < Pi+1 means?

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

        No pi isnt the subsequence its index’s pf subsequence

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

          Thank you, but why do you think so? I see this: The Nut is a curious guy, so he wants to find the number of strictly increasing sequences p1,p2,…,pk, such that: 1... 2...

          Please, get me right — I'm not trying to be a jerk, and prove that I'm right and you are wrong — I'm just looking for clues, to understand it right next time.

          I mean non of n-a-sequences ("aa...aa" n times) is strictly increasing and k is the number of this sequences, not number of "a"s...

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

Div2E states:

Recently, the Fair Nut has written k strings of length n, consisting of letters "a" and "b". He calculated c — the number of strings that are prefixes of at least one of the written strings.

So he calculates all the possible strings that would be prefixes? Not only those k of length n, that where written?

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

Can someone give me some links where I can learn about convex hull opt? The old ones that are on codeforces blog's does not work.

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

.

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

Hi I got accepted in problem B(div.2); but there's a test case that is not in your tests, but I will get TLE on it. The test case is this: 1000 10^12-1 10^9 10^9 10^9 .... please add this TC and rejudge

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

Guys, what is needed to solve Div2 Problem D? I know DFS but I am not able to understand the approach to be used for this problem. For me, the editorial above is providing no clue/ help. Can someone help me with some explanation on this problem?

Thank you.

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

    Think of it like this : You need to search for a path. So, for each node, you consider its subtree. Now 2 cases : a) You need to find the best one-ending path. That is, find the best path that starts somewhere in the subtree and ends in this particular node. This is the path that can be extended by the ancestor node. So, you need to store it in the DP state. b) You need to find the best possible path in this subtree. Also, it should pass through this particular node. The path in a) is one of them. The others can be found if we combine the best paths from the 2 of the children subtrees. Which we can do by sorting the children DP states.

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

how is Radewoosh pronounced?

is it like Raydwoosh or Ra-De-woosh?

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

.