cookiedoth's blog

By cookiedoth, history, 6 weeks ago, translation, In English,

Hi!

I'm glad to invite you to Codeforces Round #526, which will be held on Dec/10/2018 19:35 (Moscow time). The round will be rated for both divisions.

Problems were prepared by me, Dimon, maxim.shuklin, egor.lifar.

Thanks to ismagilov.code, Kuyan, 300iq, alexey_kuldoshin, Jatana for testing, arsijo and gritukan for helping us and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given 6 problems in each division and 2 hours to solve them.

UPD:

The scoring distribution in Div. 1: 500-1000-1500-2000-2000-2500

The scoring distribution in Div. 2: 500-1000-1500-1750-2250-2750

UPD: Congratulations to winners!

Div. 1:

  1. Radewoosh

  2. CongLingDanPaiShang3k5

  3. Endagorion

  4. ksun48

  5. Um_nik

Div. 2:

  1. Muffinhead

  2. usureluflorianr

  3. arjunsanjeev7

  4. IAmNotGood

  5. tyler

UPD: Editorial

 
 
 
 
  • Vote: I like it  
  • +170
  • Vote: I do not like it  

»
6 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

I think the date is wrong

»
6 weeks ago, # |
Rev. 3   Vote: I like it +164 Vote: I do not like it

I am confused.

»
6 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

Aww, new codeforces round, new chance to fall!

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Time is always a severe problem for us Chinese fanatic.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      Sounds like u have long awaited for that aha

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

“Is this rated?” hURr DuRR

»
6 weeks ago, # |
  Vote: I like it -38 Vote: I do not like it

will this rate my rating

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

2300

»
6 weeks ago, # |
Rev. 4   Vote: I like it -14 Vote: I do not like it

...

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Again a new chance to restart coding...

»
6 weeks ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

does cf stops producing 5 problem Div2.s ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish for 2400.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

how many problems are shared between the divisions ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes I wont lose rating

»
6 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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'

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How can i register now?

»
6 weeks ago, # |
  Vote: I like it -29 Vote: I do not like it
The comment removed because of Codeforces rules violation
»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

RIP problem statements

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +35 Vote: I do not like it

    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 :(

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Nice.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +16 Vote: I do not like it

      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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 3   Vote: I like it +8 Vote: I do not like it

        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 :(

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve DIV1B?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

»
6 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

can someone explain div 2 C problem and its solution?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why [0], [1] are valid?

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                Rev. 3   Vote: I like it 0 Vote: I do not like it

                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 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  :( not yet.

                  if the given string be aaa, then second condition can never be met by any sequence. Then?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, but then all the sequences will be of the same size, to meet both the conditions.

                  So, required sequences are: [0], [1], [2].

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  But this is not mentioned in no where in the problem :(.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  It's called vacuous truth. https://en.m.wikipedia.org/wiki/Vacuous_truth

                  If the sequence is of length 1, then there's nothing to check regarding the second condition. So you can consider that it meets the requirement.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks djm03178

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Yes, both the condition should be met at the same time.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Please help me. I'm yet to understand the problem statement. 1. which consists of only a's 2. two a's should have at least one 'b' between them in the original string.

      how to relate this two points with the given condition in problem statement.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Credit to matcoder

        It doesn't depend at all if there exists any letter other than a or b in the given string. You can for sure ignore those letters, so the editorial says to erase them. Now, what you have is a string consisting only of a and b's. Also two consecutive b's can be merged as one. So your final string will look something like (a...a)b(a...a)b(a...)...

        You can now consider this problem as sum of all possible product of subsets of a given set, where each element in the set is the number of a's delimited by b.

        For example: In the string "aaabaabaaab", set formed will be {3,2,3,0} (0 can be ignored). Now if you have a set {a1,a2,...,aN}, then sum of all possible products of this set is equal to (1+a1)*(1+a2)*...*(1+aN)-1.

        Proof:

        Write the required answer as follows:

        S = Sum of products of subset with (size=1)+(size=2)+...(size=N)

        S = (a1+a2+...aN)+(a1.a2+a1.a3......+aN-1.aN)+...+(a1.a2.....aN)

        After factorization,

        S = (1+a1)(1+a2)...(1+aN)-1

        For more help check this.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I read this one before. But, what if the given sequence is "aaa"? No 'b' is present here.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            For this part append one extra b at the end, and count the total number of a's, the answer is (no of a's +1 ) simply, which is 4 for this test case(aaa).

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How did you get — which consists of only a's — this point from the problem's description? this is the thing where I felt short to make up.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lol. I solved it in this way, though couldn't debug it within time.
      AC submission

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      But how to ensure that both the paths do not come from the same child?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should keep maximum and second maximum pathes.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What? How?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    can you please elaborate why that condition is useless?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it +11 Vote: I do not like it

      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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C without seg tree??

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Div2D test 7 anyone please?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Check this case:

    6
    100 100 5 5 5 5
    1 3 0
    2 3 0
    3 4 0
    4 5 0
    4 6 0
    

    The right answer here is 205.

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

early system testing nice ^^

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For div1E, is it enough to use long double?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

»
6 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

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?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it -33 Vote: I do not like it

        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 :(((

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sorry wrong reply, i wanted to replay another comment.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      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
  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

can someone please share their approach to Div2 D ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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! :(

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
6 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

Last week I was mocking sina_pakseresht 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

»
6 weeks ago, # |
  Vote: I like it +78 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 !

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Fast judging, pretty good.

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I didn't write this code myself but 46872251 uses the CHT and doesn't seem to produce overflows. Source: kactl

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it +44 Vote: I do not like it

        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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
            Rev. 2   Vote: I like it +8 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
              Rev. 2   Vote: I like it +5 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

How about Div 2 C?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I also used the same approach as yours. Some coders used dp. I didn't get that. I also got AC though

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      In Div2 C : In first example test case , we are not taking a sequence [1,4,5].. can you please tell me why ??

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

»
6 weeks ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

KAN MikeMirzayanov savkinsd2089

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

»
6 weeks ago, # |
  Vote: I like it +459 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Seeing your performance in recent contests I don't think it's going to be just a moment, congratulations!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Yeah I think tourist has a script that registers him automatically to the next contest if he is not in the first place anymore,..

»
6 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

»
6 weeks ago, # |
Rev. 3   Vote: I like it +199 Vote: I do not like it

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it +86 Vote: I do not like it

Congratulations Radewoosh.Number 1 on both rating and contribution.

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ((i-x)+(i-1)+(x-1))*2. So x cancels out. Similarly when x> i.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      For x>i, i cancels out. So this proof is wrong.

      P.S. — This soln is correct because x=1 is among optimal solutions.

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone explain me div 2 c with example

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u explain with an example by telling subsequence ?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ps : I am weak in combinatorics :(

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Its 9 + 3 * 4 + 4 * 2 + 3 * 2 + 3 * 4 * 2

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              are u sure ?

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Lets count Length of 1 = 9 Length of 2 there could be from first pack of a and second then second and third and first and third Length of 3 is choosing one from each pack

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No pi isnt the subsequence its index’s pf subsequence

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 2   Vote: I like it +4 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            K is the length of sequence it can be from 1 to n

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

hell o what this is
??
rate?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how is Radewoosh pronounced?

is it like Raydwoosh or Ra-De-woosh?