mtnshh's blog

By mtnshh, history, 3 years ago, In English

The Programming Club, IIT Indore is proud to present our flagship event, Divide By Zero! The contest will take place on 11.04.2021 17:35 (Московское время). This round will be rated for all participants with a rating lower than 2100.

Divide By Zero 2021

Thanks to the following people for making the round possible:

There are 6 problems, and 2 hours to solve them. The points distribution will be updated later.

Update: The scoring distribution is 500 -- 1250 -- 1500 -- 2000 -- 2750 -- 3000.

Update: Editorial is up.

PRIZES: Twenty Codeforces T-shirt will be given to:

  • Top 10 Indian Participants
  • Random 10 from top 100 (rank 11-100) Indian participants

Hope you guys enjoy the contest! See you on the leaderboard!

Update: Here is the list of winners who won T-shirts. We will contact you guys soon. Congrats!

Top 10 Indian Participants

Random 10 from top 100 (rank 11-100) Indian participants

We have uploaded the link to the code for generating random numbers and ranklist here.

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

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

Indian round ,Cool,,, Hopefully I will be gray this round :)

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

    It's not about hope, You'll be gray if you participate.

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

      It was joke comment.

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

      Yess bro....Thanx for motivating me,,,,I will participate this tym,,,,I tried many time but I am not able to solve even one problem :)

      EDIT:

      Spoiler

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

        To be honest, I wasn't motivating, wether you solve all of the problems or none you will be newbie after your first contest.

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

          This just got me to think, what's the maximum delta one could achieve? Like, say a new account finishes 1st in a combined round (like the global round). She will gain 500+(actual delta). Where actual delta might even be 500-600s considering it's a combined Div1+2+3 round. That's quite close to pupil, right?

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

            Well, first of all it depends on the contest, as you mentioned global round is rated for the 3 divisions and it's nearly impossible that an unrated account ranks the first place. So second and third divisions are left(since an unrated account can't participate in a first division contest), and I've seen unrated accounts reaching the first place in a second division contest and gained at most 900 delta.

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

              The person said max delta so it doesn't matter if its almost impossible for an unrated account to win a contest, plus you are also forgetting alt accounts.

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

            An unrated account starts from 1400, the maximum is gotten from winning a contest. Also notice that the more the people in a contest, the higher the rating for the people at the top also same if the opponents are of higher rating, so the best case is winning div 1 but its unrated for a 1400, so we have to stick to global rounds and div 2s . You can use CF visualizer to check for the contests with the highest number of people in global and div 2 and 3.

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

              Unrated accounts now start from 0 rating.

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

              Yes, that is why I mentioned common rounds for all divisions. With div 2 or 3 the maximum change would be less. If it is possible to get +700 then along with 500 (being first contest) one can still skip newbie and become pupil

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

            JrNTR

            EDIT: Just wanna say he got 1000 in first round (I guess maximum possible)

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

    Indian round ,Cool,,, Hopefully I won't be green this round :)

»
3 years ago, # |
Rev. 5   Vote: I like it -48 Vote: I do not like it

why indian guy ?

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

    because IIT indore means The Indian Institutes of Technology Indore

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

      I really think the "The" you mentioned was knowingly... Seriously..

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

i think its time to change the country part in the setting to india for this round :dicaprio:

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

    Maybe time for getting a Shipping address in India too, and also ID proof.

    PS.: Currently, shipping t-shirts would be tough in India too, shipping worldwide is almost impossible.

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

      you can sell it to someone in india $

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

        Not worth the effort xD

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

          i know XD it was a joke but some people take it seriously lol

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

How is blue coder setting problems? I think rules were changed this year, you need to be at least 2100.

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

    A blue can't set alone but he can do with orange or red. Orange/Red can only set contest.

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

As a contributor, I hope my contributions will become positive after this contest XD.

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

    As an advisor; Try rewriting; as a contributor, in the beginning, that will surely stonk your contribution.

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

One of my little dreams is to see my contributions positive !! Certainly anyone no likes negative contributions, so don't be harsh with me and help me achieve this little dream ..

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

    I have noticed you comment in almost each blog Maybe you should try to control your urge as it seems too irritating for others.

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

      Thanks for your kind words, which caused more negative votes.. After this comment, I am no longer interested in my Contribution. I assure that you will not upset about see my comments anymore :)

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

