When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Arpa's blog

By Arpa, history, 7 years ago, In English

Hello again, and hope you have been Joon-Joon of the round :P

I’m preparing harder version of some of the problems (Div.2 A, B, and Div.1 A, D) and I’ll put them on some gym, so if you are interested in harder version of problems please wait for about one week.

You can see and download the problem archives (pretests, tests, statements, validator, checker, solutions) here. You can see solutions in solutions folder, note that there are several codes there, there is a descriptor for each code (.desc) that shows the verdict of that code.

Preparation details:

On 25 May Batman came up with problem Div.1 D and other problems authored inchmeal.

9/25/16: Proposal sent to Gleb.

11/12/16: Answer from Gleb: Your proposal has been redirected to Nikolay KAN.

11/15/16: Nikolay has replied, and commented about problems, saying some problems are easy, some are hard, some are ok.

I changed some of the problems, change the constraints for some others and we talked about solutions through email.

11/17/16: We switched to Telegram.

Creating tests, writing generators, writing statements, etc started in the Polygon.

12/06/16: Round #383 hold.

gKseni told me how you want to get your money and I had no idea.

gKseni told me that it is possible to transfer my money and finally May 4, 2017, I received my money through Okpay.

I have another problem set to prepare another div.1 + div.2 round, but I haven’t enough time now :(.

Paintings in problems were suggested by me, painted by Batman and edited by me. Problem stories and this editorial were suggested and written by me. KAN helped us preparing the round very much, we are thankful to him. This table for each person and for each problem shows the number of the committed changes (in polygon) he has made in preparing the problem (it is good for showing how much someone was involved in preparing).

I used Google Docs for writing everything.

User\Problem Div.2 A Div.2 BDiv.1 ADiv.1 BDiv.1 CDiv.1 DDiv.1 ETotal
Me891616101937114
Batman321070114
KAN and testers 3359771361

Here is another table, showing the number of expected accepts (in my opinion, before the contest) and the number of accepts (after system testing).

Div.2 A Div.2 BDiv.2 CDiv.2 DDiv.2 EDiv.1 ADiv.1 BDiv.1 CDiv.1 DDiv.1 E
Expected 6000450020005001506004003005010
Accepted 3966172311316841047947450151

Hints

Div.2 A: Write the last digit of 1378n for several small values.

Div.2 B : Note that if then .

Div.1 A: If the answer exists, it depends on the lengths of cycles in the functional graph.

Div.1 B: It’s similar to a simple knapsack problem, think on O(n·W) solution using dynamic programming.

Div.1 C: Build a graph and put edges between each 2 * i, 2 * i + 1 and each BF and GF.

Div.1 D: Keep a mask for each vertex, i-th bit of maskv is true if the number of edges in the path from root to v such that letter i is written on them is odd. Now if number of bits in is 0 or 1, path between v and u is Dokhtar-kosh.

Div.1 E: Sort all of the options, then the problem becomes easier, solve the new problem with sqrt decomposition.

Details

Div.2 A

Idea, authoring, solution by Batman, preparation by Batman and me.

My and Batman ’s birth year in Solar Hijri calendar is 1378.

Div.2 B

Idea, authoring, solution by Batman, preparation by Batman and me.

Div.1 A

Idea, authoring, solution, preparation by me.

Attractive boys/girls are called Joon-Joon in Persian. Owf is a sound used when we (Persian) are interested in something, especially when we see something attractive, such as our crush :P

Div.1 B:

Idea, authoring, solution, preparation by me.

The problem authored by me 2 days before the contest :D (#FastAsFerrari). Attractive girls are called (some word similar to) “Hos” in Persian. It’s a good place to thank amsen, whose name (Hir) gave me this idea (to use word “Hos” instead of “attractive girl”).

Div.1 C :

Idea, authoring, solution by Batman, preparation by Batman and me.

“Kooft” is something make people die. “Zahre-mar” meaning is “Venom of Snake”.

Div.1 D:

Idea by Batman, authoring, solution, preparation by me.

“Dokhtar-kosh” is an adjective, used when something is very very attractive.

Div.1 E:

Idea, authoring, solution, preparation by me.

Solutions

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

I’d like to finish the editorial with the below poem by Hafez:


از صدای سخن عشق ندیدم خوش‌تر یادگاری که در این گنبد دوار بماند

Translation: I have never seen anything that sounds better than love, it’s the relic which will remain in the universe.

Good luck and see you soon in “Round #383 hard version” ;)

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Nice Editorials

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

Arpa Best editorial I have ever seen till now in Codeforces :D

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

In Div2C why if there is a cycle of even length we add len / 2 to S?

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

    Because if the cycle is even you can go until the middle and return (from x to y and from y to x). Also you can go from x to x, but this option don't minimize the value of T. And when the cycle is odd you must take all the cycle (sorry for my poor English)

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

      That makes sense. Thank you very much!

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

      Got your Point ... I don't understand Why the answer is the LCM of all the length ?

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

        suppose that you have 2 cycles with lengths 20 and 15. Now you have T1 = 10 and T2=15. You need to find a T, such T is multiple of T1 and T2 (this guarantees that you can go from any x to y, and go from any y to x, possibly more than once). The problem says "find smallest T". that is the LCM. (sorry for my poor English)

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

      Could someone please explain with an example as to why Len/2 operation is being done

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

        Because if a cycle has even length, in order for the condition to be fulfilled, it is not necessary that the line of calls starts and ends in the same person. For example, if 1 calls 2 and 2 calls 1, t=1, because if the cycle starts in 1 it will end in 2, and if it starts in 2, it will end in 1.

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

Good contest... but, can anyone explain better the solution for Div1C problem? I can't understand the editorial... Thanks

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

    Put edges between pairs a_i,b_i and also between 1-2,3-4,5-6,...,(2n-1)-(2n).

    In this graph we don't have any odd cycle(prove it yourself) and if we color the vertices with colors 1 and 2 it could be answer of the problem, cause a_i and b_i have different colors and also for each 3 consecutive people there is at least one edge between two of them and they have different colors...

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

      Сan you explain, why problem has no solution, if there is no solution in this graph, please?

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

        You can always color the vertices by two colors in that graph so the main problem has always a solution too...

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

        Because it can be proved that this graph always has a solution, also a solution to the main problem, we don't have to care that the problem has no solution.

        Proof is very simple. Bipartite graphs always have a 2-vertex-coloring solution!

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

      We can have a different coloring if we put edges between 2-3,3-4,...,(2n-1)-(2n),(2n)-1

      Shouldn't we check for both the graphs? Thanks

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

        You could always check for any graph that is bupartise, as there is always a solution from these graphs you could consider any of them.

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

The style of your editorial is great.

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

I used a different solution to solve 741E.

For K<=50 I created range trees (memory is O(N*50), build is O(N*50), total query is O(Q*50*logN)).

For K>50, N/K <= 2000 so we can iterate through each block of K in time, querying a sparse table over the whole array (memory is O(NlogN), build is O(NlogN), total query is O(Q*2000)).

Thus we have O(Q*(2000 + 50*logN)) which is runs pretty fast.

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

Very nice idea to add hints to the editorial.

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

anyone else solved div2 A using bigmod? :v

»
7 years ago, # |
  Vote: I like it -17 Vote: I do not like it

I will get some money for using my name or its idea :| .

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

    You are getting some minuses instead :P

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

This is maybe the best editorial I've seen. Though, I don't see why you use religion quotes on this website.

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

    Thanks. Why not? My purpose is to show other people our literature.

    EDIT I had misunderstand meaning of word "religion", I thought your mean is the poems in the post.

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

      You start some of your blogs with "in the name of God". It looks like it isn't about showing the literature.

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

        Why not? Anyone has some beliefs, and I believe in "Anything which doesn't starts with "In the name of God" is incomplete"

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

          Let's move to private messages, shall we?

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

            I'm very sorry for doing this. I'll remove "In the name of God" from my blogs now.

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

              But why? I thought it was good :)

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

              would you mind telling us why?

              maybe i remove it from my comment...

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

                As Errichto said, "neutral websites like CF should avoid discussions about religion because it's unrelated to competitive programming and can only divide people".

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

                  If something as generic as "In the name of god" can offend people and cause hate, then maybe they should see a psychiatrist.

                  You did write some heavily religious stuff. I'm sure Errichto referred to those.

                  Btw, I'm not very religious myself(karma is my religion), but I like seeing others following their faiths. I believe every belief deserves to be respected.

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

                  پس شما باید قبول کنی که تو کدفرسس کار ناقص انجام میدی

                  در ضمن ما با به نام خدا گفتن میگیم خدایا حتی به موقع کد زدن هم به فکرت هستم

                  مورد سوم کدی که میزنیم از خداست و به همراه اعتقاد با خداست و برای خداست

                  پس ما اینجا فقط به نام خدا نمیگیم بلکه تمام اعتقادات و اهدافمون رو داریم میگیم

                  چطور میشه که داستان های کودکانه گفتن منافاتی با مسابقه ندارند ولی به نام خدا گفتن منافات داره

                  اگر امروز این رو از دستت بگیرن فردا تمام اعتقاداتت رو از دستت میگیرن

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

                  به خاطر لحنم ازت معذرت میخوام

                  امیدوارم بهترین تصمیم رو بگیری

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

                  As an atheist I don't mind people including their beliefs in their blogs or lectures, just don't make it too long.

                  Different from Errichto, though I find the poem parts more disturbing (just imagine if a Christian lecturer starts every lecture with the words from the Holy Bible ), I feel like it's a bit nazi to forcing someone else to remove one short sentence "in the name of god".

                  Ehh, I guess it's 2016 after all.

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

            I think the word "God" should be removed from all posts in CF if there any post contains "God".

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

          in the name of god

          congratulations for your blog.

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

Many thanks for the wonderful editorials! I can tell how much efforts you put into this. Kudos guys!

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

Woah! Nice job!

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

I did Div2A simply with pow(1378,n,10) in python

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

Two Hoses x and y are in the same friendship group if and only if there is a sequence of Hoses a1, a2, ..., ak such that ai and ai + 1 are friends for each 1 ≤ i < k, and a1 = x and ak = y.

what does this mean?

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

in Div1-A why i have to take the LCM & why i am taking the (len / 2) when it is even ??

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

    Consider two cycles, for one value of t is 3 and for other value of t is 2 then, the minimum number that satisfies condition of the problem is lcm of both. And for question of taking len/2, if you read last sample testcase in problem you'll understand it

  • »
    »
    7 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    So to answer your second question see this comment. It helped me out. For your first question lets consider two pairs of people: a and b, c and d. Let's say that to go from a to b you need a cycle of length 3 (a -> u -> v -> a) and to go from b to c you need a cycle of length 4 (b -> k -> l -> m -> b). If t was 4 then you could go from b to c but you would have also followed path a -> u -> v -> a -> u (which is not a cycle). Now you need minimum t such as after t moves you can complete some number of cycles. This is the LCM over all cycle lengths. For this example answer would be 12, doing 4 full cycles from a to b and 3 full cycles from b to c.

    Hope I helped!

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

mate quick editorials , thanks for that :)

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

