Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

chokudai's blog

By chokudai, history, 7 months ago, In English,

We will hold Sumitomo Mitsui Trust Bank Programming Contest 2019.

The point values will be 100,200,300,400,500,600.

We are looking forward to your participation!

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

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you for your participation!!! Was it easy or difficult?

Actually, for all problems (A through F), there are two or more different ways to solve. In the contest you only have to come up with one of them, but now the contest is over — it's good to find the another way to solve :)

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    I felt it was about there for a ABC level contest, a bit on the easier side.

    I really liked problem E, the solution is very elegant!

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest, Thanks!)btw, can I get penalized if I re-submit task on which I got AC?

»
7 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I want to know whether the problem statement of Problem E (Colorful Hats 2) was clear or not. (I'm writing this comment to increase the quality of future rounds)

It was written "Assuming that all these statements are correct," in the problem statements, but some people said that it implies that there are no case of contradictory statements (which means the answer is always non-zero), which is not true — but there were 7 clarifications about it. The word "assume" does not say more than assuming things.

However, we are sorry for writing somewhat unclear statement. No writer/tester noticed that there can be some people who read like this. We don’t have hundred eyes.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    Please try to have a pop-up notification next time whenever there are such clarifications. Normally in codeforces, we get a popup notification so we are able to know what has changed/clarified. BTW the contest was great for ABC.

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

    In this case, "Find the number of possible combinations of colors of the $$$N$$$ people's hats that satisfies all those statements." would have been a little clearer. (In Japanese, $$$N$$$ 人の人の帽子の色の組合せとして考えられるもののうち、すべての人の発言に矛盾しないものが何通りあるか求めてください。) However I'm not sure how it can be generalized...

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think a simple solution would be to show a sample test case that there is no solution.

    4
    0 0 0 0
    

    should do the trick

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

      It's definitely true. This subject was so well-discussed (and was also controversial) among Japanese competitive programming community, right after the contest.

      The conclusion for us was that it was a inaccuracy not to put such "zero-testcases". Initially, we thought about having three sample testcases (only three since we need to avoid sample-case esper) to help finding bugs, and one is for the answer over $$$10^9+7$$$. So the remaining two should be non-zero testcases, as we thought naturally. But this was a misjudge for us because adding one "zero-testcases" may not change the ability to do sample-case esper.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        What is sample-case esper?

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

          I mean, sample-case esper refers to the action which "successfully predicts" the regularity of the answer or the solution by looking sample-cases, without thinking why it holds.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        I guess it was well discussed by you and your brother only? It's hard to imagine that many people would engage in conversations with you on their own.

»
7 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Here's an unofficial English editorial for the contest: https://codeforces.com/blog/entry/71857

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

The virtual contest interface is very confusing. I just saw it today for the first time.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the bonus part of question D Lucky-PIN, which mentions that the problem can be solved in O(N*3) instead of O(N*1000).Any hints.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thinking in a mathematical sense,

    • No. of 1 digit unique code = No. of distinct characters in the string.

    • No. of 2 digit unique code with 'i'th digit as the 2nd digit = No. of unique 1 digit code upto 'i-1'th index.

    • No. of 3 digit unique code with 'i'th digit as the 3rd digit = No. of unique 2 digit code upto 'i-1'th index.

    Voila, we now have established a simple 3 way recurrence. DP TIME!

    Code : https://atcoder.jp/contests/sumitrust2019/submissions/8939651

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    We can iterate from 1-st to (n — 1)-th element(0-indexed) fixing middle sign of password. And also maintain two maps, which store quantity of signs to the left and to the right sides of current fixed sign. So we can construct all possible combinations of password and then insert them into set to avoid repetitions. Code: https://atcoder.jp/contests/sumitrust2019/submissions/8827548