gyh20's blog

Codeforces Round #729 (Div. 2)
By gyh20, history, 3 years ago, In English

Hello Codeforces!

feecIe6418 and I are glad to invite you to Codeforces Round 729 (Div. 2) which will start on Jul/03/2021 16:05 (Moscow time). Note the unusual start time of the round.

The contest will last for two hours, and you will have five tasks to solve. The tasks are prepared by feecIe6418 and me. This round is rated for participants whose rating is not higher than 2099.

We would like to thank:

It's the second time we hold our contest, our previous round Codeforces Round 670 (Div. 2).

We tried our best to make the statements short and clear, pretests strong and problems interesting. We hope you like the problems!

Score distribution will be announced shortly before the round.

Score distribution: 500-1250-1500-2000-(2000+1000)

Editorial is published Editorial

Congratulation to the winners:

Div1+Div2:

1.Nilou_

2.244mhq

3.jiangly

4.Benaive

5.Ormlis

Div2:

1.Nilou_

2.Benaive

3.hehezhouyyds

4.TuNormie04

5.SoilCrystal

Spoiler
  • Vote: I like it
  • +439
  • Vote: I do not like it

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

If you are nerd who is on cf all day, lets be thankful for the resources we have ! Quick question : How ? Ez, just participate and enjoy this great round ! Wish you enjoyable contest :)

Also, as a person involved in testing, I can assure that problems are interesting with statement being kept short and crisp. Make sure you register :)

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

    how to become a tester?

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

      A common question and yet answered a lot of times. There are no rules for this. You should either be friends with setters or have experience of being a setter(the main thing is to be trustworthy).

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

    It's been a long time since (shirt and crisp) in contest. Can't wait for this!!!

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

Now I really have to say problem B was really harder than A :(

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

Nice start time for Chinese! Wish I can be purple in this round :).

→ Reply
»
3 years ago, # |
  Vote: I like it +336 Vote: I do not like it
Ah Shit, Here We Go Again
→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping not too difficult.hoping getting high score

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

you will have five tasks to solve

Neither problems nor questions, tasks seems good.

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

    Boogaboos were best.

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

    How does one "solve" a task?

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

      You complete or perform a task, and to complete a programming task you need to solve it

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

I appreciate this.

Spoiler

Hope i am able to solve B.

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

Chinese Round! But it's sad that I couldn't participate in it because of my courses TAT

→ Reply
»
3 years ago, # |
  Vote: I like it +105 Vote: I do not like it
As a tester, I'd like to say:
→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Was waiting for this contest eagerly to come back to expert

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

Chinese round means get ready for FSTs.

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

A lot of testers!!!,I am afraid of paper leak.:) kidding never mind

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

Yet another codeforces contest, Yet another unusual timing contest

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

As not a tester I'm waiting really good contest with brilliant problems.

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

Wow, another Chinese round and friendly time for Chinese! I'm looking forward to problems written by feecIe6418!

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

Note the unusual start time!

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

2 hours and 5 problems ? My rating is expected to have a negative expectation value.

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

cf1

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

The best thing is the honesty between the programmers!

RESPECT!

d701bd3c2f75588c6d07b7238555c7d9

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

5 problem contest means C will be a good problem to solve.That means people will not get away with speed solving + short statements(My advantage as I am a big fan of AtCoder type problems).Can't wait for this contest to start.

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

    What are AtCoder type problems?

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

      Atcoder Is a platform similar to codeforces with problem statement not exceeding 10 lines

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

        the code does not exceed 10 lines as well

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

Nice start time (for UEFA Euro :) )

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

I love codeforces!

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

Hope to have a good experience.

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

At your last round, I became master for the first time. I hope I will become again tomorrow.

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

Strange 38 Comments Done but Nowhere I can See 1-Gon.

PS: Not Tagging him he might be busy it seems :-)

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

    He is probably busy taking over the CF Empire.

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

      Mono-Gon Empire

      Looks like a nice name. Orz

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

      And I thought he was busy setting up the Monogon Forces UI this whole time. Didn't he already take over CF?

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

        I don't think so. Not yet, at least. As he mentioned before, he is working on that. He has to beat a strong opponent like Mike, after all.

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

          Well please explain why he is the top contributor and not Mike. :\

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

            Mike's contribution is +231 and mono-gon's is +210. I guess you know that 231 is greater than 210. Mike didn't add himself to the top contributors page.

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

              Of course I did, I was simply trying to point out precisely that fact. :) Mike should add himself to the contributor list to halt the revolt.

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

                I think he doesn't add himself willingly. If I'm not wrong, he did mention it once, but I couldn't find his comment.

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

yes, with this time frame I can participate without worrying about missing EURO.

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

Hope to become expert this round!

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

I hope I will raise my rating in this contest))))))))

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

I hope to become a specialist after this round

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

My comments getting contribution after having been removed completely baffles me...

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

Cool, good start time, I think this will be my first contest, I hope I enjoy it as much as all of you.

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

Is this rated contest?

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

    This round is rated for participants whose rating is not higher than 2099.

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

Yeah! Finally a contest after a long break. :)

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

We hope the problems be interesting and balanced

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

starting my cf journey with this contest wish me luck

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

Note the unusual start time of the round.

Well, for the Euro cup, actually :>

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

Yuhao Guo is a genius prob. setter! orz

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

Looks like I am not the only one who gets distracted and uses o instead of i with that scire distribution.

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

Scire distribution.

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

    oops

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

    Seems like the authors are too excited about the contest..xD

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

      Now, after reading comments i understand why they were so excited...xD

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

Does (2000+1000) mean that E2 will be as easy as 1000?

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

What is (2000+1000) difficulty? Not the same as 3000?

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

    There are two subtasks. The first one gives you 2000 points and the second gives another 1000 points.

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

how to become cm ?

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

Coming back to participate after 5 July'19.

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

Hope my ratings increase this time.

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