in 741C, I believe you make an edge between 2i and 2i+1 for the constraint => in every 3 consecutive Among any three guests sitting on consecutive chairs, there was two of them who had different type of food.. But the constraint has more cases than 2i and 2i+1 are opposite. Should not there be a provision to check those cases also?

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

    But look that graph, if you try to bi-color it, you always will be able to bi-color it and for every 3 consecutive nodes its impossible that all 3 have the same color. Think, you have a-b and c, as a-b must have different color (cause you have an edge betwen them) you are respecting the rule. That's why you don't need other provision.

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

      Yeah, we can bicolor following 2i and 2i+1. But there are other ways we can bicolor it without following 2i and 2i+1. I am asking, to either prove that we cant, or that it is not required

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

        There are many solutions. So, there exist solutions in which 2*i and 2*i+1 might have same color for some i. But, we need to find anyone solution. The above construction gives one such solution.

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

          But, if there is no solution for 2i and 2i+1, there may be other solutions which we ignore

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

            There always exist solution for 2*i and 2*i+1. You need to give anyone solution.

            Let me explain in other scenario. Question — "print any prime below 10^18". Answer — do you find all primes below 10^18, consider them and print one prime? No, you give anyone prime which works.
            Also, now suppose you have figured out a way(given a magic function) which gives twin primes. You call this function, and give one of its values as your solution. One can argue, if there exist no twin primes below 10^18, then you are doomed. But we know that this magic function will work correctly. In other words, it will give one possible solution.

            The above construction always give one such solution out of all possible solutions S.

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

              Okay, actually my problem was that if there exists no solution. Then there might be more conditions which we could have checked. That is, if there graph constructed contains an odd cycle. But yeah, after you pointed it out,I saw an odd cycle is not possible. It was a nice solution, I hope I can come up with a solution like this some day.

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

    I have the same doubt. Arpa please elaborate why your method is correct.

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

