Jeel_Vaishnav's blog

Codeforces Round #548 (Div. 2)
By Jeel_Vaishnav, history, 6 years ago, In English

Hi everyone!

I would like to invite you to my second Codeforces round, which I have created with my friends Ashishgup and Vivek1998299.

With that said, I bring to your attention our new Codeforces Round 548 (Div. 2) that will take place on Mar/21/2019 18:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would like to thank Ashishgup and Vivek1998299 for their help with preparing problems, vintage_Vlad_Makeev, mohammedehab2002 and Um_nik for testing the problems and cdkrot for coordinating our round. I would also like to thank MikeMirzayanov for the awesome Codeforces and Polygon platforms.

You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.

Good luck! :D

UPD1: Shortly after the contest, we'll be on the community Discord server to discuss the tasks.

UPD2: Score distribution is — 500-1000-1750-2250-2500-3000

UPD3: Editorial

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

Comments Comments (185)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

Is there something wrong with the registration system before? I noticed that it said the contest will be rated for people whose rating is under 1900 on the registration page when I registered for this contest.The Candidate Masters who registered that time have the sign of out of competition. What should we do now? Should we register again or the administrator will help us fix the bug? Please fix it, thanks and wish all the participants have a good contest and get a good rating.

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

    You can write comment in THIS BLOG, MikeMirzayanov has noticed the issue

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

    I was registered out of competition and had to re-register. I am not sure if everybody noticed that — is there a way to automatically transfer all out-of-comp candidate masters to normal registration?

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

      Mike said here that he was going to fix it later. He probably hasn’t gotten around to it yet.

      → Reply
»
6 years ago, # |
  Vote: I like it -42 Vote: I do not like it

oh god PLEASE no useless math so we can participate .... i know we don't matter for you anymore but make an effort for us and don't bullshit us.
but i don't have much hope in this one as the problem setter is from india . oh well

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Codeforces round by an Indian coder. I am really exciting for this contest.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    why so ?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    I hope someone with the handle name "System_test_failed" reply to this comment

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

    Let's hope your code will pass in system testing too. :)

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

    Any categorization of people according to their respective nationalities is potentially provocative.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    excited*
    learn to speak English before trying to look smart online.

    → Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Let's hope for a contest with awesome questions with strong pretests !!!

→ Reply
»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Squad is Back on the occasion of Holi.

Super Excited.

→ Reply
»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Contest on Holi.

Confused whether to be happy or to be sad.

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

    Anyway it doesn't matter, You won't be busy hitting colours at 9:05pm (IST) in the night.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is there a separate discussion forum for Codeforces or do people have to write blog entries?

Does anyone know if Topcoder has the same functionality as Codeforces like being able to solve past problems, submit solutions for testing, viewing other people's solutions filtered by language sorted by executions time, etc.? Topcoder website seems like a disaster. I would ask this in the Topcoder forum except I can't find a way to make a post there and there customer support seems unable to help. Thanks.

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

    Yes, it has most of it, but you need to download and launch Topcoder Arena

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

      Thanks. Is there a separate discussion forum on codeforces or do I ask questions on Round blogs like this?

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

        You should ask questions in blog entry, or comment on the relevant post

        → Reply
»
6 years ago, # |
  Vote: I like it +80 Vote: I do not like it

holi .

→ Reply
»
6 years ago, # |
  Vote: I like it -22 Vote: I do not like it

it is too late for our Chinese students (￣_￣ )

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

    Because it needs to consider the time in Russia and the time in the author's country. It is late for Chinese students sometimes, but whether you participate in it or not still depends on you. You can balance your study, sleep and the training and the contests. If you really want to join the contest, just do it. If you are worried about the time and will not join it, you still can virtual participate or just practice the problems when you are free.

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

      There is no doubt that I will participate in it,because I really enjoy it.However it just goes against my original intention of wanting a healthy life. :D thanks for your reply.

      → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Should the pretest be strong enough or not ??

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it -20 Vote: I do not like it