Mathforces.

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

    It actually does not feel like a coding competion at all. I mean, the term "coding competion" somehow implies that the problems should be solveable using codings skills.

    With todays problems coding skills are not relevant.

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

      Don't be salty, just work on your math skills and you'll do better next time :)

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

        It is more likly I quit.

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

          They are relevant — go take edu rounds. Other problem setters will always be a hit or miss. I know personally, I will never take an Omkar round because I will never succeed in those math-y rounds, and the problems are often severely underrated in my opinion (how was Diluc 1500?)

          I think also, for someone with your experience, you should know this already.

          Your point that "coding competion somehow implies that the problems should be solveable using codings skills" is nonsense. That's like saying "physics competition somehow implies that problems should be plug and chug formulas". Get over it, physics competitions have been about manipulating algebra >10 years ago.

          I agree, math is hard. If you want to quit, go ahead. But complaining about CP in general is your own opinion and projecting it on others is lame.

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

        Why just math? We can hone our physics and chemistry skills and have corresponding rounds here.

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

          Those are empirical sciences, it's not at all the same.

          You can solve all of today's A-C without any special knowledge or tricks, you just need to look at some examples and find a pattern.

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

Problems in the contest are complete shit and very commonplace and ugly.

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

the greatest contest i have seen.

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

    why downvote me ??? brrrrr. I only said that contest is good :))

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

      When offering an opinion you are always at risk of it turning out to be an unpopular one. :)

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

anyone else buckling up for a FST on B ?

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

    yep, me. But time limit on test 2 :)))

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

      did you handle a == 1?

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

        yep, both a == 1 && b == 1. even n % b == 1. if you pass through problem B could you give me solution ?

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

          Contest is over, so all the solutions are available for you.

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

        I missed the case a==1...got infinite loop thanx for telling....99% of my solution for B was correct except a==1

        PS:Need a handful of water to die away right here.

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

    what's FST

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

Problems were nice but giving 3 problems purely based on maths is not a good idea. Many people can only solve top 3 problems and if all the top 3 problems are based on maths than how can people enjoy the round?.

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

    Since CP mainly consists of Math, problems like this should be expected. But seeing that I got obliterated by those problems today, I agree. Today's round was Math-heavy.

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

      After this round, I've made it a point to read all the questions before submitting even 1 of them. If I find so many math problems, I'll just leave instead.

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

I have seen CP contests for Russian school students. This feels like Russian Mathematics Exam for class 8 or whatever.

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

contestants eagerly waiting for the next cf round.... Chineese question setters!!! Take this maths test

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

someone plzz kill me i took 7 attempts and more than 1 hr to find out that my first submission's logic was correct on problem B but getting wrong answer due to overflow :(

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

    Well, if it is because you were using int, how about using long long everytime? If you're not doing it because of TL or ML issues then all I can say is, it is much easier to correct these errors rather than getting a WA on pretest 2.

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

      bro, I was using long long only but while storing the powers of a it overflowed. In the loop I was checking for all the powers of a but I should've break the loop when power of a becomes greater than n because then u can't reach n from that power but I kept on checking all power in which due to overflowed value it was giving wrong ans, that was my mistake :(

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

are these the good ideas they were talking about... looolllll

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

And, problemsetters, please consider that these "tell me the formular" problems are very cheater friendly.

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

    Yet we see so less number of submissions

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

      Those 3000 AC submissions of problem C are hurting me from inside was this problem that easy ?

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

        After seeing Um_nik's solution, yes. But before that, I had no idea how could do that in almost constant time.

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

          I didn't got Um_nik's solution. (Problem C)

          I didn't get the code, Ik that we need to iterate over answer and check how many numbers out of n have the answer 2, how many have answer 3, etc.

          It would be a great help if you or Um_nik can explain the implementation, I mean how he solved it?

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

            I wrote an explanation of Um_nik's solution here: https://mirror.codeforces.com/blog/entry/92410?#comment-811677

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

            I think that my solution is not different from editorial? You can also check this comment.

            The main idea is that for any sum (of non-negative integers) $$$\sum_{i=1}^{n} A_{i}$$$ it is equal to $$$\sum_{k=1}^{\infty} F_{k}$$$, where $$$F_{k}$$$ is the number of $$$A_{i} \ge k$$$. You can imagine it as follows: draw rectangles with height $$$A_{i}$$$ on 2D-plane, then $$$\sum_{i=1}^{n} A_{i}$$$ is the total area if you calculate it by columns, but also $$$\sum_{k=1}^{\infty} F_{k}$$$ is the total area if you calculate it by rows.

            In this problem it is very easy to calculate $$$F_{k}$$$ and their sum, and that's exactly what my code is doing.

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

MATHFORCES

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

Found this research paper from which C appears to have been lifted directly (?). Still can't comprehend, too tough this. Feeling dumb AF

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

"Coding requires good amount of math"

...and we took that personally! ~ today's contest setters

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

MEET AN EXPRIENCED & SHAMELESS CHEATER This is how Master_Jiraya bypasses Plagiarism testing.

i reported to codeforces and MikeMirzayanov about him from past 4 contest and he does cheating in it also and got plagiarism , thanks to u for upvote my comment so that he got punished . and today again he cheated in the contest , pls again upvote my comment ......

Master_Jiraya does cheating from starting and i reported about it to MikeMirzayanov and he got plag in last 3 rounds , he abused me in private chat becz i reported him https://ibb.co/JmhSwKL . guys show your support and again upvote my comment so he again got punished.

People like Master_Jiraya are spoiling the sport. I don't understand where would cheating take them in life. They will never get anywhere in life but always remain what they are i.e cheater. He should be banned from the platform as soon as possible . MikeMirzayanov sir pls ban him and skip his solutions .

his todays contest submission 121219128 121218241 , saw his submission timing , he submitted 2 solutions within 2 minutes , tourist your new competition ,lol and also see this dummy variables snippet to bypass the plagarism . ban this Master_Jiraya , i urges the admin of contest to help me to skip his submissions gyh20 feecIe6418

FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}FOR(i,0,ttt){ int tmp=xx[3]; xx[3]=xx[5]; xx[5]=tmp; xx[1]++;}

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