WOW , The best editorial until now
Good job bro :)

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

God bless you my brother :)

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

In Div2-D how can we consider only a memeber of group in our DP?

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

    During DFS when you try to label each "vertices" (hos) to a connected components, you should also list down which vertices for each connected component contains

    Then during the DP, iterate through all the list of vertices and try to take one vertices (we know our weight and beauty value, just like knapsack problem)

    Hope it helps

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

      fonmagnus

      Can you please tell this in a little detail. I tried understanding accepted solutions but wasn't able to understand.

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it +4 Vote: I do not like it

        For each vertex, we can find out in which group that vertex belongs to (we can simply using DFS for labelling connected components). We also precompute the total of all weight and beauty im this group and store it in an array weightSum[k] and beautySum[k]

        Let's say after the DFS we have the group of friends in group A that contains (A1, A2, ..., Ak), these vertices are belong to group A, so we list down these vertices in a vector that represents the list of vertices for each group.

        After doing so, we can run a DP with two states : let's say DP(pos,w) means we are currently evaluate the group[pos] with a remaining weight of at most w

        In our DP, the best solution can exists in any of these 3 alternatives :

        1. Not take that group means we evaluate the next group DP(pos+1,w)

        2. Take all of those group together DP(pos+1,w-weightSum[pos])+beautySum[pos] means we evaluate the next group with a new remaining weight and added with current group beauty (make sure our current weight is not less than this group weight).

        3. Take only one of the hos in this group that produces the best solution. We dont know which hos is the best solution, so we iterate through each i-th hos in this group (by listing down the vertices list in a vector I've mentioned earlier, we simply can iterate through all of the list) this alternatives is DP(pos+1,w-weight[i])+beauty[i] where weight[i] and beauty[i] each represents the weight and beauty for the i-th hos in our current group.

        Then we just compare which one of those alternatives produces the best solution :)

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

          I have a question,possibly a "dummy" one.

          Is it possible that when we check for a whole group(the total amount of weight and beauty and if we manage to fit it inside our certain weight that somewhere (one) inside that group is better solution then the whole group? Im asking this because i failed test because of this and i couldnt understand why...After i found that a group can fit inside my DP[X][J] i never checked for 1 member inside that group and i just skipped it..It failed a test and after removing the else contidtion it passed...

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

            Yes. Suppose that you have 7 hoses, such that 1,2,3,4 are friends and 5,6,7 are friends. Hoses in the first group have beauty 1, except for the hose 1, who has beauty 5. Each members} of the second group have beauty 2. All of the hoses weight 1, and the scenario can stand weight 4. Your algorithm will give as an answer 8 (take the whole first group), while the optimal answer is to take hose 1 and the second group.

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

