mtnshh's blog

By mtnshh, history, 5 weeks ago, In English

The Programming Club, IIT Indore is proud to present our flagship event, Divide By Zero! The contest will take place on Apr/11/2021 17:35 (Moscow time). 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

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

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

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

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

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

      It was joke comment.

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

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

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

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

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

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

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

              Unrated accounts now start from 0 rating.

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

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

            ur id seems to be scam 2020

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

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

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

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

why indian guy ?

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

    because IIT indore means The Indian Institutes of Technology Indore

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

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

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

        It should be The Great Indian Institute of Technology, Indore

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

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

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

      you can sell it to someone in india $

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

        Not worth the effort xD

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

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

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

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

    Also if you have problemsetted in other juries or contests you can do it.

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

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

»
5 weeks ago, # |
  Vote: I like it -78 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 ..

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

    LoL

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +27 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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +18 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 :)

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

    You got my upvote ;) good luck becoming positive

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

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

All the best everyone .... Jai Hind

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

Many indian contest recently. You guys are motivated.

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

    Naah, just population I believe xD

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

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

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

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

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

Indian round, cool

insert nationalistic comments

»
4 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

China>India

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

good to see India here.

»
4 weeks 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)))

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

mtnshh , When points distribution will be updated ??

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

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

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

    I think it is just free points.

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

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

      It were somewhat hard-earned free points for some of us

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

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

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

      It is also a common abbreviation for in my opinion.

»
4 weeks ago, # |
  Vote: I like it -47 Vote: I do not like it

SRH match appud pedtunav kada ra neechuda

»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

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

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

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

hope I remain expert after this contest :)

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

Is it rated?

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

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

wake the firck up samurai

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

Every intellectual having more than one year experience of coding when solves first and only problem of div2 thinks that becoming tourist is not hard,
An intellectual,2021

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

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

i need a t-shirt :) like them

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

The score distribution is wrong, lol

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

Why is my nlogn solution giving TLE for B? 112705441

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

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

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +68 Vote: I do not like it
  • »
    »
    4 weeks 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.
    • »
      »
      »
      4 weeks 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.

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

Can someone explain me the approach of C?

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

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

      What is the formula to that series?

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

        a[i] = 1 for i = 1 to 10 and

        a[i] = a[i — 9] + a[i — 10] for i > 10

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

      Is it cool to access oeis, during the contest ?

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

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

    Yes, let me try. I passed pretests of this problem after getting a TLE on the 2nd test.

    Let $$$c[n][i]$$$ be the number of "i" $$$0\leq i\leq 9$$$ after $$$n$$$ operations. You build the relation between $$$c[n][i]$$$ and $$$c[n-1][i]$$$; which is a 10x10 matrix A; and $$$c[n][i]$$$ can be calculated via $$$c[0][i]$$$ and $$$A^n$$$.

    So the goal is to calculate 2*10^5 matrices $$$A^k$$$ given the first matrix $$$A$$$(which is a sparse matrix).Since A is sparse, after calculating $$$A^{n-1}$$$, you can calculate $$$A^{n}$$$ in O(100) instead of O(1000). So the complexity to calculate all matrices is O(2*10^7); and I passed pretests in 888 ms.

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

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

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

ModuloForces

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

How to solve D?

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

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

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

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

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

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

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

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

            For posterity:

            ❯ g++ --version
            g++ (Ubuntu 8.4.0-1ubuntu1~18.04) 8.4.0
            Copyright (C) 2018 Free Software Foundation, Inc.
            This is free software; see the source for copying conditions.  There is NO
            warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
            
            
            ~/Desktop/competitive/codeforces/1513
            ❯ g++ 1.cpp    
            
            ~/Desktop/competitive/codeforces/1513
            ❯ ./a.out
            5
            1912 1
            5 6
            999 1
            88 2
            12 100
            5
            2
            6
            4
            2115
            
            ❯ g++  -fsanitize=undefined 1.cpp    
            
            ~/Desktop/competitive/codeforces/1513
            ❯ ./a.out
            1.cpp:52:36: runtime error: index 16 out of bounds for type 'long long int [10]'
            1.cpp:52:38: runtime error: store to address 0x55f17e832c60 with insufficient space for an object of type 'll'
            0x55f17e832c60: note: pointer points here
             00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00
            
            
»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

so hard :(

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

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

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

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

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

    For B. The observation is that a[1] = a[n] = minimum value of the array. Also, for every i, a[i] & a[1] = a[1].

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

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

Problems were hella good imo, especially D

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

how to solve b

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

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

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

i hate contest from these iit during contest but love them a lot while upsolving https://codeforces.com/contest/1513/submission/112707749 i did dp but fuck it

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

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

my Code for C runs five minutes after contest ends, end every time - C is based on recursion where you can start from state when number becomes two digit i.e. 10 and calculate what happens after k steps using dp.

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

Missed D just by a minute :(

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

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

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

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

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

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

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

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

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

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

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

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

    try adding fast io

    tie(nullptr)
    sync_with_stdio(false);

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

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

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

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

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

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

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

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

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

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

    every time you count dp again

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

    Its O(10*m*t)

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

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

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

          Ohh okay, wasn't sure about it ! Thanks a lot !

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

    You are given t <= 200000

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

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

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

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

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

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

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

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

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

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

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

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

    The constraints were too tight:)

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

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

    You can do nothing. That's the rule.

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

      But I had submitted same solution both times.

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

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

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

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

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

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

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

    >see numbers
    >"MATHFORCES!!!"

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

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

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

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

    Here is a counter:

    1
    5 1000
    2 12 6 3 5
    
  • »
    »
    4 weeks 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

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

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

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

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

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

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

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

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

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

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

Can anyone please review or suggest why my problem C solution is giving TLE? I precomputed the values and added in the sum but still test case 3 fails. Here's my solution : 112712714

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

.

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

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

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

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

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

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

          Ya i have implemented the same

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

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

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

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

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

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

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

        use scanf, printf

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

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

When can we get the editorial.

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

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

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

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

This round really awesome with some good problems but that's my bad I couldn't solve problem C.

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

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

Can anyone help me in understanding why my code failed for problem B?

I used the logic of getting the lowest element. Then there are two positions for it, so cnt[lowest_element] * (cnt[lowest_element] — 1), and then I multiplied it by fact[n-2] ( for handling various permutations of the middle elements )

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

Thank you

( edit -> linked wrong submission )

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

    You also need to check weather the AND operation of all numbers is equal to the smallest number or not. In case they are not equal than the answer is 0. (also for finding the AND of all numbers initlize the variable used for this purpose by the first element of array and not 1).

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

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

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

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

      I always used cin/cout before and it always worked for me, i realized today that they actually have some significant time difference

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

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

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

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

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

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

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

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

waiting for editorial .....

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

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

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

I just received a message about leaking of code or same solution. But I really don't know how are solutions matched . Yes by mistake I used Ideone in public mode . I accept my mistake but don't block my account this mistake will never happen again in the future

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

Editorials are on time.

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

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

My submition is still waiting for recounting(((

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

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

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

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

      wow, im actually stupid, thank you

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

If I get Wrong answer on pretest 1 then will that be counted as penalty(-50)?

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

Memorable contest for me. I became an expert:)

»
4 weeks 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)

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

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

I think it is funny!

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

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

    Updated!

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

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