Hazyknight's blog

View as a tester (Codeforces Round #641)
By Hazyknight, history, 4 years ago, In English

As you guys may notice, there is a big gap between Div1C and Div1D. We apologize for our inaccurate measure of the difficulty of Div1 D and Div1F1. In fact, many testers solved this problem during their VP. I think it's because CNOIers trained such kind of problems more, I mean combinatorics and counting. As you can see this round contains a lot of math things, Div1 DEF really sound like math problems. Previously, we think problems should more like this (math, finding lemma, observation) rather than graph+data structures+strings. This is because we want to do something new. In peoples mind, CN rounds usually means data structures+(graph/string/FFT) which is not interesting at all.

I discovered that many participants asked about Div2B. Honestly, I was confused as well when I was testing the round. I told this to the author but later we decide to keep that discription. This ended up in a big trouble which we haven't thought about before.

There are also some problems about the test data. System test is not strong enough and some strange code passed the final test. We notice this by checking 3 suspicious challenges. It turns out that the reason it that only the author of each problem made the data of his problem.

We will design more contests in the future. And we will try to avoid these problems. If you have anything that you want to say to us or any uncomfortable experience you encountered during the contest, just let us know.

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

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

What does VP mean? Did you think that D is of difficulty similar to other div1 combinatorics problems worth 2000 points?

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

    Virtual Participation, I guess.

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

    VP="virtual participation" Actually some testers said that Div1 D is hard but not that hard. It is maybe because CNOI always test us with combinatorics. We will try to involve testers from different places to test our round next time. Sorry for the miscalculation of the difficulty.

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

I think there should be balance in type of problems . I think most problems were based on Number Theory .Though i liked them .

If one of the first four problems was graph problem then it was nice.

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

    In fact when we prepared this round at first, it's not all number theory. But some problems had been replaced and we haven't notice this until the contest.

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

Problems were very good anyways. Thanks for the contest!

Thought I would prefer $$$n\le 100$$$ in E :(.

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

    Agree with this comment.

    Another possibility that neal suggested to me (that would make the problem much easier and less annoying) is to give the same problem but not allowing $$$T_i=0$$$ in the input.

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

      Nah, that will make this too easy. I see that you want to say "hats puzzle was nice", and it was, but solving the puzzle is not even the half of the problem.

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

        Ok, it seems to be easier than I thought to check the validity of a sequence, so I agree with you. The algorithmic part of filling in the hat colors in the main problem is interesting too.

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

I think that the only problem similar to D on CF is 951F - Company Acquisitions, and it is easier. Or maybe my solution is too complicated.

I very much liked the problems though!

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

Somebody Please explain me the problem statement of Div2 B. It seems to be easy yet I couldn't crack it..:-(

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

    An extra condition on Longest increasing subsequence. The extra condition being that for two adjacent indices i and j, (i%j) should be zero.i.e. i should be divisible by j.

    For example :- For (1,3,5,6), we can pick following sub-sequences (1,3,6),(1,3), (1,5), (1,6), (3,6).

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

    Maximize K such that you can choose index i1,i2,..ik hold ij|ij+1 and sij<sij+1

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

I thought your problems were nice, and I might think about D, E, & F more after the contest. I like your idea of adding more math and combinatorics problems; these are fun and I agree that it's nice to have a different flavor of problem sometimes.

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

Is there a good OJ for past CNOI combinatorics problems? I would like to get better at combinatorics.

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

    There are some if you can read Chinese. uoj.ac loj.ac luogu.org

    But actually I think codeforces and atcoder is enough for you. Because many CNOI problems are too hard for Expert.

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

      I haven't tried CNOI problem yet, what's the majority/average difficulty for CNOI problem in Codeforces rating?

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

        There are many levels. Basically we have NOIP as the first level of selection. Since the rules are quite different from Codeforces or ACM-ICPC(In two days we spend 3.5h to solve 3 problems each day, and each problem has many subtasks), the difficulty range is in fact quite large: the easiest are usually around 1500(just estimation), and the hardest is definetely around or more than 3000. This level includes some basic algorithms, data structures and some math.

        Then in higher levels, like the selection of province team and NOI, time is extended(5h) and there are many complicated algorithms, data structures and harder math. The average difficulty is more than 2500, and the hardest of them maybe pretty hard, even unsolvable during time of 5h.

        And then there are WC and CTSC, which are final selections of National team for IOI. In WC and CTSC things will be pretty hard, and sometimes magical because they may include some algorithms that are quite new and advanced. In this level each problem is hard.

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

          Thank you for the neat and detailed explanation and for the round yesterday.

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

      Correct man. It took 5 hrs to solve a CNOI problem and then I gave up.

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

    What's CNOI? (Sorry if its a dumb question)

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

      "(Chinese) National Olympiad in Informatics"
      Initially, I wanted to share a lmgtfy link. But no relevant results on google.

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

      I think it’s Chinese OIer, meaning the Olympic in informatics participants in China

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

    You can find most cnoi problems in English on wcipeg.com.

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

In peoples mind, CN rounds usually means data structures+(graph/string/FFT) which is not interesting at all.

I was very disappointed to see no DS in the contest. But still, the problems were quite cool. Can't wait for the solution of F2!

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

As a Chinese participants(Not an OIer), I want to thank your team for the schedule, A lot of friends of me make huge preparation for this round, some of them may even put off their homework for this round because of its good time(for GMT+8). By the way, what's your confusion about the div2B? I'm a little curious. Thank you for the great problem! I believe I will learn a lot from this round!

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

There is a saying that CN Rounds usually have more FSTs because of weak pretests...Seems like there are also many FSTs in Div.1 A&B. How do you think about this issue? (Not complaining btw)

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

    When we were testing, we focus only on the problem itself and we've test how strong the system test is. But since we haven't test whether code with some mistakes can pass the pretest (we testers didn't know which test is belong to the pretest). :(

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

    Can you explain what an 'FST' is? I am not familiar with the term. Is it short for 'Fail System Tests'?

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

What is a CN round?

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

Too much maths, too few algorithms, graphs and data structures. But overall, enjoyable problems.

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

    Prob 2A-2D was pretty good tho, and it only requires a bit of math knowledge.

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

Thanks for sharing this retrospective--weak tests are always unfortunate, but if it's any consolation, I thought the problems were all quite nice. While I agree that more math/observation-based problems should be used, I do think it is probably a bit excessive to set a round where 5/6 of the problems are mostly math--each problem was individually beautiful, but the set was a bit unbalanced.

I did find the note about testing D1D really interesting. Perhaps one way to ensure consistent contest quality is to ensure that all rounds are tested by people from several different countries. The way people train in, for example, the U.S. compared to Russia compared to China varies significantly, and incorporating feedback from competitors with a range of strengths and weaknesses seems helpful in ensuring that problemsets are balanced and fair to all competitors. (Perhaps the coordinators could help ensure that this happens by adding trusted testers from countries not represented in each individual contest's testing pool.)

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

I don't mean for this to come out wrong because I liked the problems, but saying

"Previously, we think problems should more like this (math, finding lemma, observation) rather than graph+data structures+strings. In peoples mind, CN rounds usually means data structures+(graph/string/FFT) which is not interesting at all."

Strikes me as quite questionable. It's literally saying that giving math problems is more interesting than giving computer science problems.

Again, I more or less liked the problemset (maybe a bit less now that I know the solutions), but I really don't like the stance you're taking for the types of problems that ought to be given.

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

    I don't think he is saying that computer science problems are boring ,but since every round consists those so it's interesting to sometime have rounds based on maths and lemma. Basically he was just trying for something different than what was expected and is frequent.

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

      Cf is already primarily math/combo, I don't understand why this is something new or a good thing, it would be better if there were more ds problems, as that would be a change for cf.

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

        I was answering for div 2 round since i don't about the questions of div 1. Div 2 generally contains some simple and intuitive problems for A,B,C so it was refreshing to have different kind of problems for those. Ofcourse it would have been better if D was some DS or ALGO based instead , it would have made div 2 much more interesting .

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

Even I feel this contest was vague. Having DP in Div2B, and for Div1A, you have two solutions where the implementation of one is 100 times easier than other (you can look into my submissions if needed). And lastly, why is Div1B rated 2000? I feel it was much easier than Div1A (it's just that I didn't read that problem). Overall, it was a vague contest with just maths and I am absolutely disappointed with the results.

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

    And lastly, why is Div1B rated 2000?

    When will you people learn that these are based on the people who solved it during contest time?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      1. I thought things have changed after this.
      2. Imagine swapping Div1A and Div1B. I feel we would have more submissions on the latter.
      3. There are many things that I don't know about this system yet. But if someone were to make a mistake, I would have explained it to that person in a nice and sweet manner.
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +45 Vote: I do not like it

        I'm sorry if I sounded harsh. Things have changed after (1) but as far as I understand, they are still automatic.

        I don't agree with (2). To me A seems much easier. I solved A immediately after reading, but needed to think to solve B. Actually I thought even C was easier than B.

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

          I personally agree that B was harder than both A and C. Maybe it's a matter of taste, but the observations on both A and C were much easier than the observation on B for me.

          But B is the easiest problem "in retrospect". Once the observation is spoiled for you, you can't unsee it.

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

    Having DP in Div2B

    This is ok in my opinion, it's very intuitive and probably one of the easiest forms of DP out there. A few contests ago, there was a prefix sum, quite possibly the easiest DP form, problem in Div 2B, so this isn't exactly a major issue.

    I feel it was much easier than Div1A

    I disagree with this too, for me the ordering was more like (easiest) 1A,1C,1B (hardest)

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

      Maybe that I feel it is easier because I did not read D during the contest in the hopes that I'll do C. But later when I read the problem, it immediately struck me. I guess the same thing happened with you in case of problem C. Personal opinion, it is, after all.

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

In Div2B I implemented some longest increasing subsequence where $$$S_{i+1}$$$ is divisable by $$$S_{i}$$$. Of course the statement says otherwise. Asked why I did get this wrong I would say "order of increasing numbers" was irritating, and "because Orac arranged them properly" did not help either.

What I think would had helped: A half sentence explaining why the example "...and the obtained arrangement will be beautiful."

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

    IMO the statement was a bit confusing for Div2B but later I figured it out from the sample test cases.

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

pretests for div2C were poor

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

That was a really nice contest. The problems were clear and moreover most of them are related to number theory and maths which I really like. I would love to take part in contests like this. Cheers

Is there, by any chance, you guys can make contest with problems only related to number theory mixed with other topics like graphs etc. That would be really fun tho.

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

    I didn't like that the contest was mostly number theory and mathematics. but actually i'm glad it did. It made me realize how terrible i am at Mathematics.

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

      Keep practicing mate, you’ll definitely improve your skills.

      The good thing about number theory and maths related questions that you can easily find your mistake and you have to prove your solution before submitting it and one can easily prove the correctness if he/she have practiced these types of questions.

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

Please add me as a tester in your next rounds :DD

Let me give you some reasons, i'm from Iran and i really like problem-setting/testing/coordinating and CP. I am usually available and Iran's time is very close to China's time(about 4 hour lag from Mashhad).

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

Chinese OI competitions (NOI, NOIp, CTSC...) has less conclusion problems (like div2 a,d) and similar amount of maths, include FFT, NTT and a lot more in higher levers(like div2 c), searching(like div2 e), more dp(sometimes with DS or other dp optimizations) and graph/tree (usually with a algorithm/DS). Hard Chinese problems are very hard to get AC, so we usually do 60pts or 30pts and than try to optimize it, it’s quite different from cf problems

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

Never expected to get a DP problem in Div2 B and a hard math problem in Div2 C(from the perspective of a Div2 participant) :) Quite explains the unusual duration of the round! :\ Problems were good though!

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

Guys these problems are actually the best problems I have ever seen. But, I can't still undersatnd the statement of Div2E. Please help me to understand div2E

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

I feel that the Div. 2 round was very number theory intensive. But thanks a lot nevertheless! It made me realize that I'm really terrible at number theory. Can someone give suggestions on how to gain a good mathematical background in number theory to be able to tackle problems like these?

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

    Though i did terribly bad in last 2-3 contest and got demoted to pupil, I can tell what i did to improve upon.I cant advice(I am not good enough). I did all easy problems of number theory on SPOJ. That gave me a bit confidence on number theory.

    PS: I am demotivated after last rounds performance. I hope it helps you somehow.

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

      Oh ok well, thanks for sharing! I'll try going through it. And don't worry about the rating, I'm sure you'll do great. Good luck, cheers.

      → Reply