Nice editorial. Enjoyed contest. Congrats to winners :) I could do Div2A in 30 seconds, but couldn't do other ones. Hope to see you on next contests.

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

I don't understand 741B (the dp parts). Can someone please explain the steps in a better order or maybe link a good solution?

edit: got it :)

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

I really respect your effort , BUT there is so much stuff in this tutorial that no body cares about :)

I am not trying to be offensive , Big thanks for your round and good tutorial :)

Anyway has anybody noticed that RIP (English and Well formed statements) in Div1 A , B

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

    I find those unusual parts quite interesting actually.

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

      The hints part is really cool and should exist in every editorial.

      Well the intro , and preparation details , and that details section :D I don't know what's the point !

      This guy is really proud of making this round (and he must be). But I think there must be something wrong , this is the round 383 and nobody ever wrote any of that stuff. you may find one part of them in few rounds. But this is kind of too much :D

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

for DIV2 — C is there a better solution using DP ?

http://codeforces.com/contest/742/submission/22769871

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

    brother it got failed at test 61 , before posting here please check at least once .

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

      brother .. i know that my answer fails at test 61

      i'm asking for a hint to make my solution accepted using DP approach

      thanks

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

One of the best written editorial on Codeforces

»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

can someone tell me where is my code is wrong thanx in advance http://codeforces.com/contest/742/submission/22771264

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

    please someone reply me

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

      in your code :

      ll lets_do(int ind, int wt) {

      if (ind > n)  return 0;
      
      if (dp[ind][wt])  return dp[ind][wt];
      

      .....

      I think it should be :

      if (ind > gp )  return 0;
      

      right ??

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

Very cool editorial and problem ideas! Thanks Arpa for the great Round

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

One of the best editorials I've ever seen! And this hint section is the best part!

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

Best editorial I've ever seen. Great job!

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

Arpa and Batman,

I found your mistake in task div2.B.

In statements was wrote 1 ≤ n ≤ 10^5. N could be 1. We need find pair, but if n == 1 answer will be 0.

But, you haven't any tests n == 1.

For example I thought that

My mistake, but got accepted

My solution is wrong but it passed.

You was should add test when n = 1.

This my my wrong , but accepted solution :P :
22750839

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

    We didn't have test with n=73901 too...Sorry for this... :/

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

      Okay, maybe it isn't mistake, but I just wanted to say that you should note this for future...

      but still thanks for round.

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

      Min- and max-tests should always be included in the final tests. It often allows to fail some more solutions, while there are no drawbacks.

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

    Excuse me, I accept my mistake.

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

In Div 1 C, "This graph doesn’t have cycles with odd length". Doesn't this test case contradict?

2

1 3

2 4

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

    The graph will have edges: 1-3 2-4 1-2 3-4

    Does it have cycles with odd length?

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

      Oh! I misunderstood the editorial. Thanks!

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

    Actually it does not.  Maybe you forget to connect vertice 2*n and vertice 1.

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

I keep getting wrong answer in testcase 4 for 741b , why is the answer not 1710057 but 1495706?? can somebody explain? thx

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

    try this test case: 10 5 100

    64 90 3 94 96 97 52 54 82 31

    796554 444893 214351 43810 684158 555762 686198 339093 383018 699152

    6 8

    8 3

    3 9

    2 3

    10 3

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

This is the fastest tutorial in CF I'v seen.Thank you Arpa.

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

Best Editorial till date seen by me on codeforces. Thanks! Arpa

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

IN div2- C why i need to LCM of all length which are stored in the vector S , according to tutorial . I understand the fact n/2 for even but why need LCM , Can anyone explain ? . Please dont ignore .

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

    If for one cycle, length is 3 but for another length is 2, Then you have to choose a value which satisfies both cycles. You cant choose t=3 because it wouldnt work for 2 cycle and vice-versa.
    Therefore the smallest number to satisfy both of these cycles is the LCM.

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

    Consider for example that we have two cycles :

    of length 8 and 12.

    So the considered value is : 4 and 6 ( because we have even number of nodes in the cycle, we consider n/2 in that case).

    Now the LCM(4,6) = 12.

    You can see that 12 satisfies for both the cycles.

    If the cycle satisfies for t, it should also be satisfied for all multiples of t.

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

    I explain it before here

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

Can you please explain the solution of Div1 D using centroid decomposition?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It says : We're sorry. You can't access this item because it is in violation of our Terms of Service.

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

        It seems you are right and I'm so sorry : (

        Please download the archive here, I'll fix the problem soon.

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

        Finally, I moved files from Google drive to Mega.nz, now you can see the solution you wanted here -> dokhtar-kosh-tree_HellKitsune.cpp.

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

Can anyone further elaborate on Div2 Problem B? I didn't quite understand the solution.

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

    I will explain you my approach:

    1. you need to understand that: a xor b => x ; it means that: a => b xor x;

    2. sort the array

    3. imagine you fix a value a_i (1<=i<=n). you can use binary search in order to find the values such b xor a_i = x. ( Here you need b value. But b = a_i xor x. ).

    4. Now you must realized that you are counting any pair twice. (Because you count a_i with a_j and a_j with a_i) that is why you need to divide the answer by 2.

    5. Don't forget the constraint i<j. You must consider different positions.

    I hope this helps you. (Sorry for my poor English)

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

Best editorial ever. Wish every future codeforces rounds have such editorials. Its always better read hints than to directly read the complete solution. Thanks Arpa

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

I didn't get the solution of Div.2 B for this case.

6 2

1 1 1 3 3 3

so for this answer should be 9 as each of 1 can go with each of three but as per my understanding of the solution of the problem , We will first count the frequency of each input digit so in this case , frequency array will be ....freq[1]=3 , freq[3]=3

Then we will go through the frequency array and we will add corresponding element present at X Xor i place for each i of freq array... So in this case , 2 Xor 1 is 3 so ans=ans+freq[3]=3; then 2 Xor 3 is 1 so ans=ans+freq[1]=6; then we will divide it by 2 as suggested in solution so answer will be 3 but rather it should be 9.

I think I misunderstood the solution, If anyone finds the problem in my understanding then kindly help me out.

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

    the answer is 0 because there is not any pair Ai and Aj (1<=i<j<=n) for which Ai XOR Aj = 1

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

      Ohh ! Sorry I have made a mistake in writing that example consider X as 2 then It will be the question I am looking for! I updated it. Thanks.

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

Can anyone explain in div1 B, what is newDP and oldDP?

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

    Copy the dp array to oldDp before each group, then copy newDp to dp when processing is done.

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

      A small trick in implementing this: instead of dumping away each oldDp array away each time, use it as the NewDp array right after the processing is done.

      for example:

      for i in range(X): j = i%2 dp[j] is currentDp dp[j^1] is newDp

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

        For sure I know, but I had wrote that this way for simplify.

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

          I only meant to hijack to post, in case if zhussupov didn't know how to implement it w/o getting MLE. =P

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

And what is the biggest possible answer for div 2 C and what is the proof for this?

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

    I think the biggest value is when we only have components of prime size.

    Since the maximum number of vertices is 100, we can make a graph with components of size: (3,5,7,11,13,17,19,23)

    and the LCM of everything is 3*5*...*23 == 111546435

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

Thank you for introducing hints in editorials. It's educational and does not need too much additional effort. I hope all authors follow this trend in the following contests.

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

In div1E, i wonder how to solve RMQ part in O(n) for each K?To each K less than n^0.5, i think we should build RMQ arrays.i can query in O(1),but how could i initialize RMQ arrays in O(n) for each K?

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

Can someone please explain Div2.B I am not able to understand it.

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

    Brother , logic behind to solve the problem is that — A^B=C <=>A^C=B <=> B^C=A (you can verify it by taking some examples do this operation on their binary representation) — next task is you need to find the all the tuples such that i<j , Ai^Aj=x or(find all i such that Ai=Aj^x) you just need to find the count of Ai that present in the array before j index . (you can use count sort for this .)

    let me know if you are not able to get it .

    For reference you can check my solution : Solution Link

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

I love this kind of Solution because of the hints.

Normally, Author only writes solutions down, it's not good to build a system of thinking.

I have to give you an up vote. :)

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