How come 2900 people solve C??!!

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

    Open OEIS.
    Stare the pattern for 30 mins.
    Write a formula based on the pattern.
    Done.

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

    i just solved this task for some small Ns in my mind and then came up with the formula

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

      can you tell me the formula?

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

        i can give you a code:

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

          goddddddddd.............

          I was thinking just like this....but I wasn't able to converge on the step to take gcd of num and i.

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

        let us now consider the number i. then those numbers that are not divisible by all numbers from 1 to i are divided by their lcm. we can calculate how much before this number i was divided by all the numbers from 1 to (i-1). let it be X(n/lcm(1...i-1). We also know how many numbers are divisible by all numbers from 1 to i (n/lcm(1...i)) = Y. then the number of numbers with i = the minimum divisor = Y-X

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

          let $$$F(i) = lcm(1,\cdots ,i)$$$.
          The number of numbers in the range $$$[1,N]$$$ with $$$i$$$ being the smallest non-divisor number is equal to $$$\lfloor N/F(i)\rfloor - \lfloor N/F(i+1)\rfloor $$$? Is this what you want to conclude?

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

            no, The number of numbers in the range [1,N] with !!i+1!! being the smallest non-divisor number is equal to ⌊N/F(i)⌋−⌊N/F(i+1)⌋

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

              Oh, yeah my bad it should be $$$i+1$$$.

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

                so did you understand the solution?

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

                  Yes, completely. I was doing the same, but the template ruined everything.

                  There was an extra MOD variable which was set to $$$998244353$$$ and I could never get correct result for large $$$n$$$ * smiles in pain *.

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

      omg bashkort > Java

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

        wtmoo why are you not purple, scam

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

          Gosh I wish there was a USACO tutor that could help me get to purple.

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

How to solve B? I know it would be some trivial shit >_<

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

    If you don't multiply by a, you can generate 1, 1 + b, 1 + 2*b etc, and all will have remainder 1.
    If you multiply once, you can generate, a, (1 + b) * a, (1 + (2*b))*a etc, and all will have remainder a % b.
    So you just need to check if there exists a^k = n (mod b) where a^k <= n.

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

    You can show that $$$n$$$ will always be of the form $$$a^x + by$$$ so you just subtract the powers of $$$a$$$ and check if the result is divisible by $$$b$$$.

    Be careful with the case where $$$a = 1$$$

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

      suppose we first multiply , then add and then again multiply will that not change the formula?

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

        No, since (x * a) === (x+b)*a (mod b) === x*a + b*a (mod b). Still, you wouldn't like to add first. Only x * a can change reminder (mod b), so check if there one equal to n%b. And beware of corner-cases like a = 1, b = 1, and/or n = 1.

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

        n will always in the form n=a^i+b*j Proof:- Let at any point n=a^x+b*y now

        1) If we multiply a — n=a*(a^x+b*y)=a^(x+1)+b*a*y = a^i+b*j (let x+1=i and a*y=j)

        2) If we add b — n=a^x+b*y+b = a^x+b*(y+1) = a^i+b*j (let y+1=j)

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

          Thanks! This proves that every number that belongs to the set can be represented as $$$a^x+by$$$.

          But how can we prove that every number that is representable as $$$a^x+by$$$ always belongs to the set? I mean, can't there be a bad pair of $$$x$$$ and $$$y$$$ values, which will result in a wrong "yes" answer?

          Edit: Now I see it myself, $$$a^x+by$$$ is just obviously reachable from 1 by first multiplying it $$$x$$$ times by $$$a$$$ and then $$$y$$$ times adding $$$b$$$. So any non-negative integer values $$$x$$$ and $$$y$$$ are good.

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

      """

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

        I fail to understand why it is giving me a TLE. plz help!. Ignore execution time checking in main(), leaving that too gives TLE.

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

          You have not checked for when a is 1. This means that when a==1 the pow will never update and it will be an endless loop.

          Also next time try using spoiler tag to hide your code.

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

        You should put your code in spoiler tags.

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

MATHSFORCES

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

I declare problem D unsolvable. This won't change even if I am presented with a solution.

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

    Would you read it?

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

      I would. But as I said, once the declaration has been made, it shall not change.

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

    I came up with an approach which I could not fully execute because I was running low on time, but here's my idea if anyone is willing to try it out.

    Instead of trying out every single subset, let's just consider the probability of a number being included in the final result and then add $$$P(i) \cdot Total \cdot val[i]$$$ to the result, where $$$P(i)$$$ is the probability of its presence, $$$Total$$$ is the number of subsets and $$$val[i]$$$ is the value at given place in initial array.

    By doing some DP with two states, in $$$O(N^3)$$$ we can determine the probability of $$$k$$$ lower numbers being present in the final multiset, for each $$$0 \leq k < N$$$. Could someone let me know if this approach would work?

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

      Maybe in a similar way you could count the number of times the number will appear in the final result, instead of his probability

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

    My idea was: for each + x count how many subsequences up to index i have x in the kth position. But I ran out of time working out / implementing the DP.

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

Great problems! I really enjoyed this contest. Maybe a bit math-heavy, but I like that.

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

Problem B Had me :)

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

Task C was quite similar to Problem 2 of the 3rd level of the Argentinian Regional Mathematical Olympiad 2012

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

math & dp round:(

$$$10^9+7,998244353,mod,mod$$$

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

L.O.L problem D with repeated value is kind of hard to understand, can anyone show me how to deal with this situation? (sorry for my bad en).

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

    You can just assume that operation — removes minimal number with first occurence, so all numbers will be unique.

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

    You can just make everything be distinct values. Instead using $$$A[i]$$$, you can use the ordered pair $$$(A[i],i)$$$. Now everything is distinct.

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

Great contest! Thank you feecIe6418 gyh20.

Did you like the questions too?

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

I regret giving this contest :)

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

International Codeforces Maths Olympiad !!!!!

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

I hope the person who set limits for E stubs his toe.

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

    And ofcourse, code passes with pragmas -_-

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

      as expiation you should stub your toe

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

      What does it actually do? Is it something that one should use in generic template or can it also have bad influence on something?

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

        No clue. I just know it makes code faster sometimes.

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

Was D a dp problem? I could not figure out the states for like an hour and half :(

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

    I came up with something but was struck at a point if we maintain for every index the minimums possible with their count we can add that to the answer in case of '+' case. But I am struck with the '-' case, we can only track the minimums, but in '-' case we have to expose the second minimum, but I don't have track of that :(

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

    I did Problem D it with dp.

    I mark - with -1 and + x with x in an array. We chose one position check with num[check]!=-1 which we are going to check now: what will be the final contribution of only this number to the answer. We replace all other numbers in the array. If the number is less than num[check] we replace it with S. If the number is more than num[check] we replace it with G. It it is same as num[check] we replace it with S if it is before check and with G if it is after check.

    Now we start a 2D-dp dp[pos][S]. We will check the positions from left to right and the dp counts for position pos how many S we still have, S beingt the amount of numbers smaller than num[check]. num[check] itself also gets added to S at position check. If we passed position check then all num[pos>check][0] are set to 0, because we lost our num[check], it can't contribute anymore.

    In the end we sum all dp[n][S] over S and multiply it with num[check]. Repeat for all positions check and we got our answer.

    My submission: 121349216

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

      Thanks for the explanation!

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

      Can you please explain again what exactly does the dp state dp[pos][S] implies? For example, what will dp[4][3] mean?

      Also, why did you say that for pos>check, num[pos][0] = 0?

      Thanks.

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

        I got an image for you:

        You always add following the the arrows. The blue arrows mark not taking the number. It doesn't change S. There are no blue arrows to $$$+5$$$ because we need to take it. Red arrows decrease S on - or keep it equal, if we are at S=0 (see on thefirst -), increase it on S and don't change it on G.

        If we take +5 at some point and later S gets reduced to 0 then we have lost the +5. Thats why we delete the values in the red fields.

        In this example dp[4][2]=2 means, at position 4 (the second -) there are 2 subsequences of $$$[-,S,+5,-]$$$ such that we have 2 Elements in our set and we haven't los our +5 yet. Those subsequences are $$$[-,S,+5]$$$ and $$$[S,+5]$$$.

        Hope this helps!

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

          Thanks a lot man, this makes sense.

          For the extra case of num[pos][0] = 0 for pos>check, I think you need not explicitly write that, as the algorithm will take care of it.

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

            How will it take care of it? If I wouldn't do that, e.g. dp[5][1] would take contribution from dp[4][0] which it mustn't! I'm going to add an arrow there in an edit.

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

      How long did it took you to understand a statement?

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

      What are S and G?

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

        oh got it...smaller or greater?

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

          Yes exactly. I'm going to post a visual example later to explain more in detail.

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

            Thanks a lot!

            Can you also share how you got good at dp, as I have read your dp solution to the problem "Armchairs" and it was really good?

            And where you practice dp from? Thanks again.

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

              There's no recipe for this. Keep practicing and keep doing maths. :)

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

            Where will you post the visual explanation? In the editorial blog?

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

    Yes, it is. Let C[i][j][k] be the number of subsequences of S up to index i such that the jth value is/would be the k-th highest element in the multiset. Then the answer is the sum of S[j] * C[n][j][k] for all j and k.

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

how to solve problem B ?

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

    a(x + b) = ax + ab

    therefore if n is in the set, n = a^k + mb.

    for all a^k <= n check if (n - a^k) mod b = 0, if so then return Yes.

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

      i don't understand n = a^k + mb. you can again explain

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

        Every Number will be of the form:

        according to allowed operations ((((((1*a^n1 + m1.b)a^n2 + m2.b)a^n3 + m3b)....)

        So if u expand it it becomes: a^K + Lb = n.

        I figured it out very late I was foolishly trying to solve the expanded polynomial.

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

A, B & C are solved in less than half an hour and only 3 problems are solved in 2 hours :(

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

    i solved A in 2 minute. and only 1 problem solved in 2 hours.

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

    i solved A in 1 min. nothing in next 2 hrs I was approaching C taking 2 for all odd and 3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19 factorial for even can anyone tell what wrong in approach

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

      you have to take lcm instead of factorial.. i was also doing same mistake earlier. consider f(12) ans is 5 for this.

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

This is not a contest for begineer.

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

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

What was that C ? I came up with a lot of stuff but all led to inclusion exclusion which I am very weak at. This round made me love and hate math.

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

    $$$f(i) = x$$$ means that $$$i$$$ is divisble by $$$(x-1)!$$$ and not divisible by $$$x$$$. let $$$ans_i = n/lcm(1, 2, ..., i)$$$, start from end and subtract $$$ans_j$$$ from $$$ans_i$$$ where $$$(i < j)$$$ and add $$$ans_i * (i+1)$$$ to the answer.

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

how to solve C?

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

    If you plot out the first few terms of $$$f(k)$$$, you notice that the sequence is "almost" periodic:

    $$$\mathbf{2}, \mathbf{3}, 2, 3, 2, \mathbf{4}, 2, 3, 2, 3, 2, \mathbf{5}, \ldots $$$

    The changes to the pattern are at certain threshold indices $$$t_k = 1, 2, 6, 12, 60, \ldots $$$. These are precisely the values $$$\text{lcm}(1, 2, \ldots, k)$$$ where value $$$k$$$ appears for the first time.

    Let $$$r_k = t_k / t_{k-1}$$$ and $$$g(n) = \sum_{k=1}^{n}{f(k)}$$$. Then we can use the pattern we noticed to compute the sums for each threshold:

    $$$g(t_k) = r_k \cdot g(t_{k-1}) + f(t_k) - f(t_{k-1})$$$

    In other words, the sequence up to $t_{k-1}$ repeats itself $$$r_k$$$ times up to $$$t_k$$$, except $$$f(t_k)$$$ is different.

    Suppose $$$t_k < n < t_{k+1}$$$. Then we can observe that:

    $$$g(n) = g(t_k) + g(n - t_k)$$$

    Using these two formulas we can efficiently compute $g(n)$ for any $$$n$$$.

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

      Ok, how do people solve it in 3 (or even 10) minutes though?

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

        If I knew that, I'd have a higher rating. :) It took me about 30 minutes with the above approach. I can see that Um_nik found a brilliant solution which is way simpler to implement.

        Suppose $$$f(n) = i$$$. Then we know that $$$n$$$ is a multiple of $$$t_k = \text{lcm}(1, ..., k)$$$ for all $$$0 \le k \lt i$$$ (letting $$$t_0 = 1$$$). In fact, we can express $$$f(n)$$$ as the count of these divisors $$$t_k$$$:

        $$$f(n) = \sum_{k : t_k \mid n}{1}$$$

        So to compute $g(n)$, we can just count up the multiples of $$$t_0, t_1, t_2, \ldots$$$ up to $$$n$$$. This can be expressed as:

        $$$g(n) = \sum_{k : t_k \le n}{\left\lfloor{\frac{n}{t_k}}\right\rfloor}$$$
        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I didn't get this line Then we know that n is a multiple of tk=lcm(1,...,k) for all k<i. Can you elaborate the process please.

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

            If $$$n$$$ is a multiple of all of $$$1, \ldots, i$$$ then it is a multiple of $$$1, \ldots, k$$$ for all $$$k < i$$$. And if a number is multiple of some set of numbers, then it is a multiple of their $$$\text{lcm}$$$.

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

I love how they used A to lure participants XD

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

How to solve C ? I found this on OEIS but not able to solve it. Thanks.

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

    let us now consider the number i. then those numbers that are not divisible by all numbers from 1 to i are divided by their lcm. we can calculate how much before this number i was divided by all the numbers from 1 to (i-1). let it be X(n/lcm(1...i-1). We also know how many numbers are divisible by all numbers from 1 to i (n/lcm(1...i)) = Y. then the number of numbers with i = the minimum divisor = Y-X

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

I don't know why I am getting TLE in question B.

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

    Because n might be a + 10000000*b for example.

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

      The only line describing each test case contains three integers n, a, b (1≤n,a,b≤10^9) separated by a single space.

      Shit,I thought n<=10^9.

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

        you thought correctly

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

        n is less than 10^9, and the n I showed is not necessarily bigger than 10^9 (what if a={prime around 10^8} and b=1?).

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

          I get it.The loop will run many times.

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

            Its called time complexity. Amazing concept.

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

CountingForces

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

problems were more like trashes ! it took away all the fun during contest ! what's the point to arrange a online contest based on these trashes ?

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

First 15 mins submissions account to 55% of total submissions. Difficulty transition from B to C was high enough.

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

Out of curiosity: why do most people dislike mathforces?

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

    Because it's hit or miss for many people.

    For example,
    1. In B, I failed to observe that a^n(a^m(1+k*b)+l*b) is actually in the form a^p + q*b.
    2. In C, I failed to observe that multiples of lcm(1..x) can give result for x+1.

    Any tips regarding how to not miss these observations?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +41 Vote: I do not like it
      1. Factor out $$$a$$$ or $$$b$$$ / manipulate the expression. The final expression should be as simple as possible.
      2. "Contribution to the answer": how many times does $$$x$$$ appear in the sum?

      Btw I think that most greedy observations are more "hit and miss" than mathforces.

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

        Regarding 2, I thought along that line but couldn't come to the conclusion that lcm could be used. I was actually thinking with inclusion-exclusion principle for some reason. :(

        Yeah, greedy observations (especially game theory based) are the most difficult for me at least.

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

      for C I don't think such observation is needed. I just observed that product of $$$1^{st}\,\,14$$$ primes is greater than $$$10^{16}$$$. So I wrote a brute force solution with time complexity $$$O(14*log(10^{16}))$$$. One more trivial observation will be if $$$f(i)=x$$$ then $$$x=p^k,\,k>0$$$ otherwise if $$$x=p^{k1}q^{k2}$$$ then we can always find some $$$j<k1$$$ or $$$k2$$$ such that $$$p^j$$$ or $$$q^j$$$ does not divide $$$i$$$. . Now you have to just implement it. You can see my submission if you want it should be understandable.

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


 i couldn't get the modulo correct, help guys,

 for 10000000000000000, i am getting 807500006, while the answer is 366580019.





 ll x = n/6;

 ll ans = 0;

 if(x > 0) ans = (ans + ((x%MOD * 12%MOD)%MOD))%MOD;

 if(x > 0) {
    if(x%2) {
       ans = (ans + (((x/2)+1) * 4));
       ans = (ans + (x/2) * 5);   
    }   

    else {
          ans = (ans + ((x/2)*4));
          ans = (ans + ((x/2)*5));
    }
 }

 if(n%6 == 1) ans = (ans%MOD + 2)%MOD;
 else if(n%6 == 2) ans = (ans%MOD + 5)%MOD;
 else if(n%6 == 3) ans = (ans%MOD + 7)%MOD;
 else if(n%6 == 4) ans = (ans%MOD + 10)%MOD;
 else if(n%6 == 5) ans = (ans%MOD + 12)%MOD;

 cout << (ans%MOD)%MOD << "\n";
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The logic is wrong. For example, $$$f(12) = 5$$$, not $$$4$$$.

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

      but it is 5, i've just added 4 and 5 there,

      my approach was, 2 3 2 3 2 4 2 3 2 3 2 5 .......same continues.. is it correct??

      will there be any other number than 4 and 5? im not sure

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

    solution seems buggy, try for following cases of n i.e. n = 12 n = 30 n = 27

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

The first half of the contest certainly required some mathematical maturity, but solving C was quite rewarding. I liked all the problems individually, but found it a strange choice to put B + C on the same contest and D + E on the same contest. Thank you for writing!

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

I thought that actual programming is done on CODEforces, seems like I am mistaken. My bad.

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

Why does my code TLE? I tried to cover all the corner cases...

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

    You forgot about cin.tie(NULL); ios_base::sync_with_stdio(false); /s

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

      it is in my main function. Here I have put only the solve part, testcase handling and fast (er) IO is in main function

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

        oh, then try pragmas. But without sarcasm, it TLEs because of 

                if(n%a==0){
            n/=a;
        }
        else{
            n-=b; // <- bad
        }

        Imagine if n is large and b is small, it will decrees it so many times.

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

    If n = 10^9, a = some_prime>1/2*10^9, b = 1 and t = 10^5 you'll have around 0.5*10^14 operations. Which is equivalent to TLE in 3 secs.

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

Please Correct me if I am Wrong -:

Approach -:

f(odd number) = 2; f(even number except multiple of 6) = 3; f(odd multiple of 6) = 4; f(even multiple of 6) = 5;

Now just check how many EVENs, ODDs, ODD Multiples of 6 & EVEN Multiple of 6 are there in n & simply add f() of all of them.

I was getting right answers for first five test cases, couldn't get through the modulo one T-T

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

    f(60)?

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

    In fact, I was stuck with the same problem, but sequence actually looks like this https://oeis.org/A007978 As you can see it's also containing seven somewhere. There is different solution, I guess.

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

      2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19. From these numbers, 1 number will be there. Cheers :)

      In other words, f(x) is always between [2, 19]

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

        I found that observation quickly. But how does it help to find the solution?

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

          its a nice observation, but it doesn't help. there is much more to it.

          121235927

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

        Nope. $$$2*2*2*2*3*3*5*5*7*11*13*17*19=1163962800$$$ which is divisible by all the numbers in $$$[2,19]$$$

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

ProblemSolvingForces. Please, we need problems where you need to write segment tree and get ac, because calculating lcm and calculating answer modulo 998244353 is too hard and you can't solve problems like that if you didn't spend 20 years learning math.

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

    Pretty sure there are people who upvoted you because they sincerely believed what you said not realizing the sarcasm

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

Thank Writers and RIP for my rating.

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

In problem E (both E1 and E2), why were there almost no cases in which $$$mod$$$ is small? There should have been some cases that have $$$mod=10$$$, for example.

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

    Honestly, I have never seen a solution that fails neither big modulos, nor mod=1 but fails anything in-between.

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

Imagine getting 3.935sec/4.000sec on the pre-test, and having to look at "Running Test 63", "Running Test 64", ... one by one after that. MY HEART, oh my god. Untitled

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

could anyone please help me in figuring out the mistakes that I have done in building the logic of problem C, it would be a great help if anyone helps me through this. Thanks in advance! Here is my code (https://pastebin.ubuntu.com/p/vXc24T32Sh/)

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

I'm sorry, but this is not the kind of contest many people like..

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

Stop saying that the problems weren't good.Problems were really good.You are reluctant solve div-2 A B C level math problems.Come on bro!!!.Without skills in maths, you won't go a long way.in cp

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

    Tbh, this has nothing to do with how good your math level is. It's all based on: do you see it. I figured out how to do ab and c, but only because I was lucky I saw it, not because I have math skills.

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

      bro it's combination of cp and math skills.Practice in cp enables you to 'see' it.For example, in B n was in some form a^x+by...and your math skills enable you to check it.You shouldn't blame the problem setters for making this sort of problem

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

        I agree that math is indeed needed, but you can't say this is a programming contest. It felt like a math olympiad. Tell me, where are the problems where you needed data structures, algorithms, ..

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

          Codeforces certainly doesn't give math problems only in every contest.One or two contests like this is ok.And if it felt like math olympiad to you, then what would you call atcoder? Mathcoder??

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

            The last 4 contests I did contained a lot of math problems. I would be better if there were 1 math problem in this contest in the next 5 contests, instead of just putting them together.

            You also said something about atcoder, but I've never done a contest there.

            And if there are people who like these kind of contests, which I have totally no problem with, but please do it somewhere else or announce it beforehand. When people want to do a contest at Codeforces, they most likely want a contest where there will be graphs, dp,.. and most importantly: multiple solutions. Don't tell me there are many approaches for problems like these..

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

              You also said something about atcoder, but I've never done a contest there.

              AtCoder is a nice platform and their beginner contests are good for beginners. Exactly because they are easier than codeforces Div.2 and you will be almost guaranteed to solve multiple problems during a contest. Here's an announcement of their tomorrow's contest: https://mirror.codeforces.com/blog/entry/92484

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

    Stop saying that the problems weren't good.Problems were really good.

    The biggest downside of this contest was that places between 4685 and 14370 had been decided by just speed-solving a single problem A (even before cheaters removal). And this alone is very weird. The problem setters may have miscalculated something, unless the plan was to unleash their good problems on good-for-nothing audience.

    You are reluctant solve div-2 A B C level math problems.Come on bro!!!.Without skills in maths, you won't go a long way.in cp

    You did well in this contest. Congrats! But there's no need mocking the others. Hopefully the others learned from their mistakes and will show better results next time.

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

Thanks,for an amazing round!!

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

Finally back to blue

It felt like I didn't deserve to post messages for the last week and now I can post again

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

To not keep you waiting, the ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

Although the problems A, B, C were straight up math, in the end I reached purple for the first time, so tianbu orz, gyh20 orz

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

Curious as to why only a single sample was given in E. This is probably just me whining, but it could've been helpful for debugging such a bug prone problem where I can't figure out if it's a mod issue or not. I know a brute for small n takes < 5 mins to write. But those spare minutes often make the difference.

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

Felt like i was giving a Maths Contest, rather than a Programming contest.

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

Problem C explanation

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

I hope they post the editorial soon. Early editorials are good because you still have interest in the problems immediately after the contest and that's usually not the case with late editorials

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

too mathy. Bad contest/coordination.

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

In problem B, I used two approaches. One with a for loop and one with a while loop. The while loop solution got a TLE whereas the for loop one got accepted. Why might this be happening?

Solution 1 (while loop) : 121246493 Solution 2 (for loop) : 121249628

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

    I think the variable c overflows, causing an infinite loop. For the first submission, c is an integer and for the second one, it is a long long.

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

    Somehow your solution 1 the variable c is integer whereas solution 2 the variable c is long long. So multiplication overflow could be occurred on solution 1.

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

Sorry if you find the round unbalanced, we will try to make it better next time(hopefully if there will be a next time).

But here's something I want to say

I personally am not a fan of math problems(in fact I like data structures and graph theory and greedy MUCH better), and I dislike math just like many of you do.

But I wouldn't say that the problems are bad simply because they are mathy, and problem E is counting which is not particularly math, you don't need to study MO for any of these problems.

Math is a type of competitive programming, which is important for any of us to learn. You can't just judge a problem by it's type, feecIe6418 really spent his efforts when preparing the problems, you can see that every problem involves something different and something new. You don't need high leveled math, just simple math learned in middle school.

I dislike math, no matter in the past or now. Before, I considered mathy rounds as bad rounds, but I gradually understood that I didn't find the problems interesting because I didn't put myself into it. You can find something new in different problems. It doesn't matter whether it's math or not, but its quality does matter. It would have been really easier if I just simply copy a data structure problem and add some queries or change a little, or I can just join two well-known idea and make a new problem,or simply copy some problems from MO and make a constructive problem, these things are much easier than creating a "math" problem .

Don't say a problem is all about math if you find $$$mod$$$ numbers in it. Problems on counting usually focus on finding a suitable DP state or find another way to cauculate, And the problems aren't necessarily needed to be solved with polynomial technology.

We discussed the problems over and over to avoid using some well-known solutions or problems too standard. Though I don't like math and I'm not good at math, but I wouldn't call a problem "trash" if it is simply because it is a problem about math.

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

    btw, you might have to wait for the editorial. I currently can't get in contact with feecIe6418 now , maybe he has gone to bed(same as last time). I'll make sure it is published as fast as possible.

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

    loved the round, waiting for the next one lol

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

    For me a math problem is similar to "have to solve the problem by working on formulars". Else it is not a math problem.

    In this context B,C,D where such problems. (E I dont know, but E does not matter anyway, like no div2 solved it)

    My usual strategy is to recognize a math contest before submitting A, and if do so, do not submit at all. In this sense my todays error was to not check problems enough before participating. But actually it feels like I've been betrayed.

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

    Although I usually lose rating in a mathy round, I don't personally dislike mathy round. I dislike myself for being not mathy enough xD. Anyway,thank you for the challenging problems. I learnt a lot from this round.

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

Video Explanation for Problem A and B :

Problem A: https://www.youtube.com/watch?v=tWEbqar5tCA

Problem B: https://www.youtube.com/watch?v=zun-Wbr4rWk

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

Can any body tell what is wrong with this solution for problem b 121252891?

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

    In case a = 1, the answer is "Yes" if (n — 1) % b = 0, not if n % (a + b) = 0. Example: n = 5, a = 1, b = 2.

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

For C, you don't need to use the inclusion-exclusion principle in a complicated way because the sequences of multiples of lcm(1, 2, ..., i) are subsequences of one another. You can just update by the difference of the 'lowest non-divisors'. For example there are floor(n/2) terms with f(i)>=3, floor(n/6) terms with f(i)>=4, floor(n/12) terms with f(i)>=5, floor(n/60) terms with f(i) >= 7... So to count them all: 3*floor(n/2) + (4-3)*floor(n/6) + (5-4)*floor(n/12) + (7-5)*floor(n/60) ... (here if (newQ-q)*floor(n/div), start with q=3, div=2 then div = lcm(div, q)(=q*div/gcd(q, div)); q += 1 (keep incrementing if q divides div). That's for the even terms, the odd ones are just 2.

Hopefully this makes sense.

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

    you said f(i) =3,then f(i) =4 then f(i) = 5 then why not f(i) = 6 . How to know which f(i) will contribute to the answer . How you know that 6 will not come and many numbers like 6 which will not contribute to the answer . I know that that are some few numbers(including primes) . But cant really figure out which numbers are contributing to the answer ?? Can you please Teach me ?/ i am new to this all maths problems ...

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

      If x has more than one prime factor, say 6=2*3, then it wont contribute. If you say that f[i] = 6, it means that i is divisible by 2 and 3(along with 4 and 5), but not by 6. Ofcourse, this isn't possible. Hence, only powers of primes will contribute.

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

can someone tell me why in codeforces round 729 question B giving wrong answer if i write if"(n%b==1)" it gives wrong submission but for "if((n-1)%b==0)" it gives correct submission. question link-https://mirror.codeforces.com/contest/1542/problem/B

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

Unfortunately, I only finished implementing E2 after the contest :(. Oh well, here's my solution:

Consider two different permutations $$$p, q$$$ of length $$$n$$$, and say that they match on the first $$$n - i$$$ numbers for some $$$i\in [0, n - 1]$$$, and differ on the $$$n - i + 1$$$th number. WLOG $$$p$$$ is lexographically smaller than $$$q$$$. Let $$$S$$$ consist of the set of numbers in the last $$$i$$$ numbers of $$$p, q$$$, which clearly are identical. Then the difference in the number of inversions in $$$p, q$$$ only depends on the difference of the number of inversions in the last $$$i$$$ numbers of $$$p, q$$$. Say that the $$$n - i + 1$$$th number of $$$p, q$$$ are $$$j$$$th and $$$k$$$th largest elements of $$$S$$$ respectively, where we must have $$$j < k$$$. Let the last $$$i - 1$$$ elements of $$$p$$$ have $$$ij$$$ inversions and the last $$$i - 1$$$ elements of $$$q$$$ have $$$ik$$$ inversions. Then the difference in the number of inversions of $$$p$$$ and $$$q$$$ is simply $$$(j + ij) - (k + ik)$$$, and we simply need that $$$ij - ik \geq k - j + 1$$$.

Thus if we do casework on $$$i, j, k$$$, we simply need to find $$$f[i - 1][k - j + 1]$$$, the number of pairs of permutations such that they have length $$$i - 1$$$ and inversion counts differing by at least $$$k - j + 1$$$. We can iteratively build each array $$$f[i]$$$ from $$$f[i - 1]$$$ by doing casework on the newly added element in the permutations along with some simple math calculations and prefix sums. Then this overall works in $$$\mathcal O(N^3)$$$ since there are $$$\mathcal O(N^2)$$$ inversions. Note that I shift my indexing by a value $$$I$$$ so that negative indices are handled more easily.

My submission is linked here for more details. I used the solve function to calculate the number of permutations of length $$$n$$$ with exactly $$$k$$$ inversions, but it is only used for $$$n = 3$$$ as a base case, so it's not needed.

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

When will you put the editorial link ?

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

I have a solution for C without LCM, but I don't know why it gets WA on n = 1e16. I tested it with every n < 100 and it works. Can you find a mistake here?

Solution: find all the smallest numbers whos divides by the sequence of first numbers (will call them super numbers):

1 (div by 1)
2 (div by 1 and 2)
6 (div by 1, 2 and 3)
12 (div by 1, 2, 3 and 4)
60 (div by 1, 2, 3, 4 and 5)
...
*the biggest super number below n*

Then, we start choosing numbers step by step starting from the max to min. We divide n by our super number, subtract with the amount of this operation on the previous step, and then multiply this number with the first non-divide number.

j = min_dev.back();  // for 60 this is 7, for 12 is 5, for 6 is 4 etc
int x = n / values.back() - last;
out += x * j % mod;
last = n / values.back();  // values here exactly our _super numbers_ (1, 2, 6, 12, 60, 120...)

All code here: https://mirror.codeforces.com/contest/1542/submission/121259996

I had been debugging this code for the last hour of the contest, but haven't found any error.

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

This code for problem D in Java gets a TLE verdict.

java

While this direct translation to C++ gets AC with time to spare.

cpp

Does anyone know a way to optimize the Java code? or should I just take this as yet another sign to switch to C++?

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

    Make the switch! You'll thank yourself later.

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

      Sure C++ is generally faster, but you can get Java to work in almost all scenarios. In your case, one major optimization you could do to get Java to AC is to modify your sum(int a, int b) operation. Instead of using the % operation, just check if a+b exceeds MOD, subtract MOD from it. Of course, this assumes a, b < MOD in the first place.

      My submission runs in about half of the time limit by doing this: 121250179

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

        Thanks, that did help. I also remember a few other problems where this trick would have helped too.

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

Before editorial comes out, you can find solutions here: https://www.youtube.com/watch?v=QbRMPoFpDmg&ab_channel=ColinGalen

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

Will there be Chinese editorials？

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

    I think you can check luogu, some Chinese people will publish Chinese editorials on luogu.

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

      I mean, offical Chinese editorials.

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

        In general, there won't be Chinese editorials.

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

        I think luogu is probably the largest Chinese editorial. There are thousands of Chinese people discussing algorithms in luogu.

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

Nice start time for Chinese! But prblem C is really harder than B.

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

    I don't think so. I came up with the solution of C in 5 minutes, but more than 15 minutes for B.

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

    I even think D is easier than C. Should have solved D if I didn't spend 1 hour on C :)

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

Could anyone tell me the solution of Problem D? I'll appreciate it if you can give me some hints.

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

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

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

Problem A Why this code showing me WA? https://mirror.codeforces.com/contest/1542/submission/121273828

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it 
    if(n%a==0)
     {
     	pr("YES\n")
     	return;
     	
     }

    Consider the testcase

    14 7 10

    Your code will print "YES" but the answer is "NO"

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

Bye bye Expert :(

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

mathforces :(

The difficulty gap between A and B and the one between C and D are quite large :(

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

Guys, what were the difficulty levels of the problems B and C in your opinions?

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

    Based on difficulty I'd say 1300/1800

    But given that quite a lot of people solved C, I assume it will be 1300/1600

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

in the C Tutorial : "Since f(n)= i means lcm(1,2,...,i−1) ≤n " why? I don't understand this, can you explain it to me?

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

    If $$$f(n)=i$$$, then $$$n$$$ is divisible by $$$1,2,\dots i-1$$$, so $$$n$$$ must be a multiple of $$$lcm(1,2,\dots i-1)$$$, so $$$lcm(1,2,\dots i-1)\leq n$$$.

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

Anyone can help explain why ans for Div2 E2 with n=5 is 904 rather than 819?

It seems that I somehow misunderstood the description, but idk how...

A simple py program that outputs 819 for n=5:

from itertools import permutations

def invnum(p):
    ans=0
    for i in range(len(p)):
        for j in range(i+1,len(p)):
            if i<j and p[i]>p[j]:
                ans=ans+1
    return ans

def check(p, q):
    if p[0]>=q[0]:
        return False
    return invnum(p)>invnum(q)

cnt=0
l = list(permutations(range(1, 6)))
for p in l:
    for q in l:
        if check(p,q):
            cnt+=1
            #print("p=",p,' q=',q)
print(cnt)

Update: nvm, i thought the 'lexicographically smaller' do not include cases when p1=q1, because I didn't see these cases in the example with n=4.

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

→ Reply