Arpa's blog

By Arpa, history, 10 months 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 Sa1378 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 Sa1378 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
Sa1378321070114
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 Sa1378, preparation by Sa1378 and me.

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

Div.2 B

Idea, authoring, solution by Sa1378, preparation by Sa1378 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 Sa1378, preparation by Sa1378 and me.

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

Div.1 D:

Idea by Sa1378, 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  

»
10 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Nice Editorials

»
10 months ago, # |
  Vote: I like it +54 Vote: I do not like it

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

»
10 months 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?

  • »
    »
    10 months 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)

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That makes sense. Thank you very much!

    • »
      »
      »
      10 months 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 ?

      • »
        »
        »
        »
        10 months 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)

    • »
      »
      »
      10 months 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

      • »
        »
        »
        »
        10 months 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.

»
10 months 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

  • »
    »
    10 months 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...

    • »
      »
      »
      10 months 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?

      • »
        »
        »
        »
        10 months 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...

      • »
        »
        »
        »
        10 months 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!

    • »
      »
      »
      10 months 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

      • »
        »
        »
        »
        10 months 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.

»
10 months ago, # |
  Vote: I like it +40 Vote: I do not like it

The style of your editorial is great.

»
10 months 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.

»
10 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Very nice idea to add hints to the editorial.

»
10 months ago, # |
  Vote: I like it +4 Vote: I do not like it

anyone else solved div2 A using bigmod? :v

»
10 months ago, # |
  Vote: I like it -17 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are getting some minuses instead :P

»
10 months 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.

  • »
    »
    10 months 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.

    • »
      »
      »
      10 months 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.

      • »
        »
        »
        »
        10 months 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"

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

          Let's move to private messages, shall we?

          • »
            »
            »
            »
            »
            »
            10 months 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.

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

              But why? I thought it was good :)

            • »
              »
              »
              »
              »
              »
              »
              10 months 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...

              • »
                »
                »
                »
                »
                »
                »
                »
                10 months 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".

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 months 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.

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

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

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

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

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

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

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

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

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

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 months 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.

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

              why are u afraid creations instead of Creator? people will discuss u anyway. do everything for God's satisfaction not for people.

          • »
            »
            »
            »
            »
            »
            10 months 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".

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

          in the name of god

          congratulations for your blog.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Mashallah! very good editorials! go on despite on people who don't like ur actions.

»
10 months 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!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Woah! Nice job!

»
10 months 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

»
10 months 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?

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

    got it.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how ? i missed the point why you should use disjoint set ... can u explain? its a very poor description..

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You don't have to use disjoint set, you can use any method of finding connected components. I used dfs.

»
10 months 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 ??

  • »
    »
    10 months 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

  • »
    »
    10 months 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!

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it's the minimum time so that i can fully complete any cycle , am i right ?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      if i count maximum T it also satisfy all the cycles why not ? here is 4,3 in my vector . If i take 4 as a answer , it satisfy cycle which need 3 (4>3) , also the cycle with 4 (4==4) . So why i need LCM ?

      "it's the minimum time so that i can fully complete any cycle " == taking maximum T also satisfy this , why i need LCM ?

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You have to take exactly t steps. If the cycle has length = 3 and you take 4 steps you don't end up at the starting position.

        Now if you consider the lcm of all the cycles, you will have the number of steps necessary to satisfy all of them (start at x and end at x). In your example (4 and 3), you should take 12 steps in order to end at the starting positions of both cycles.

        Also, note that for even cycles you can go to the middle of it and use the same amount of steps to get back at the origin (you want to know the t necessary to go from x to y and from y to x), in odd cases you have to go through the entire cycle to get to a y that returns to x in the same amount of steps).

        Since you want the minimum t, that implies that you need to divide the even cycles length by 2. (If you had cycles 4 and 3, you should use the lcm of 2 and 3 which is 6)

        Hope that has cleared it up!

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

seriously?

we have two types of food, kooft and zahre-mar!!!! i'm from iran too

i couldn't stop laughing when i read that.

thanks mate, nice editorial. it helps a lot

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

mate quick editorials , thanks for that :)

»
10 months 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?

  • »
    »
    10 months 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.

    • »
      »
      »
      10 months 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

      • »
        »
        »
        »
        10 months 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.

        • »
          »
          »
          »
          »
          10 months 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

          • »
            »
            »
            »
            »
            »
            10 months 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.

            • »
              »
              »
              »
              »
              »
              »
              10 months 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.

  • »
    »
    10 months 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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

God bless you my brother :)

»
10 months 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?

  • »
    »
    10 months 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

    • »
      »
      »
      10 months 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.

      • »
        »
        »
        »
        10 months 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 :)

        • »
          »
          »
          »
          »
          10 months 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...

          • »
            »
            »
            »
            »
            »
            10 months 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.

»
10 months 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.

»
10 months 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 :)

»
10 months 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

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

    I find those unusual parts quite interesting actually.

    • »
      »
      »
      10 months 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

»
10 months 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

  • »
    »
    10 months 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 .

    • »
      »
      »
      10 months 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

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

One of the best written editorial on Codeforces

»
10 months 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

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

    please someone reply me

    • »
      »
      »
      10 months 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 ??

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but here i m working on indexing and if i access an group or a single element from a group than next time i never select any element from that group

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thanx i do it i slightly change my code ind to grp according to ur hint and its accepted thanx a lot

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 months 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!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Best editorial I've ever seen. Great job!

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

Arpa and _-_Sa1378_-_,

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

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

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

    • »
      »
      »
      10 months 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.

    • »
      »
      »
      10 months 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.

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

    Excuse me, I accept my mistake.

»
10 months 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

  • »
    »
    10 months 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?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh! I misunderstood the editorial. Thanks!

  • »
    »
    10 months 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.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I made the same mistake, I think he connects every consecutive vertices.

»
10 months 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

  • »
    »
    10 months 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

»
10 months 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.

»
10 months 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

»
10 months 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 .

  • »
    »
    10 months 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.

  • »
    »
    10 months 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.

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

    I explain it before here

»
10 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    • »
      »
      »
      10 months 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.

      • »
        »
        »
        »
        10 months 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.

      • »
        »
        »
        »
        4 months 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.

»
10 months 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.

  • »
    »
    10 months 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)

»
10 months 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

»
10 months 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.

  • »
    »
    10 months 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

    • »
      »
      »
      10 months 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.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    10 months 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.

    • »
      »
      »
      10 months 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

      • »
        »
        »
        »
        10 months 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.

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
10 months 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?

  • »
    »
    10 months 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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you very much for the contest, and of course for the editorial was very good explained.

»
10 months 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.

»
10 months 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?

»
10 months 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.

  • »
    »
    10 months 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

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bro, I am not able to understand the working of your loop. can you please give a better description of the loop.

»
10 months 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. :)

»
10 months 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?).

»
10 months 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.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check out my solution. its understandable.

  • »
    »
    10 months 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.

»
10 months 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 ?

»
10 months 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?

  • »
    »
    10 months 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.