Hi Arpa, I could not find your blog for Arpa's Technique. My solution splits queries on K=20 and uses only sparse tables and is faster than your submitted solution on E. I wanted to know how your technique works (your blog is missing?).

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

Still can't understand the Div2 D solution :C Can please someone explain it in detail? I mean I understand the solution of simple knapsack problem. I just don't realize how to use it properly in this problem.

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

    check out my solution. its understandable.

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

    In 0/1 knapsack, the choice of one item is "pick" or "not pick".

    While in this question, there is some constrains that items in same group can only be picked mutual exclusively, or pick them all.

    So it is much alike to 0/1 knapsack, except that now you have to handle it group by group, for each group, you can

    1. Not pick any items in this group at all: dp[group_i][W] = dp[group_i-1][W]
    2. Pick either one item in this group
    3. Pick ALL items in this group

    For case 3, you can pre-compute and make an extra virtual item of sum(weight) and sum(beauty) for each group, so that it can be viewed as part of case 2 as well.

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

I was looking at few solutions for problem 741D like this one http://codeforces.com/contest/741/submission/22787904 but what i am not getting is how we are ensuring that the number of set bits is either 1 or 0 which is the required condition for ensuring whether palindrome word can be formed or not.

ans[i] = max(ans[i], x.second + maxHeight[x.first ^ (1 << b)] — 2 * h[i]);

like here we are seeking solution for subtree rooted at i then the quantity x.first^(1<<b) can have more than one bits set.

Can someone explain me this ?

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

This is my submission for Div.2 problem B.

I got WA on test 11 but it's too big to trace on paper, can anyone provide a smaller test that can hack my solution?

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

    I've explained the reason, read Corner case #2.

    You can download that test here or the full package here. Take a look to my code if needed.

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

i am getting wrong on test case 56 for my solution of DIV2 D .

http://p.ip.fi/b8Ob

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

best editorial

»
3 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Div. 1 D and E are shit problems I must say. Div. 1 C is kinda neat though