mac_n_cheese_pog's blog

i hate implementing
By mac_n_cheese_pog, history, 3 years ago, In English

on yesterday's contest,i cant do anything because of buggy code.i should be able to do problem c if i dont write unecessary if elses that makes my code too long and hard.can anyone help me with this problem? writing unecessary if elses and unecessary ideas is not only when contest but also at practice

  • Vote: I like it
  • -47
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

The more time you spend thinking and planning beforehand, the faster you can implement it later. Especially if you find yourself writing unnecessary code, it implies that you are writing without really being sure what you are doing. You can try writing some high level pseudocode first and then following it. It's not easy though, I often realize that I'm approaching a problem totally wrong only after I start to run tests. It can also help to be really modular and write lots of functions. Since, when you are writing a function, you are producing a piece of code that solves an easier problem that you will be more likely to implement without issues. But it will take practice.

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

    how can u reach blue? is it true that reaching blue or purple only need fast implementation and problem solving skills? im curious

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

      I just reached expert in my last contest and to reach it, yes, you pretty much just need to be able to implement solutions to simple problems quicker than others (as well as get a bit lucky with contest problems). However, keeping the expert rating is a whole different deal, and I suspect I'll likely drop back to specialist until I can consistently solve more complex problems.

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

      Kind of true, you don't need to know many algorithms and Data Structures to reach Expert. I didn't even know graphs and trees other than the absolute basics when I first touched blue. If you solve the first 3 problems quickly and solve 4th problem sometimes(depends on the contest difficulty) you can reach blue. But to do problems fast you need to have decent practice in solving problems. But let's not get too ahead of ourselves here, for purple you'll have to learn many things. Expert lasts for 300 points, that's a big range so you won't just get past so many people just by being fast.

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

Your implementation will naturally become more refined and concise as your problem solving skill expands. I remember writing over a 100 lines for easy problems when I was still new to cp, but I'm able to do the same in 1/3 — 1/4 the amount of space now.

Implementation shouldn't be a huge part of competitive programming (somewhat ironically I suppose) but it ends up making a large difference of contests -- and implementation skill helps a lot outside of cp when you're doing applied CS stuff.

If you want good examples of implementation, try looking at top people's codes who don't use macros (ecnerwala and jiangly come to mind). In particular I remember looking at their solutions and being amazed they wrote less than half the code I would for problems.

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

    how to solve problem C? i never solve 3 problems in a contest before.whenever i encounter problem C its like my ideas require self decision making (idk what it is called) but yea a code cant do something on their own.for example dp questions.as a math person(not that good but im experienced in olympiads) dp question is basically trial and error.meanwhile any programming language cant think about the optimal solution by itself.searching for dp states is like nonsense to me.so yea,as long as a code cant think about the best result by itself,i think i wont do problem C

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

      Try reading the editorial if you haven't. But this was my general (compressed) thought process for C.

      Ok so we have a string of length 10 and the answer is at most 10 meaning we can probably brute force. Let's suppose the answer ends after $$$x$$$ games. Then it's optimal to either make player 1 win as many games in the first x and player 2 win as few games in the first x and check whether player 2 can ever catch up to player 1 in the last 10 — x games -- if they can't then x is a possible answer. Of course, this works vice versa too, so we do another case where player 2 wins as much as possible and player 1 wins as few as possible. Just return the first x that we terminated after that.

      You seem to be putting too much thought process in implementation while coming up with ideas. For problems that are challenging, it's best to separate implementation completely from your thoughts/observations. Once you come up with enough to solve the problem, make sure you concretely know how to implement them (which isn't as bad as it sounds). CF is great because problems don't have much implementation compared to thinking (in general) compared to some other contests.

      → Reply