Indian round cool. Expecting to do good and atleast come closer to green :)

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

All the best everyone .... Jai Hind

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

Many indian contest recently. You guys are motivated.

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

    Naah, just population I believe xD

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

      The same reason why there are so many smart Chinese :)

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

Hi Sir, I am not able to attend these contests which startsat 8:05 PM. So, Please Change the timing to Sunday Morning 10:00AM. So, Please consider my request. Thank you Sir

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

On April 6th, a contest was held in Codechef which was prepared by IIT Varanasi. After competing in it I felt it's some what like a classical math question paper than a programming contest. So, is it Déjà vu ?

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

Indian round, cool

insert nationalistic comments

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

China>India

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

good to see India here.

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

I wish this contest have interesting problems and strong pretests.

Wish you all luck and rating increasing)))

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

Auto comment: topic has been updated by mtnshh (previous revision, new revision, compare).

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

1250 for a B problem,The B is going to be some mind-fuck problem IMO.

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

    I think it is just free points.

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

      What a positive attitude you have, but then again you are a MASTER and I am a grasshopper(literally because i am green).

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

    Funny thing is IMO can be read as International Math Olympiad:)

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

I have a feeling that this contest is going to be terrible.

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

I think it's cool than chinese round,because chinese round is too hard,although it's my country...

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

hope I remain expert after this contest :)

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

Is it rated?

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

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

wake the firck up samurai

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

MikeMirzayanov it's kind reuqest. please no codeforcoes round during CSK matches. As you know this season dhoni last season. I want to enjoy both codeforces and msd. Please atleast change timings of CSK matches

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

The score distribution is wrong, lol

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

Why is my nlogn solution giving TLE for B? 112705441

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

    You are initializing an array of size 2,00,001 in each testcase. Maybe that's the reason?

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

can anyone plz tell me why D wrong on pretest 3??

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

    Yes, someone please tell me what is the Pretest 3 in D.

    • I got WA on Pretest 3.
    • Then, I figured out I used to wrong iterator. After correcting it also, WA on pretest 3.
    • Then I thought, maybe it is because of overflow. So, I used long long. Then also WA on Pretest 3.
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try this -
      1
      12 12
      2 4 10 16 2 6 3 21 30 17 20 16
      Answer — 55
      I figured it out in the end but was not able to implement it in time.

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

Can someone explain me the approach of C?

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

    I precomputed number of digits for 0 to 9 until 2e + 50 and then solved eatch testcase in log10(n) by simply adding values from the array.

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

      What is the formula to that series?

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

      Is it cool to access oeis, during the contest ?

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

        As long as the resource being looked up exists before the start of a contest, it is okay to take help from that resource during contest

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

    I have just debugged my code :( But I think it will be AC. EDIT: It got AC: 112711140

    We can calculate answer independently for every digit, so we can use precalculation.

    Precalculate all the answers (200000) for 9. It will take about of 2*10^6 operations

    Then, in every test case count how many times every digit is present in n. I have used cnt array for that.

    Substract every number from 1..9 from 9 and check if it's less than m. If it is, just add calc[m — (10 — i)] * cnt[i] to the answer. Else, simply add cnt[i] to the answer.

    Time Complexity: amortized O(1) per every test case.

    Code:

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

    https://codeforces.com/contest/1513/submission/112705430

    I am getting TLE On Pretest 3? What is wrong with my submission?

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

      try to add ios::sync_with_stdio(false); also add #pragma GCC optimize("Ofast") and #pragma GCC target("avx,avx2,fma")

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

ModuloForces

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

How to solve D?

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

Can anyone explain why I am getting Runtime error on pretest 1 for problem C? Its working fine on my local machine! https://codeforces.com/contest/1513/submission/112707395

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

    your code has "index out of bound" on line 51

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

      How did you check that? My local runtime env doesn't complain..

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

        Add -fsanitize=undefined to your compiler's flag. But even without any flag I still got segmentation fault.

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

          Btw, thanks it was indeed the mistake. I reckon, you deleted your comment of -Wall, but that was some good info for me again, so thanks for that. In my case -fsanitize=undefined does give me runtime error now. Thanks a bunch! :)

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