I think this contest will be harder than div 3

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to add some scores ^_^

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Jeel_Vaishnav thanks for contest

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

Раунд от индуса..........

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why "fidofido" is the bad word?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Woow this round, I will fall) but its doesn't matter, because it will "FUN"!

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Hi guys! Unfortunately CF-Predictor doesn't work in last version of Chrome. They changed Cross-Origin Read Blocking policy and my extension can't send requests to the backend anymore. But the actual problem is that I can't update code and fix issue ASAP. I recently started working in Google and they have pretty strict policy about open source projects. I'll try to come up with some solution, but sorry terms are unknown.

Current solution is to use website version.

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

    What about Firefox? Is the extension working there?

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

      Yes, I suppose so. It even can works in Chrome if it doesn't updated yet.

      You can just open any past contest and if you see additional column with rating change, extension is working.

      → Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Complexity distribution is so balanced

→ Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Nice Problem D!

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

What is wrong with the pretest 8 on problem C?

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

    I think you have not taken care of adding 10^9+7 while subtracting and then taking mod.

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

    you might be doing (total-calculated_value)%mod, which gave WA to me , but using (((total-calcualted_value)%mod )+mod)%mod which gave AC,hope it may help.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

D is a very cool problem

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

.

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

During the contest, I got alot of "codeforces is temporarily unavailable" page and the problem was taking a lot in order to show anyone face the same issue like me?

→ Reply
»
6 years ago, # |
  Vote: I like it +116 Vote: I do not like it

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when you don't want to solve graphs problems but cf has another opinion

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

A lot of people were saved by the authors from being hacked on A due to integer overflow.

→ Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

PROBLEM C IMPOSSIBLE WHY WA??

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

who is the setter of problem d ? Ashishgup ?

→ Reply
»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Million dollar question-How to solve D?

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

    for each number g you have to find 3 things:

    a = how many numbers are relatively prime to g within range [1,m]

    b = how many numbers will have gcd g again when paired with g within range [1,m]

    c = how many numbers have gcd<g when paired with g. (This was the hardest part for me in this problem)

    The rest is calculating E(g) with a bit of knowledge of probability

    My code: 51649595

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

Is there O(n*k) solution for C? Or the constraints were there just to bamboozle innocent people like me? :)

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

    No need to count connectivity of red edges. Merge all nodes with red edges to components and multiply each member count of adjacent components

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

    Just a linear time solution. O(n)

    Count the number of bad strings, and subtract them from total (n^k) to get the final answer.

    Think how you can form a bad string, which doesn't traverse through any of the black edges. For simplicity remove the black edges from the graph and then, you'll get some connected components.

    To Form a Bad string of length K, all the nodes should be from the same component. If you take nodes from different components, they must have to traverse through a black edge and hence it will not remain a "bad string".

    Now suppose cnt = no. of nodes in a connected component. Then no. of bad strings formed by nodes of that particular connected component is = cnt^k

    Total no. of bad strings = sum of bad strings of each component.

    Note : If the difference is less than 0 after taking modulus with 1e9+7, Add 1e9+7 to make it positive.

    → Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

One minute silence for the three Indians: alwaysGREEEN, Abhinaviitbhu and imhemant.
Who were the only people to get hacked today, on the occasion of holi.

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

    and a minute for me for 3 fail hacks

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    First, notice that this is an inclusion-exclusion type of problem. So the answer will be something like: all possible permutations — all impossible ones. After realizing that, you'll soon notice that all the impossible ones are the collection of nodes that don't have any black edge at all.

    Hence, we can simply isolate collection of nodes by using disjoint set. Simply merge when the edge is red and skip the black edge. When you have got a bunch of disjoint sets, you can calculate how many permutations can be constructed from a disjoint set of size x. pow(x, k)

    The total answer would be pow(k, n) — (for each disjoint set of size x, pow(x, k))

    Solution

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve C

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

    lets do tree with only RED . we have forest and answer is n ** k — a1 ** k — .. — af ** k, whee ai number of vertexes in i tree

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

    Count how many sequences are bad (not good) and subtract it from N^K. If we make the graph only with red edges, for each connected component with size X we will get X^K bad sequences from this component. Sum of bad sequences for each component will give total number of bad sequences. It's not possible to get any more bad sequence because merging any two component would need black edge which we can't use in bad sequences.

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

