hitch_hiker42's blog

How to lose the fear of edgy math problems (and not hate them)?
By hitch_hiker42, 4 years ago, In English

There is a class of problems that always bug me:

https://codeforces.net/problemset/problem/1263/A

https://codeforces.net/problemset/problem/1366/A

https://codeforces.net/contest/1539/problem/A

There are things common with these types of problems:

1). they usually require doing greedy casework or edgy math

2). you can sometimes force a binary search solution to pass (though it is tedious)

3). usually given as Div2 A/B (hopefully not in Div1), so you feel a little frustrated after not solving them for around 30 minutes (which sometimes results in a bad contest)

4). most of them are in the difficulty range: 900-1200

5). even after you solve these, there's a little scope for satisfaction

6). I'm a little curious about this one: some of these are written by MikeMirzayanov (probably he can explain better :p)

I hate these problems, probably because I am too lazy to do the casework or I suck at greedy or maybe the sort of math that's involved (eg: ceiling or flooring things, maybe check if the remainder is zero in the end, maybe add 1 or subtract 1?) doesn't suit my taste yet. Do you guys like these sorts of problems? If yes, can you explain what is the motivation behind them, and why you like them? I want to get rid of this feeling and get better at these types of problems.

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

Comments Comments (25)
| Write comment?
»
4 years ago, # |
  Vote: I like it +123 Vote: I do not like it

Don't try to solve every case of the problem. Try to figure out a single formula on pen and paper. It is the same situation when you try to do casework in the problem, which can be solved by a defined existing algorithm. Smart practice will work here.

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

    Usually, I don't naturally see a formula in such problems. My first ideas somehow always involve binary search.. which though feels a little overkill, but sometimes is faster to AC than struggling with coming up with a formula. Also, sometimes there's not a single formula but a few depending upon 2-3 cases. Anyway, I'll try following this during my practice. Thanks.

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

    What is smart practice?

    Edit : I am honestly asking this question, that how to practice smart. (after now reading it,I think my reply might have sounded like arrogant reply) EzioAuditoreDaFirenze

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

      Hi. First of all, it's not an arrogant reply. I was sharing my thoughts on the post and I think the author got that right. By smart practice, I mean, solve only those problems during a period in a limited time. That's how you become used to a particular type of problem. Let's stop this discussion here only.

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

        Ah another miscommunication. I was talking about my reply not your sounding arrogant. Anyways, thanks for replying. Thats helps.

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

But isn't it assumed that a person(let's say 1600+ rated ex: you) knows how to do them easily. How can someone progress in rating without knowing how to solve such problems?

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

    Being able to solve a problem and hating it are not mutually exclusive. I too dislike such problems and take slightly more time to solve them than my rating peers.

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

    Assumed by who? I don't think there is any parallel between progressing in rating and knowing how to solve a specific class of problems. You progress if you can solve a general class of problems, on average. And well, I didn't say I cannot solve them. I just struggle with them sometimes, and that's why I don't like them yet.

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

I do feel exactly as you. Although, I don't think I hate these problems because the first feeling I get by reading these problems is of scariness. In the problem A of yesterday's contest, you can see from my submissions, I submitted a Wrong Answer, just because of missing out on a simple overflow condition and brute-forced through multiple test-cases to finally find the error after 30+ minutes. And this is all after reading the problem, not finding any formula for the first 20 minutes and then eventually moving on to attempt B and C. I really get scared by these problems.

Any help would be absolutely delightful!

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

Emm... some details are bored and yukky really, and they are all in the same key.

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

1539A was weird, even some GMs had problems with it (galen_colin spent around 20 minutes: https://www.youtube.com/watch?v=mCNkeyNnTDs)

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

    I also occasionally struggle on problems like this. When I'm solving a div2A I'm looking for the one observation that makes it trivial. But in these math problems, there's not really a clever observation but just work you have to do, and you might make some mistakes in small details.

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

Luckily, they are the first problems, so you can dodge the contest, downvote the announcement and go play Dota 2.

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

.

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

Even if you hate them you can reach 3000+

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

    ko_osaga is that possible like without solving div 2A,B can any one can reach 3000+ ? but how ?

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

      Once you reach div1, only div1 rounds are rated for you, and as we all know, div1A = div2C, so if you give div1 rounds, you don't have to solve 2A/B ever! So once one reaches 2100 somehow (div2 rounds are unrated), one can move on to 3000+ without needing to solve 2A/B! XD

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

        What range of problems i have to solve to solve div 2 c,d ? like 1300Rating problems ?

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

      I mean, you don’t have to like them. I get disgusted when I see problems like what OP said. Probably most people will feel the same. Although I don’t know if the linked problems are in such kind..

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

        Yes, actually I couldn't recall many such problems when I posted but the linked ones do convey the idea more or less. I agree though that they're more on the lower end of the spectrum. This one though, is at a much higher level in my opinion: Codejam Round 1B: Broken Clock

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

          Yeah, I didn’t like that problem either. I think it’s hard to be in a position to enjoy such problems. If you focus on things you like, your skill will be generally better so you can be better at such problems too?

          → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it
I don't know
→ Reply