cookiedoth's blog

By cookiedoth, history, 2 years ago, translation, In English

Hi!

I'm glad to invite you to Codeforces Round #526, which will be held on 10.12.2018 19:35 (Московское время). The round will be rated for both divisions.

Problems were prepared by me, TheWayISteppedOutTheCar, CTPAX, Egor.Lifar.

Thanks to ismagilov.code, Kuyan, 300iq, alexey_kuldoshin, Jatana for testing, arsijo and vintage_Vlad_Makeev 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. kiwikiwi

  3. Endagorion

  4. ksun48

  5. Um_nik

Div. 2:

  1. Muffinhead

  2. Usu

  3. arjunsanjeev7

  4. IAmNotGood

  5. tyler

UPD: Editorial

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

»
2 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I think the date is wrong

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

I am confused.

»
2 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Aww, new codeforces round, new chance to fall!

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Time is always a severe problem for us Chinese fanatic.

  • »
    »
    2 years 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.

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

      Sounds like u have long awaited for that aha

      • »
        »
        »
        »
        2 years 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.

      • »
        »
        »
        »
        2 years 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号才能打)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

“Is this rated?” hURr DuRR

»
2 years ago, # |
  Vote: I like it -38 Vote: I do not like it

will this rate my rating

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

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

»
2 years ago, # |
  Vote: I like it -34 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

2300

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

...

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

Again a new chance to restart coding...

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

does cf stops producing 5 problem Div2.s ?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish for 2400.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

how many problems are shared between the divisions ?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yes I wont lose rating

»
2 years 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.

  • »
    »
    2 years 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'

  • »
    »
    2 years 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.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How can i register now?

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

RIP problem statements

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    2 years 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 :(

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

      Nice.

    • »
      »
      »
      2 years 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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 years 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 :(

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve DIV1B?

  • »
    »
    2 years 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.

  • »
    »
    2 years 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

»
2 years 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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

can someone explain div 2 C problem and its solution?

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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?

      • »
        »
        »
        »
        2 years 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.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Why [0], [1] are valid?

          • »
            »
            »
            »
            »
            »
            2 years 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'.

            • »
              »
              »
              »
              »
              »
              »
              2 years 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years 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?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years 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].

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks djm03178

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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.

      • »
        »
        »
        »
        2 years 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.

        • »
          »
          »
          »
          »
          2 years 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.

          • »
            »
            »
            »
            »
            »
            2 years 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).

        • »
          »
          »
          »
          »
          2 years 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.

  • »
    »
    2 years 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)

»
2 years 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.

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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

    • »
      »
      »
      2 years 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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should keep maximum and second maximum pathes.

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

    What? How?

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

    can you please elaborate why that condition is useless?

    • »
      »
      »
      2 years 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.

    • »
      »
      »
      2 years 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.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C without seg tree??

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Div2D test 7 anyone please?

  • »
    »
    2 years 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.

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

early system testing nice ^^

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For div1E, is it enough to use long double?

  • »
    »
    2 years 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

    • »
      »
      »
      2 years 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.

»
2 years 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 :(.)

»
2 years 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?

  • »
    »
    2 years 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.

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

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

      • »
        »
        »
        »
        2 years 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 :(((

        • »
          »
          »
          »
          »
          2 years 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.

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Sorry wrong reply, i wanted to replay another comment.

  • »
    »
    2 years 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

    • »
      »
      »
      2 years 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.

      Спойлер

      it wouldn't

  • »
    »
    2 years 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.

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

can someone please share their approach to Div2 D ?

  • »
    »
    2 years 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.

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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?

      • »
        »
        »
        »
        2 years 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

  • »
    »
    2 years 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! :(

  • »
    »
    2 years 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

»
2 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

»
2 years 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????)

»
2 years 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 !

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Fast judging, pretty good.

»
2 years 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.

  • »
    »
    2 years 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

    • »
      »
      »
      2 years 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.

      • »
        »
        »
        »
        2 years 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

    • »
      »
      »
      2 years 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 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

      • »
        »
        »
        »
        2 years 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?

        • »
          »
          »
          »
          »
          2 years 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.

      • »
        »
        »
        »
        2 years 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.

  • »
    »
    2 years 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'.

    • »
      »
      »
      2 years 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.

      • »
        »
        »
        »
        2 years 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.

        • »
          »
          »
          »
          »
          2 years 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...

      • »
        »
        »
        »
        2 years 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.

        • »
          »
          »
          »
          »
          2 years 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.

          • »
            »
            »
            »
            »
            »
            2 years 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.

            • »
              »
              »
              »
              »
              »
              »
              2 years 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.

            • »
              »
              »
              »
              »
              »
              »
              2 years 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.

            • »
              »
              »
              »
              »
              »
              »
              2 years 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.

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

How about Div 2 C?

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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 ??

  • »
    »
    2 years 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'.

»
2 years 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.

  • »
    »
    2 years 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.

»
2 years 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 ?

»
2 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

»
2 years 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

  • »
    »
    2 years 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!

  • »
    »
    2 years 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,..

»
2 years ago, # |
  Vote: I like it -11 Vote: I do not like it

»
2 years 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 :)

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

Congratulations Radewoosh.Number 1 on both rating and contribution.

»
2 years 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....

»
2 years 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.

  • »
    »
    2 years 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.

    • »
      »
      »
      2 years 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.

»
2 years 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

»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

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

can anyone explain me div 2 c with example

  • »
    »
    2 years 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’

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can u explain with an example by telling subsequence ?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ps : I am weak in combinatorics :(

      • »
        »
        »
        »
        2 years 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

        • »
          »
          »
          »
          »
          2 years 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

        • »
          »
          »
          »
          »
          2 years 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?

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

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

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              are u sure ?

              • »
                »
                »
                »
                »
                »
                »
                »
                2 years 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

    • »
      »
      »
      2 years 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?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No pi isnt the subsequence its index’s pf subsequence

        • »
          »
          »
          »
          »
          2 years 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...

          • »
            »
            »
            »
            »
            »
            2 years 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

»
2 years 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?

»
2 years 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.

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

.

»
2 years 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

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

hell o what this is
??
rate?

»
2 years 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.

  • »
    »
    2 years 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.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how is Radewoosh pronounced?

is it like Raydwoosh or Ra-De-woosh?

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

.