How to solve E?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +30 Vote: I do not like it
    Spoiler1
    Spoiler2
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot!

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 8   Vote: I like it 0 Vote: I do not like it

      Is this the right approach?

      We start with a bipartite graph with 0 potential vertices on the right. We will first add all persons that were never removed to the clubs on the left. We will process the days in reverse order. We will add the person that was removed on this day to our bipartite graph after we have processed this day. As long as the bipartite matching is maximal, we add the first available potential (first 0, then 1, then 2, etc) to the bipartite graph and rerun the matching algorithm. When the matching is not maximal anymore, the final value we tried to add is our MEX value for this day. The MEX can only increase during this process, so we never have to remove added potentials anymore in the graph.

      Edit: solved while processing the days in chronological order with a similar approach as described above (but instead of adding potentials, we remove them when the matching isn't maximal). https://codeforces.net/contest/1139/submission/51653759

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

      RobeZH, how are you calculating mex using bipartite matching. Can you please explain. Thanks

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

        First we build a graph to check that whether the mex can be 1 (, more specifically, say we put the potentials on the right hand side of the bipartite graph, we build it such that only potential 0 is connected to the sink, and see if there is a perfect matching). If yes, we incrementally build the graph to check that whether the mex can be 2, and so on. If no, we know that the previous number is the mex for the current set of people.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Help me solve problem B, My solution O(n^2) :'(

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

    You can solve it in a single iteration from n-1 to 0, making it O(n).
    Check my simple solution.

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

      thank you, I misunderstood the problem. I think it don't need to end at n-1,

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

        Oh sad.. Better luck next time :)

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

    Think greedy.
    Use the maximum possible number of chocolates from a_n and with considering the picks use the maximum possible number of chocolates from a_n-1 and so on...

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can some one help me with problem D?
I got wrong answer on test 13.
Here's the code

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

Today's problem C, is the first tree problem I have solved till date without traversing (dfs/bfs) the tree.

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

    How so?

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

      I used UFDS (Union Find Disjoint Set).
      Check my solution.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        Oh, yes, I forgot about DSU solution.. But that means that you are expert and never solved MST problem, wierd.

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

          I am talking about exclusive tree problems usually given in cf.
          I believe MST is found on a given general graph.
          Or maybe I just don't remember. Thanks for judging me :)

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

            Can you talk a little about your solution using DSU?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              1. Merge all the nodes connected by red edges into disjoint sets.
              2. Find the no of sequences of size 'k' formed by each of the disjoint sets individually and sum all of them.
              3. Answer will be n^k -the sum found in step 2.
              4. Also keep in mind we need to subtract sequences with all nodes same.

              Check my solution for more clarity.

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

    In fact, it can be solved by just dfs.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to write code to hack others? I use this code to hack problem B, why the return is "Invaild input"?

include

using namespace std; int main() { int n=100000; printf("%d\n",n); for(int j=n;j>=1;j--){ int t=10000000-j+1; if(j==n){ printf("%d",t); } else printf(" %d",t); } return 0;

}

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Nice set of Problems. Three cheers to the authors :D

Already waiting for the Editorial. Please publish them soon :)

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

