gyh20's blog

Codeforces Round #729 (Div. 2)
By gyh20, history, 11 months 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.MiyoHijiriido

2.mhq

3.jiangly

4.Benaive

5.Ormlis

Div2:

1.MiyoHijiriido

2.Benaive

3.hehezhouyyds

4.TuNormie04

5.SoilCrystal

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

»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    how to become a tester?

    → Reply
    • »
      »
      »
      11 months 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
  • »
    »
    11 months 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
»
11 months 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
»
11 months 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
»
11 months ago, # |
  Vote: I like it +336 Vote: I do not like it
Ah Shit, Here We Go Again
→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This round promises to be amazing!

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping not too difficult.hoping getting high score

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I loved this, Thank You!

Spoiler
→ Reply
»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it -39 Vote: I do not like it

    I think 6 problems are better than 5 problems!

    Because when he puts 6 problems in two hours, he will make it easier than 5 problems in two hours!

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

    Boogaboos were best.

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

    How does one "solve" a task?

    → Reply
    • »
      »
      »
      11 months 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
»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I appreciate this.

Spoiler

Hope i am able to solve B.

→ Reply
»
11 months 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
»
11 months ago, # |
  Vote: I like it +105 Vote: I do not like it
As a tester, I'd like to say:
→ Reply
»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Was waiting for this contest eagerly to come back to expert

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

cf round 728 was almost a week ago. Excited for 729 :)

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

Chinese round means get ready for FSTs.

→ Reply
»
11 months 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
»
11 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Yet another codeforces contest, Yet another unusual timing contest

→ Reply
»
11 months 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
»
11 months 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
»
11 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Note the unusual start time!

→ Reply
»
11 months 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
»
11 months ago, # |
← Rev. 2   Vote: I like it +174 Vote: I do not like it

cf1

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

The best thing is the honesty between the programmers!

RESPECT!

d701bd3c2f75588c6d07b7238555c7d9

→ Reply
»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    What are AtCoder type problems?

    → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +49 Vote: I do not like it

        the code does not exceed 10 lines as well

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

          Code driving logic less than template size lol

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

Nice start time (for UEFA Euro :) )

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

I love codeforces!

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to have a good experience.

→ Reply
»
11 months 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
»
11 months 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
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    He is probably busy taking over the CF Empire.

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

      Mono-Gon Empire

      Looks like a nice name. Orz

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

      Isn't he supposed to do it by continuously collecting contribution?

      → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
          • »
            »
            »
            »
            »
            »
            11 months 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
            • »
              »
              »
              »
              »
              »
              »
              11 months 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
              • »
                »
                »
                »
                »
                »
                »
                »
                11 months 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
»
11 months ago, # |
  Vote: I like it -40 Vote: I do not like it

i hope question A) and B) will be from binary search :_:

→ Reply
»
11 months 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
»
11 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

excited

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

Hope to become expert this round!

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

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

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

I hope to become a specialist after this round

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

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

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wanna cross 1300 rating on this round!!

→ Reply
»
11 months 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
»
11 months ago, # |
  Vote: I like it -24 Vote: I do not like it

Is this rated contest?

→ Reply
  • »
    »
    11 months 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
»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

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

We hope the problems be interesting and balanced

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

starting my cf journey with this contest wish me luck

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

    I think you should know that others can see your colour and contest history.

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

      Ya I know. its a fresh start for me though. gave the last one way back. 4 months ago I think!

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

    Copy-pasting Same Comment since 3 contests I guess:-)

    PS: This one 4th.

    → Reply
»
11 months 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
»
11 months ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Yuhao Guo is a genius prob. setter! orz

→ Reply
»
11 months 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Scire distribution.

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

    oops

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

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

    → Reply
    • »
      »
      »
      11 months 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
»
11 months 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reading some funny blog posts before the round.

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 months 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

last time I gave your contest . it was a complete disaster for me. I guess not this time.

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

how to become cm ?

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

Coming back to participate after 5 July'19.

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

    all the best. all i can say is problems have got harder probably.

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

    And saw this shit.

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

      Can't agree more. Was this mathematics exam?

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

        Observation exam

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

        Problems and competition has gotten harder significantly in the last 1-2 years. More resources and tutorials available. Smarter people joining. You maintained expert. You are good to go. I wonder when i will reach even a specialist. Need to be more consistent but doing Leetcode lol these days.(which does not help much here)

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

Hope my ratings increase this time.

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

Mathforces.

→ Reply
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is more likly I quit.

        → Reply
        • »
          »
          »
          »
          »
          11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
»
11 months 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
»
11 months ago, # |
  Vote: I like it -30 Vote: I do not like it

the greatest contest i have seen.

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

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

    → Reply
    • »
      »
      »
      11 months 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
»
11 months ago, # |
  Vote: I like it -17 Vote: I do not like it

anyone else buckling up for a FST on B ?

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

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

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

      did you handle a == 1?

      → Reply
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
      • »
        »
        »
        »
        11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    what's FST

    → Reply
»
11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
»
11 months 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
»
11 months 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
»
11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
»
11 months ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yet we see so less number of submissions

    → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
          • »
            »
            »
            »
            »
            »
            11 months 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
            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you. I got how main idea is working.

              Thought I didn't get it still how it is used in the code. May be I need to think harder.

              Thanks a lot, again!

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

MATHFORCES

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

    I was expecting at least one such comment. You, sir, have not disappointed me.

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

