Блог пользователя TheOpChicken123

Автор TheOpChicken123, история, 22 месяца назад, По-английски

Hello all, I am a 15 year old student in Singapore, and one of my biggest dreams is to qualify to participate in the IOI, if not, get a medal in it. I know a lot of you are probably looking at my grey handle and questioning this goal but I am never going to give up and I study quite a lot for it. But anyways — because of this — I have a few questions of how IOI questions compare to the questions on CodeForces.

  1. Are the type of questions that you get in IOI similar to the ones you get on CodeForces? Or is there a subset of problems in CodeForces that are similar to the IOI? Do you get more Ad Hoc questions, or more algorithm + data structure intensive questions? Are there more array questions? Graph questions? Permutations and Combinations? I am looking for more of a general answer for this, i.e. If they appear not at all, rarely, frequently, or all the time.

  2. If the types of questions that you get in IOI and CodeForces are comparable, what would the rating distribution of questions be of the 3 questions you get over 1 day (5 hours) (if it were in a CodeForces contest). Also, what would be the lowest ranking on CodeForces to be able to solve these questions within the 5 hours. For example would a high yellow coder be able to do well in IOI?

I am asking the above two questions as if CodeForces is a good website to prepare for IOI, I can assign myself goals in CodeForces that would help me achieve in IOI. For example if my CodeForces rating is a good way to measure how well I would do in IOI, I can focus on improving my CodeForces rating and solving CodeForces questions.

However, if CodeForces is not a good website, or there is a better one:

  1. What would be the best website to test my problem solving skills on? I want a website with questions which have a similar difficulty and type to the questions that one would get in the IOI.

  2. What would be the best books or articles or videos (basically anything) that you recommend for me to read/watch to learn advanced algorithms and data structure's as well as advanced problem solving. I want a book that is challenging and has a target audience of advanced competitive programmers. Note, I am currently reading cp4 book 1 by Steven and Felix Halim.

Thank you so much for answering these questions (you don't have to answer them all, maybe just one would be greatly appreciated.) I would go through IOI past papers to answer these questions myself but unfortunately I don't have enough experience to figure out the underlying concept in questions or the intended solutions by the problem author. Thanks for helping!

Теги ioi
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I have a couple of suggestions:

  • Solve problems from The CSES Problemset. It contains 300 high quality problems from varying difficulties and subjects, and is constructed in a way that teaches you more important and useful algorithms and data structures than I can count on all my 5 10 20 fingers.
  • Participate in OI style contests. that means contests like USACO, COCI, BOI, CEOI, JOI, APIO, IZHO and of course IOI (I might have even forgotten a few, look here). You don't need to be an official participant in order to compete, there are many online judges and mirrors for these contests. I would definitely recommend starting with USACO, it's divided into divisions so at each step the challenge will be 'easy' enough to be possible for you, but hard enough for you to improve by trying it.
  • About codeforces, I feel it's different from IOI in many ways, but it's still a good way to improve you CP abilities. So yea why not, try reaching a high rating, but don't do too much cf and too little OI stuff because you won't improve nearly as fast.

Hope this helps you, wish you the best of luck!

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Obviously I am no expert in this, but to me it seems that OI problems usually require more implementation than CF problems, and they can never be solved by a quick observation that has practically no coding. (On CF sometimes you can get by with little coding, example: https://codeforces.com/problemset/problem/1696/E, rated 2000, solution is 2 lines) For OI problems, I think that you have to be more methodical and precise about your observations, and can never really guess a solution like you can in CF.

»
22 месяца назад, # |
Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

CF contests and IOI are quite different in styles. For a CF contest you are usually given 5~7 problems and 2~3 hours, which is quite a short period so the tasks are designed in a way that it is possible to solve all of them (or almost all) in the contest duration (for top competitors in the world). This means that CF problems are more light-weighted and seldom require heavy implementation, especially in recent rounds. They also do not require you to have some really deep knowledge of some complex ideas. You can view CF problems as some math or algorithmic puzzles (as well as AtCoder problems, which somehow better fit the description). On the other hand, IOI-style contests often last for more than 5 hours, which is the least possible time for participants to at least come up with some fresh ideas, or implement complicated algorithms. This makes IOI problems much more difficult than CF problems. You may need to make some really awesome observations, or sweat out implementing some data structures.

I'm not saying that CF shouldn't be used for IOI preparation. In fact the last problems of most Div.1 rounds and some Div.2 rounds are quite challenging and are worth the time if you fully analyse them and come up with the solution (without reading editorials). And, as Um_nik mentions in this blog, it is just fun to participate in contests. (I strongly recommend checking that blog.)

Personally I don't know some particularly good IOI training websites. As I myself come from China, I can tell you that Chinese online judges aren't the best way to train for IOI — they aren't bad, though, with many hard problems whose solutions are considered 'mysterious' elsewhere. The not-so-good point is that they contain too many problems, and many require way too heavy implementation. Also some problems are a bit off-the-topic, that is, they require you to learn something, some technique that is never used in other CP problems. In contrast, I guess USACO and recent JOISC are best training resources. These problems are quite interesting, and meanwhile teach you a lot.

  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hello, thank you so much for your help. The blog that you linked was also very helpful in how I should learn to solve questions. Could you post a link to JOISC though as when I search it up i only find japanese websites.

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Here is the list of past JOI contests. In case you're not familiar with Chinese characters, 本選 means JOI Open, and 春合宿 means JOISC. After you click into some URL on this page (for example this), you can download the contest statements and test data. There are English statements available, but only Japanese editorials. I'm not sure if you can find English blogs about them online. But anyway, you don't often need them. Seems that by searching 'JOI' on CF there are a number of posts about that, and you can check those comments if you're really struggling with some tasks.

    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Some translations: 解説 means editorials, サンプルソース means sample implementation, 入出力データ means test data. Feel free to comment if there are still some words you don't understand.

»
22 месяца назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

I'm currently preparing for IOI since I qualify in my national olympiad and codeforces/atocder/USACO are similar to the problems I am aiming to solve (it is not the same to train for a bronze medal and training for winning IOI), so if your goal is to get bronze cofeforces/USACO/atcoder + CSES + Competitive programmer's handbook are nice resources for prectice and theory.

I would want to remember you that national olympiad may difer from IOI and if you want to qualify for IOI the first step is to study your national olympiad (what type of problems are there, heavy/light implementation...) for example the spanish olympiad tend to put a lot of interactive problems (1/5 more or less) a lot of graph problems, a impossible problem no one solve per day and 2 easy problems (5 problems in total per day, 2 days) and a real lot of math problems. Go to past national olympiad and check what to focus on!

»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I've been in CP for 6 months and participated in the Syrian and Asian Olympiad, and from what I've experienced OI style problems focus on algorithms more than CF, however CF has a lot of fun problems with brilliant ideas that can improve problem solving skills, and as Alon-Tanay suggested above participating in OI style contests can help a lot too

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

timmyfeng (orz) qualified for IOI from US and got a gold medal last year with primarily only practicing on codeforces.

It depends exactly on the style of problems for your country's selection process, but I think codeforces covers everything you need to know as long as you do enough problems on here and in past few years has higher quality problems on average than those from a bit older OI archives, which are often a bit too standard. Just make sure you do some more recent OI problems and a few OI virtual contests as well so you are familiar with OI format and strategy (in particular, how to allocate time among problems and subtasks).

Just make sure you are trying to increase the rating you practice over time and are not stuck solving too many low-rated problems, which are not too useful.