What is the intended solution for D? I managed to pass the pretests with inclusion-exclusion and some optimisations.

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

    My solution was calculating the probability of obtaining an array of length n with the gcd of the array(except the last elemnent) as x with ending element y where $$$x,y \in [1,m]$$$, $$$ n \in [1,\inf]$$$ and y is coprime to x.
    Then, summed up the contributions with a bit of math.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem E: The mex of the multiset S is the smallest non-negative integer that is not present in S. For example, the mex of {1,2,3} is 0. Why the mex of {1, 2, 3} is not 4?

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

    0 is non-negative and 0 is smaller than 4.

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

    0 is a non-negative integer. The MEX of {1,2,3} is 0, because 0 is not in the set. It would be 4 if the set was {0,1,2,3}.

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

    EDIT: Triple ninja-d :) Because 0 is nonnegative?

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

    non-negative integer means zero is included.
    {0,1,2,3,...}

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

    Oh thanks, I'm sleepy :D

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

Problem C: Count connected components of red nodes. If a connected component has p nodes. Impossible paths are p^k, sum similarly for all connected components. Finally subtract this value from n^k, also subtract no of nodes that have zero red edges. Is my idea anywhere close at least? I couldn't manage the time to implement though..

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

    I think the answer is just $$$n^k-\sum p^k \pmod{1e9+7}$$$

    → Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

can E be solved by maximum matching?

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

can prob E solved by bipartite match?

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

    Yes. But there is tricky part, it is not just reduction to maximal matching problem.

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

      so sad...

      When I recognised how to solve this problem, it was 10 minutes before the conteat ends.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was a very unbalanced round. The jump in difficulty from B to C was to great. The problems were interesting but I felt like there should have been a problem between B and C.

→ Reply
»
6 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

I made an idea for Problem D and couldn't implement it for 1 hour 30 minutes XD

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

    why ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 8   Vote: I like it +5 Vote: I do not like it

      My idea is very hard to implement(at least for me).

      My solution idea for D:

      1. We can define the weighted/directed graph to solve this problem. Each node has distinct set of primes. This means the prime divisors of greatest common divisor made by array $$$a$$$ so far. For example, if the $$$a = [24, 30, 18]$$$ then the state of $$$a$$$ is $$$(2, 3)$$$. Of course there can be self-looping edge exist.

      2. There is a special node called all, this node contains all prime numbers in $$$[1, m]$$$. For all non-special nodes there is an edge exists directed from all to that node.

      3. Calculate weight of all each edges, then you can solve the equation such like; $$$EX(node) = 1 + \sum_{\text{all neighbors}}^{} EX(neighbor) * weight$$$ where $$$EX$$$ means the expectation of length of sequence started from that state. There is an exception; $$$EX(NULL) = 0$$$.

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

      Example for $$$m=10$$$

      • all -> null: 1 (1), [2]: 3 (2, 4, 8), [3]: 2 (3, 9), [2, 3]: 1 (6), [2, 5]: 1 (10), [7]: 1 (7), $$$EX(ALL) = 1 + 0.1 EX(NULL) + 0.3 EX([2]) + 0.2 EX([3]) + 0.1 EX([2, 3]) + 0.1 EX([2, 5]) + 0.1 EX([7])$$$
      • [2] -> [2]: 5 (2, 4, 6, 8, 10), null: 5 (1, 3, 5, 7, 9), $$$EX([2]) = 1 + 0.5 EX([2]) + 0.5 EX(NULL)$$$
      • [2, 3] -> [2]: 4 (2, 4, 8, 10), [2, 3]: 1 (6), [3]: 2 (3, 9), null: 3 (1, 5, 7), $$$EX([2, 3]) = 1 + 0.4 EX([2]) + 0.1 EX([2, 3]) + 0.2 EX([3]) + 0.3 EX(NULL)$$$

      You can find weight of all edges with fast factorization.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      More simple example $$$m=4$$$

      • all -> null: 1 (1), [2]: 2 (2, 4), [3]: 1 (3), $$$EX(ALL) = 1 + 0.25 EX(NULL) + 0.5 EX([2]) + 0.25 EX([3])$$$
      • [2] -> null: 2 (1, 3), [2]: 2 (2, 4), $$$EX([2]) = 1 + 0.5 EX(NULL) + 0.5 EX([2]) = 2$$$
      • [3] -> null: 3 (1, 2, 4), [3]: 1 (3), $$$EX([3]) = 1 + 0.75 EX(NULL) + 0.25 EX([3]) = \frac{4}{3}$$$
      $$$EX(ALL) = 1 + 0.25 \times 0 + 0.5 \times 2 + 0.25 \times \frac{4}{3} = \frac{7}{3}$$$
      → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for awesome problemset and super fast system testing !