When you did not had any idea then why copy pasting some random shit from maths notebook.

Destroyed the mood.

→ Reply
»
11 months 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
»
11 months 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
»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    make a blog about this. many people don't see comments.

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

How come 2900 people solve C??!!

→ Reply
  • »
    »
    11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you tell me the formula?

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

        i can give you a code:

        Spoiler
        → Reply
        • »
          »
          »
          »
          »
          11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
          • »
            »
            »
            »
            »
            »
            11 months 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
            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

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

                so did you understand the solution?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      omg bashkort > Java

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

        wtmoo why are you not purple, scam

        → Reply
        • »
          »
          »
          »
          »
          11 months 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
»
11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You explanation is nothing but an absolute beauty... Genius. I was trying to understand this very thing and kept looking in the comments but your explanation is just perfect.

      → Reply
  • »
    »
    11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was able to get this but was unable to convert this logic to code successfully.

      → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 2   Vote: I like it -38 Vote: I do not like it

      """

      → Reply
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            thanks, I have checked it initially but I forgot the case where (n-1)%b != 0. Thanks

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

        You should put your code in spoiler tags.

        → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

MATHSFORCES

→ Reply
»
11 months 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
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Would you read it?

    → Reply
    • »
      »
      »
      11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
  • »
    »
    11 months 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
»
11 months 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
»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Problem B Had me :)

→ Reply
»
11 months 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
»
11 months ago, # |
  Vote: I like it +45 Vote: I do not like it

math & dp round:(

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

→ Reply
»
11 months 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
  • »
    »
    11 months 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
  • »
    »
    11 months 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks DpForce for amzing problem

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest should be renamed as Mathforces Round #...

→ Reply
»
11 months 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
  • »
    »
    11 months ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    The problems were interesting i liked them :)

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

I regret giving this contest :)

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

help me guyss

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

International Codeforces Maths Olympiad !!!!!

→ Reply
»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    And ofcourse, code passes with pragmas -_-

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

      as expiation you should stub your toe

      → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
11 months 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
  • »
    »
    11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for the explanation!

      → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
          • »
            »
            »
            »
            »
            »
            11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How long did it took you to understand a statement?

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

      What are S and G?

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

        oh got it...smaller or greater?

        → Reply
        • »
          »
          »
          »
          »
          11 months 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
          • »
            »
            »
            »
            »
            »
            11 months 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
            • »
              »
              »
              »
              »
              »
              »
              11 months 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
          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
  • »
    »
    11 months 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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem B ?

→ Reply
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I can also write the other expression but can't think of a general form a^K + Lb = n. instead i go and check if n is divisible by a, if divisible then i reduce n by a times, if not then i reduce n by b until i get the number divisible by a, i'm really stupid , thanks for your explanation

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

            I was also trying to do similar thing but it didn't work for the last sample case given. It was giving WA.Dont I'll have to try the problem again

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

            I was also trying the same, first reducing n by a as long it is divisible, and then solving the above equation, but it gave WA

            → Reply
»
11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i solved A in 2 min 30 sec and none in 1 hour 57 min and 30 sec

      → Reply
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how u thought of lcm i was just blank after factorial not worked

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

          How I got to LCM was by observing that something that is divisible by 4 is automatically divisible by 2, as 2 is a factor of 4. So, when finding out the number for which the answer would be 5, I need it to be divisible by 2, 3, 4 and not 2 * 3 * 4, as that would include an extra 2 which is not needed, this pushed me towards thinking about LCM of (2, 3, 4) which is 12.

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

This is not a contest for begineer.

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

→ Reply
»
11 months 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
  • »
    »
    11 months 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
»
11 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone tell me the problem with my approach for Ques D

dp[i][j] denotes the answer till ith index if we strictly remove 'j' smallest elements

Our answer will be dp[n][0]

The transition goes something like

if ith char is positive -: Considering both the possibilities (taking and ignoring ith element)

dp[i][j] = dp[i-1][j] + dp[i-1][j] + pow(2,i-1-j) * A[i];

if ith char is negative -:

for j >= 0

(leaving and taking ith element)

dp[i][j] = dp[i-1][j] + dp[i-1][j+1]

Link to code https://ideone.com/CgwuKR

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

→ Reply
  • »
    »
    11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks

      → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months 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
          • »
            »
            »
            »
            »
            »
            11 months 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
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I still didn't get this approach though I read it many times, can you please explain it a little more.

          Thanks a lot!

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

I love how they used A to lure participants XD

→ Reply
»
11 months 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
  • »
    »
    11 months 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
»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you thought correctly

        → Reply
      • »
        »
        »
        »
        11 months 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
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I get it.The loop will run many times.

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

            Its called time complexity. Amazing concept.

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

CountingForces

→ Reply
»
11 months 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
»
11 months 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
»
11 months ago, # |
  Vote: I like it +126 Vote: I do not like it

Out of curiosity: why do most people dislike mathforces?

→ Reply
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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
    • »
      »
      »
      11 months 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
»
11 months 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
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      33, 82 and 73 respectively, is it correct??

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

        You can write brute force approach and validate the answers for first 1000 numbers.

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

        try to f(60) !=5 you will get your bug f(60) = 7 in your code this case handled as 5

        → Reply
»
11 months 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
»
11 months 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
»
11 months 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
  • »
    »
    11 months 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
    • »
      »
      »
      11 months 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
      • »
        »
        »
        »
        11 months 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.

        →