Jeel_Vaishnav's blog

By Jeel_Vaishnav, history, 5 weeks 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, V--gLaSsH0ldEr593--V, mohammedehab2002 and Um_nik for testing the problems and _kun_ 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  

»
5 weeks 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.

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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?

    • »
      »
      »
      5 weeks 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.

»
5 weeks 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

»
5 weeks 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.

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

    why so ?

  • »
    »
    5 weeks 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

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

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

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

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

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

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

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

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

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

Squad is Back on the occasion of Holi.

Super Excited.

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

Contest on Holi.

Confused whether to be happy or to be sad.

  • »
    »
    5 weeks 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.

»
5 weeks 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.

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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?

      • »
        »
        »
        »
        5 weeks 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

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

      where?

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

holi .

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

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

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

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

Should the pretest be strong enough or not ??

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

    Ashishgup's contests run smoothly.

    Hope for this contest too.

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

    i think pretests should be strong but they should not be too strong otherwise hacking phase will have no meaning !!!

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

Happy Holi to everyone.

»
5 weeks ago, # |
Rev. 5   Vote: I like it -20 Vote: I do not like it

I think this contest will be harder than div 3

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

I want to add some scores ^_^

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

Jeel_Vaishnav thanks for contest

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

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

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

Hope see some worthy problems this time...

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

Why "fidofido" is the bad word?

»
5 weeks 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"!

»
5 weeks 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.

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

    What about Firefox? Is the extension working there?

    • »
      »
      »
      5 weeks 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.

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

Complexity distribution is so balanced

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

    lol xx its hard to set a bc

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

      haha , thats why i think why cf doesnt hold div1 rounds frquenttly :

      reason : div2 problems are more likely equal to div 1 c , d .

      then why create a seperate rounnd just for div1 e .

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

Nice Problem D!

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

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

What is wrong with the pretest 8 on problem C?

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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.

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

D is cool problem

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

Liked Problem C a lot thanks!!

»
5 weeks 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?

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

»
5 weeks 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

»
5 weeks 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.

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

PROBLEM C IMPOSSIBLE WHY WA??

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

who is the setter of problem d ? Ashishgup ?

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

Million dollar question-How to solve D?

  • »
    »
    5 weeks 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

»
5 weeks 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? :)

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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.

»
5 weeks 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.

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

How to solve C?

  • »
    »
    5 weeks 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

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

    a

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

Can someone explain how to solve C

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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.

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

How to solve E?

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

      Thanks a lot!

    • »
      »
      »
      5 weeks 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.com/contest/1139/submission/51653759

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

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

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

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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,

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

        Oh sad.. Better luck next time :)

  • »
    »
    5 weeks 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...

»
5 weeks 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

»
5 weeks 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.

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

    How so?

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

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

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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 :)

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

            Can you talk a little about your solution using DSU?

            • »
              »
              »
              »
              »
              »
              »
              5 weeks 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.

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

                Thank you!

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

    In fact, it can be solved by just dfs.

»
5 weeks 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;

}

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

    Dude, you gotta give input to the code they've submitted on which you think that expected outcome will be different from their's output, nor the code.

    Hope you get it.

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

    You need a newline at the end of the input.

»
5 weeks 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 :)

»
5 weeks 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.

  • »
    »
    5 weeks 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.

»
5 weeks 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?

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

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

  • »
    »
    5 weeks 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}.

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

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

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

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

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

    Oh thanks, I'm sleepy :D

»
5 weeks 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..

  • »
    »
    5 weeks 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}$$$

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

      What is the reasoning behind your formula?

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

        There are n^k paths in total. If there are p nodes in a connected component(>=0 red edges, ==0 black edges), invalid paths are p^k. Sum all such p^k, subtracting this from n^k gives valid paths.

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

oh shiiiiit , i solved problem C but i forgot to Print the number of good sequences modulo 109+7.

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

E has an awesome solution)) Really nice, and didn't even get close to solving it

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

contest was good !! Happy Holi everyone :)

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

can E be solved by maximum matching?

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

can prob E solved by bipartite match?

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

»
5 weeks 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.

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

    yup! but petr can solve every question. he solved such hard problems of Atcoder world finals where gennady just solved one . so before listening to twice , listen to his stream

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

    I have the same thoughts about C and D))

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

»
5 weeks 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

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

    why ?

    • »
      »
      »
      5 weeks 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$$$.

    • »
      »
      »
      5 weeks 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.

    • »
      »
      »
      5 weeks 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}$$$
»
5 weeks 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.

»
5 weeks 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?

»
5 weeks 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.

  • »
    »
    5 weeks 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.

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

    Probably compiler optimization.

  • »
    »
    5 weeks 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)$$$.

»
5 weeks 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...

»
5 weeks 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.

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

    • »
      »
      »
      5 weeks 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

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

Good contest

»
5 weeks 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 :(

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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.

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

When will tutorial be out?

»
5 weeks 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.

  • »
    »
    5 weeks 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).

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks 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.

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

      This problem can be solved in O(N).

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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?

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

          I was stuck at B because of same understanding. I am also wondering how to solve it in O(n) even though it was not the original problem.

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

    This should produce 1 not 6

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

    Lol , looks like I was not the only one who understood the problem in this way during contest time. I was stuck at this testcase for B (ofcourse because of same assumption as yours)

    5

    8 6 5 3 4

    here answer should be 12 by taking 3 from 8 , 4 from 6 , and 5 from 5.

    can anyone suggest how to solve this problem , where order should be increasing and we have to maximize the sum just like given above testcase.

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

      The answer for the above test case will be 10 and not 12 by taking 0 1 2 3 4.

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

        Thank you , but now I am curious about solving this imaginary problem .

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

      If we take your approach [3,4,5,0,0], then we see that for j=2 (here 5), and i=3 (here 0) , Aj is not less than Ai as 5>0, and neither it is 0. Hence, we are not satisfying any of the conditions.

»
5 weeks 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.

»
5 weeks 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!

»
5 weeks 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.

»
5 weeks 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.com/contest/1139/submission/51625556

»
5 weeks 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?

  • »
    »
    4 weeks 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)$$$?.

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

»
5 weeks 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?

  • »
    »
    5 weeks 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!

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

      Thanks buddy. Bad luck today indeed.

»
5 weeks 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?

»
5 weeks 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.

»
5 weeks 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.

»
5 weeks 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.com/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.com/contest/1139/submission/51920785

»
5 weeks 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

  • »
    »
    5 weeks 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.

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

benim neden degerlendirmem dusuyorki bir problem cozdum ve bir kez bile yalnis gondermedim puanym 844 ve 24 degerlendirmemi kaybetdim bunun nedenini bana soyliyebilirmisiniz lutfan

»
5 weeks 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...

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

I have a solution to Problem B but cannot pass the pretest 10 (very large values).

could anyone help me to find out flaws in my solution?

The basic idea is to find the most right tangent line of the curve of $$$a_i$$$, it treats the final solution as two parts:

  1. an increasing straight line with slope rate k=1.
  2. values after the last joint point.

We can get the answer easily by adding those two parts together.

here is my solution: https://codeforces.com/contest/1139/submission/51664626

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

In problem D. Why the example 3 has the output 3333333338?