I have enjoyed the contest a lot.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if a problem submit twice, all accept, which is the score in the problem?

→ Reply
»
6 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Why is this invalid input for hacking A? Why is this N^2 solution passing for A?? Please help.

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

    Because servers are now upgraded and with compiler optimizations almost around O(10^9) passes in one sec.

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

    Probably compiler optimization.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    The compiler optimizes the increments in the for loop into an addition. After optimization, the complexity is $$$O(n)$$$.

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I was kind of confused by problem B, it implies you can decided to buy a chocolate or not, but in reality you always buy a certain chocolate, even if 0 times...

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody tell me how to solve problem D? I was thinking to solve it like E[len]=E[number of 1's]+E[number of 2's]+E[number of 3's]+------E[number of n's] in the sequence but could not able to solve it.

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

    See my solution: https://codeforces.net/blog/entry/66067?#comment-500828

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

    No. of N-length arrays: Sum(C[i] ^ N) / m ^ N. ( 1 <= N <= ...)
    C[i]: Count of multiples of C[i] <= m. (Make sure that we do not re-count multiples, C[x] -= C[y])
    If you re-arrange 1st statement, you can get sum of infinite GPs for each C[i].
    Sum the answer for all C[i].

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

      You are taking C[i]^N for length N but it contains all the elements that have GCD>1 so length will no longer be N and it will be more than N

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, can someone explain the solution with mobius function?