so hard :(

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

For problem A, I noticed someone's solution only printed "-1" if n>=k

So I tried to hack it with a test case of n=3, k=1

But the solution was in python and I forgot integer division works differently in python :(

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

This contest is hard and required to know a lot of Math knowledge, just in my opinion. It is hard for everyone who has no experience. Bye bye Blue. I am back to Cyan soon.

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

    It's harder than usual but not because of the math knowledge imo.

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

    I agree that it needed more math knowledge than usual, but mostly math that occurs pretty commonly in competitive coding, not anything completely out of the blue.

    • A — Adhoc, maybe a bit mathy

    • B — Required some basic combinatrics, so fair enough its pretty heavy math for a B.

    • C — Pretty standard dp, no math involved

    • D — First observation is somewhat math intensive for a D (gcd = min means all elements are multiple of the min), but the rest of the problem requires no other math, just intuition of why Kruskal's algo constructs an optimal MST.

    • E — Pure math, all non-combinatorial observations can be made using just the samples. Then its just standard combinatorial ideas that most 18-1900+ rated participants should have likely come across.

    • F — didn't solve, no comments.

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

For some reason, everyone's problem A sols were hacked but its been reverted

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

Problems were hella good imo, especially D

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

how to solve b

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

    The condition in the problem is equivalent to finding the number of permutations of Indices of the array's elements so that ap1 and apn are bitwise and operation of all of the elements in array a. So let cnt be the number of occurrences of (a1 & a2 .. & an) in array a, if cnt is less than 2 then there is no such permutation and the answer is 0, otherwise the answer is cnt * (cnt — 1) * (n — 2)!.

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

    For intuition, consider n = 2. This has a valid permutation when both elements are identical.

    Now consider n > 2. What if the first and last elements in the permutation are different? Then, this is not a valid permutation since you can always make a 1-element group which has just the larger endpoint, and a (n-1) element group with all the other elements. The AND of the group with the smaller endpoint is strictly smaller so there's no solution.

    Now we know the end points have to be the same. What about the middle elements? Assume there's an element in the middle that has a 0 in a bit where the endpoint has a 1. Then, we can always make a (n-1) element group that will have an AND smaller than the other endpoint. So, every element a_i in the middle must equal the endpoint when ANDed with the endpoint, i.e. satisfy (a_i AND a_0) = a_0. This also implies the endpoints must be the smallest values in the array.

    So the answer is (count_of_smallest_element nCr 2) * ((n — 2)!), assuming there's at least 2 of the smallest element and all values in the array equal the smallest value when ANDed with it.

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

If only I never knew matrix expo, would have I not made three TLE attempts at C, coded the intended dp solution and saved the contest. Unlucky day, though I had fun nevertheless. Good contest.

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

Missed D just by a minute :(

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

I really need to know why my D failed, sumission, else my brain might explode. Please.

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

    I have the same code... also very curious :) submissions

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

    Try this -
    1
    12
    12
    2 4 10 16 2 6 3 21 30 17 20 16
    Answer — 55

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

      nope,this is not a good test,my code is right on this but wrong on 3rd TC

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

        Maybe, but the above person's code failed on this test and mine too.

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

      There are 5 components:

      cost 2: 2 4 10 16 2 6
      cost 3: 3 21 30
      3 of cost 12: 17, 20, 16
      

      So cost of all is 5*2 + 2*3 + 4*12 == 64

      How to get 55?

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

    Let's say you have a testcase like this:

    1
    3 1000
    2 6 3
    

    Your algorithm connects 2 to 6, then doesn't connect 6 to 3. This can be fixed simply by using DSU instead of your vis[] array.

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

    I made the same mistake and realized it after contest. Think of the following p=10 2 4 6 3

    here 2 will connect 4 and 6 and 3 will be connected to(2,4,6) by p=10 in your case but the better way will be to connect 3 to (2,4,6) by the edge of weight 3.

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

    Yeah, there's a catch out there! Notice that every time you're trying to connect your current index to some node on the left or right, you're checking if the left or right has already been considered or not! Now, consider the case like array [2,6,3]. Your algorithm will start from the first node and mark both 2 and 6 as connected So when you try to connect 3 to 6 (as 3 is the gcd of [3,6]), your algorithm denies saying that 6 is already visited! Now you can observe that the accepted codes have incorporated a slight change that allowed every node to be considered by potential values both on the left and right. An easy way out is always the DSU method, and when you wanna avoid that, you need to be careful about the components! So yeah one possible input is:
    1
    3 100
    2 6 3

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

I just don't get it, why my solution of C fails with TL. Looks like some very dumb mistake, which I don't see.

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        long long ans2 = 0;
        while (n > 0) {
            ans2 += cache2[m][n % 10];
            n /= 10;
        }
        cout << ans2 % mod << endl;
    }

This is the main part. The rest of the code is precomputation that doesn't depend on inputs and takes just 124ms.

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

    try adding fast io

    tie(nullptr)
    sync_with_stdio(false);

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

      Yep, that was the issue. Got AC with 327ms

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

    I got same tle, then i change cin and cout to scanf and printf and it passed

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

    also you use endl, which flushes the output on each iteration, use "\n" instead

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

      Nice point! Using endl instead of "\n" takes 826ms vs 327ms

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

    Btw, had to rewrite it from python to c++ because the most natural implementation didn't fit into time limit

    Unnecessary tight time limit for D2C

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

    Slow I/O operations, i.e., cin/cout.

    Just added this to your code:

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    

    Btw, it got WA due to integer overflow: 112713355

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

https://codeforces.com/contest/1513/submission/112698905

This is my solution for Problem C. According to me, its Time Complexity is O (10 * m) which is 2 * 10 ^ 6, which is very well for 1 second, I believe. It is giving TLE verdict on pretest 3.

What can be the possible reason behind this ?

Thank you !

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

    every time you count dp again

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

    Its O(10*m*t)

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

      I believe time limit per test case is 1 second, so why is t being included in Time Complexity ?

      Correct me if I am wrong.

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

        Each test includes t test cases. Time limit for ALL t test cases is 1s

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

    You are given t <= 200000

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

    The time complexity of your solution is O(t*10*m) which can be around 10^11 in worst case. So, it is giving TLE.

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

    Just precalculate the dp once instead of calculating it every time.

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

Could somebody tell me how to do E and F :<? Thanks <3

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

    For E, we want to reach $$$\frac{sum}{n}$$$ as the value of all elements. Lets call this the $$$\textbf{good}$$$ value of the array, all elements smaller than it as $$$\textbf{low}$$$ elements and all elements larger than it $$$\textbf{high}$$$ elements.

    Clearly a high element can never be made less than good, as it can never be used later as a sink (due to step 4), meaning we can never make it good. Same for low elements and greater than x. For the same reason, good elements can never be used in an operation.

    Now lets notice that if there exists any subsequence of the form $$$\textbf{low high low high}$$$ or $$$\textbf{low high high low}$$$ or $$$\textbf{high low low high}$$$, we can get different end costs by mapping the lows to different highs. So if there is more than 1 low and more than 1 high, we need them to all be separate, that is all lows before highs or vice versa.

    So we just want to arbitrarily choose where to place the $$$\textbf{good}$$$ elements in the array, multiply that by the number of ways of individually permuting $$$\textbf{low}$$$ and $$$\textbf{high}$$$ respectively. (and that by 2 if the array actually has $$$\textbf{low}$$$ and $$$\textbf{high}$$$ elements for the other direction)

    Ways of choosing places of good elements is clearly just $$$n \choose cnt_{good}$$$. Ways of placing low and high can be found is just multinomial theorem.

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

    In E array is balanced if sum is divisible by n and there is no subarray [x, y, x, y] where x is less than sum / n and y is greater than sum / n. You can calculate number of combinations with multinomial coefficient.

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

    Wow now that I realized I misread the problem statements. I thought i can't be source anymore :<. Wonder how many people like me and can't solve E :<?

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

      I did as well for 20 mins and asked a clarification for the sake of my sanity after seeing it was the other way around. That part is really unnatural, like you'd expect it to say $$$i$$$ and $$$j$$$ can't be used again as source and sink respectively but it says the opposite. Once you realize the reason for the condition its obvious which it is, but till then its something that's really easy to miss and should have been bolded.

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

My Submission for C got TLE on pretest 3. Afterwards, including fast I/O and changing for(auto x:s) to for(auto &x:s) ,it got passed. How?

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

    because t <= 2 * 10 ^ 5 and you code for passing system test needed for ios_base or scanf & printf

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

    The constraints were too tight:)

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