My solution is $$$\sum_{i=1}^{\infty} i*q^i = q / (q-1)^2$$$, and the answer is $$$\sum_{i=1}^{m}mu[i] * q / (q-1)^2$$$, $$$q=[m/i]/m(i=1\dots m)$$$, but it is wrong :(

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Because you count something twice or more. Let call the first expression is f(q), then you want f(i) is the answer with some first element have gcd() = i, but you also count the other with gcd = 2i, 3i, ... So you need to subtract f(2i), f(3i) to get the right answer.

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

    Actually, what you're looking for is $$$\sum_{i=1}^{\infty} (i+1)*q^i*(1-q)=\frac{q*(2-q)}{1-q}$$$(you need to factor out the $$$1-q$$$ for wolfram alpha to give you the result: https://www.wolframalpha.com/input/?i=(sum+of+i+from+1+to+inf+(i%2B1)*a%5Ei)*(1-a)*1 . Make sure to add $$$\frac{1}{m}$$$ at the end for the special case of length 1. AC code: 51651931

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

      I get it, Thx!

      It seems that I missed the case that the first element is 1.

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

When will tutorial be out?

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

[Problem B] I just realized I didn’t understand the task properly. But now I wonder if there is a nice algorithm to solve the version of this problem that I had in mind.

So the condition is such that the number of chocolates we buy has to be a strictly increasing segment. In particular we are allowed to leave some types of chocolates on the right side. For example:

5
1 2 3 1 1

Should produce 6.

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

    I had the same misconception in the beginning, couldn't thing of anything better than O(N^2).

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

    Same happened to me. Lost a lot of time for not reading again the problem statement.

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

    Couldn't solve it because I understood the same.. After almost 2 hours thinking i'm pretty sure there isn't anything better than N^2.

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

      This problem can be solved in O(N).

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

      This can be solved in O(nlog(n)) it is simply LIS dp problem in your variant

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

        I don't know if we are understanding the same problem.

        For input array = {1 1 4 3 5 1} result would be 11 (0 1 2 3 5 0).

        How would you solve it with LIS?

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked the C priblem a lot. At first I found it difficult to solve it, but after that i understood it was easy.

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Please publish the editorial as early as possible. Can't wait to see the solution of problem D, E and F!

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanx. Nice problems. It is good that in pretests exists test for TLE, at least for E. There is happen that seems like optimization do not need, but pretest got TLE and one saves time for testing and will not get disappointment after contest.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How did (n*n) solution got accepted in Q A? Link https://codeforces.net/contest/1139/submission/51625556

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

I know that E's Solution is Khun's algo with reversing queries, but I am interested to know was there any direct HopcraftKarp Solutions that passed it should be $$$O(N^2sqrtN)$$$, since the number of edges <= 5000 and the number of nodes <= 5000 that totals to $$$\cdot{2*10^9}$$$ operations approx.

but as I don't really understand how HopcraftKarp works I am not sure can it be optimized to pass?

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

    I think if we use Hopcroft Karp we need to binary search on the answer and so we attain complexity of $$$O(N^2 \cdot sqrtN \cdot logN)$$$. Can you explain your approach of using Hopcroft Karp and attaining complexity $$$O(N^2 \cdot sqrtN)$$$?.

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

      Sorry, apparently I really didn't understand Hopcroft Karp that well, a friend of mine explained it to me afterward and told me that a simple $$$O(N^2sqrtN)$$$ Hopcroft Karp is not doable.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE on pretest 6 in Problem A. Please help. Link to the submission. In this code I'm taking each substring and just checking the last digit is even or not. Is it not one of the right way to do so?

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

    Your complexity of solution is O(n^2) and I guess java is slower than c++ and the multiplier for java might not be enough for an O(n^2) to pass but in c++ it is, just bad luck i assume!

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why did my Submission 51646792 fail? Does it have something to do with modular arithmetic?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting WA on pretest 10 in Problem B. The longest testcase, I suppose. Link to my submission. Please Help.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone check if my solution for E is correct? It's not maximum matching.

First, I find max mex for the given situation without considering updates. Here's how I do that: I go from $$$0$$$ to as far as I can go by randomly picking a club which has a member of the required potential. When I choose the $$$i$$$'th club for potential $$$j$$$, I make a directed edge from all other clubs who have a member with potential $$$j$$$ to $$$i$$$. Now, if I get stuck at some potential k, I will bfs from the unused clubs to find a club which has a member with potential $$$k$$$. Now, if the path to this club is like $$$p_{x}$$$ -> $$$p_{a_{1}}$$$ -> ... -> $$$p_{y}$$$, where $$$p_{x}$$$ is the unused club and $$$p_{y}$$$ has a member with potential $$$k$$$, I can replace $$$p_{a_{1}}$$$ with $$$p_{x}$$$, and $$$p_{a_{2}}$$$ with $$$p_{a_{1}}$$$ and so on. After this I update the edges of the graph as required. By the end, I will find the max mex for the given situation.

Now, for updates: First notice that the max mex can only decrease or remain same. Now, I maintain the reverse of the graph I mentioned above, if a member from club $$$i$$$ is chosen for potential $$$j$$$, then I make a edge from club $$$i$$$ to every other club which also has a member with potential $$$j$$$. Now, for each member which leaves, we see if we were using this member in our chosen max mex, if not, we do nothing. If yes, then we bfs from this club to either find a club which is unused right now (in which case max mex remains same) or we find a used club from which we have taken a member with the highest potential (in this case max mex becomes this new potential). In both cases we update the entire graph again as required.

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

My solution for C runs in O(nk) time and it still TLEs, does anyone know why it exceeds the time limit

https://codeforces.net/contest/1139/submission/51649583

edit: I found the reason: apparently running a DFS has a much larger constant than I thought. I ended up passing by precomputing the DFS order and then doing DP directly on that

https://codeforces.net/contest/1139/submission/51920785

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem D how to find no of possible ways to get an array of length k with gcd say x

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

    You need to get needed prime divisors and avoided prime divisors. That's the key.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hello, Div.2, my old friend

I've come to solve your tasks again...

→ Reply