I had resubmitted my same correct solutions of first two questions later but my earlier correct solutions were skipped in system testing and my rank got changed .What can I do now?

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

    You can do nothing. That's the rule.

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

      But I had submitted same solution both times.

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

        Yes, but CF doesn't know that. And even if it does, that's literally the rule. You can't really complain about this.

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

        yeah, the one submitted later is considered even if the previous one was accepted, also I don't think codeforces lets you submit exact same solution twice.

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

          He just removed some comments of the old submission so that's kind of unfortunate.

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

    Codeforces considers the most recent submission even if the earlier one is correct:)

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

    I think codeforces doesn't allow the exact solution to submit twice. At least when upsolving.

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

problem A: here take some cheesy math! problem B: here take some more math! problem C: hold on! I got some more math!

honestly speaking, Problem set sucked! you know math you solve it easily, you suck at math you get rammed!

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

    >see numbers
    >"MATHFORCES!!!"

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

    None of the problems were related to math excluding B, besides that they include numbers and digits... C was DP, B had an observation, counting permutations was an easier part and A was just a constructive.

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

    I thought it was quite a well balanced round in terms of topic variety.

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

Could someone please provide me counter case for my submission of problem D .Test case 3 is very long.

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

    Here is a counter:

    1
    5 1000
    2 12 6 3 5
    
  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    See this comment, I think it is same problem as my code.

    The problem is, we do connect adjacent elements only if they have same gcd on both directions. But that is wrong, something like 2 6 3 gets connected for the price of 5 instead of 2+p

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

    thanks VTifand for counter case.

    thanks spookywooky.Yes it was that mistake. I corrected it.

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

The problem C and D are wonderful! Really nice round.I love it.

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

got the idea of solving C when there was only a few minutes left. tried my best to implement it but just couldn't finish in time :'(

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

https://codeforces.com/contest/1513/submission/112708303 Here is my solution for question c.. which is giving TLE.. but I suppose it's time complexity is O(m*10+t*10) in the worst case.. please explain

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

    you have long long everywhere, try to replace it with int

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

    Try to use "\n" instead of endl because endl takes a lot of time as it clears the buffer after each output

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

    Replace endl by "\n", as it takes about 500ms more

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

.

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

    What about the submission links and their usernames? Copy pasting the code doesen't help much.

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

https://codeforces.com/contest/1513/submission/112681391

Can someone please explain why I am getting TLE on this solution of C? I think the time complexity is O(m+t*log(n)) which should run well within 1 second?

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

    Same issues as in my solution, see comment https://codeforces.com/blog/entry/89520?#comment-779333

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

      Let me know why my solution is getting TLE . I have used fast I/O https://codeforces.com/contest/1513/submission/112700123

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

        You are actually do the dp 10 (or 20) times you need to. Consider that a digit x produces the same result after m steps as the digit x+1 after m-1 steps.

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

          Ya i have implemented the same

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

            No, you did not. You can get rid of this outer loop for (int k = 0; k <= 9; k++) {, would make it 10 times faster. for example see this submission

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

            U have used endl ,which itself takes too much time,in case of big test cases, just replace endl by "\n" ,u will see the time will be reduced to half of the previous execution time.

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

      Thanks. Got AC with FAST I/O. 732ms to 186 ms with printf instead of cout.

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

    try using FAST I/O statement you can go and see into my submissions your code is accepted after using FAST I/O

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

      Thanks. I didn't know about FAST I/O

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

        use scanf, printf

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

          For heavens' sake, stop using scanf and printf in c++ and don't recommend them to others. They don't belong to this language

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

Incredible contest:)a contest with decent level gradient in the questions.

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

Here I see a lot of comments related to problem C. Most have implemented using a 2d array of size [2e5]*[10].

  • I would like to share that it is possible to solve the question by 1d array of size [2e5] only.
  • No need to preprocess for all digits from 0-9.
  • You can preprocess all answers for zero, and then the answer for digit 'd' would be simply dp[m + d].

But, here you need to note that instead of precomputing till 2e5, you will have to precompute till at least 2e5+9.

You can check my submission here.

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

C is nice!!

Those who are unable to do it let me explain

lets think in this way if the number is this 023109

so if we know that after m operation what is the length if we start from "9" so if we know that after m operation what is the length if we start from "2"

so we just have to add cnt(0,m) + cnt(2,m) ..... cnt(9,m)

where cnt(x,y) denotes what is the length after y operation if we start from x

we can precompute ans for 0 to 9 for each m this wont take O(m*10*10) time complexity which satisfies our time limit

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

I am extremely disappointed with test cases of problem C of this round. I wrote a perfectly correct algo for the problem and was constantly getting TLE in testcase 3 of the problem. After the contest ended i just changed cin/cout by scanf/printf and boooom, it passed all test cases. You should avoid such test cases which show TLE just due to the way of taking I/O.

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

    I wonder how did you solve problems with large input before.

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

    You should always use fast IO (the ios_base......stuff)

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

Can anybody help me to find why my solution is wrong for problem B? Thanks in advance. https://codeforces.com/contest/1513/submission/112687504

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

    ans=(c*(c-1)*fact_table[n-2])%modu;

    Replace the above line in your code with-

    ans=(((c*(c-1))%modu)*fact_table[n-2])%modu;

    and see if it works.

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

why is my solution to B giving wrong answer? please tell. 112718984

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

    The problem is with the precedence of operators (sad). In your code, if you change this line if(a[i]&mi != mi) to this if((a[i]&mi) != mi). It will work. This kind of mistake sucks xD

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

waiting for editorial .....

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

Does anyone have an idea why is this (https://codeforces.com/contest/1513/submission/112721127) nlognlogn solution too slow?

EDIT: nvm I know where I made a mistake

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

Thanks for your effort!

Problems B, D and E are beautiful and so good in my opinion.

Problem C is just rude because of its TL, in my opinion. It's just about pre-calculation. Testcases are queries, in fact. Matrix exponentiation solution with O(1e3 * log(m) * testcases) should pass, because it is not a simulation solution anymore. Even matrix solution with O(1e3 * 2e5) pre-calculations didn't pass. Why so tight TL?

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

I saw lots of solutions for problem C with precalculating length after m operations separately for different digits. But notice that after applying 1 operation to 1 we get 2, then 3, ..., 9. This means that for example applying m operations to 7 is the same as applying m + 7 operations to 0. So, we can precalc this values for 0 only.

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

My submition is still waiting for recounting(((

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

Does somebody know why identical submission show different results?

Submission 1: https://codeforces.com/contest/1513/submission/112726786

Submission 2: https://codeforces.com/contest/1513/submission/112726577

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

    lol, because one problem is C and the other is D

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

      wow, im actually stupid, thank you

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

Memorable contest for me. I became an expert:)

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

I got this message after the contest:

Attention!

Your solution 112682833 for the problem 1513C significantly coincides with solutions IloveUless3/112679357, jamil314/112682833. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

This is my submission : https://codeforces.com/contest/1513/submission/112682833 This is the other submission : https://codeforces.com/contest/1513/submission/112679357 I don't see how that is not a coincidence! And I already got another warning in another contest for compiling in ideone (which, at that time, i did not know was a violation of rules)

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

Who experienced rollback rating for this contest? I am unrated this contest and come back to Blue? Some thing went wrong???

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

Can you guys please announce the selected random 10 contestants for a t-shirt from 100?

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

    Updated!

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

      Hey I just checked the list of top 100 participants. My name was not there, although I think that it should be there. Any specific reason?

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

        We have updated the ranklist; there is no change in ranks.

        It was an honest error from our end; sorry for the inconvenience.