EG0R's blog

Codeforces Round #235 (Div. 2)
By EG0R, 11 years ago, translation, In English

Hello everyone!

Codeforces Round #235 (Div. 2) will take place on March 10th at 19:30 MSK.

This is my first Codeforces round and I hope not the last one.

I'd like to thank Gerald Agapov (Gerald), Roman Rubanenko (Rubanenko), Sergey Oryshych (Oryshych) for helping me to prepare round, and Mariya Belova for translation of all problem statements into English.

Scoring: 500-1000-1500-2000-2500

GL & HF!

Top five:

  1. UESTC_XHXJ

  2. GoodByeAhu

  3. OrzSKYDEC

  4. simonlindholm

  5. angelyue

Congratulations of participant hoanglmdiv2, who solved the problem E.

Unfortunately, my fault, in the round hit the problem that was previously used on another competition. Since it does not comply Codeforces, problem E will be deleted.

English tutorial

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

Comments Comments (86)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

Hope your last (Div. 2) only contest!

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

    Only your contest (Hope. 2) last div!

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

    I think, there's 2 ways to deal with current situation with Div.2 Only contests (I mean, their low popularity) — either get rid of them at all or create Div. 3!

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

    -of-j

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

Good luck with you first round.

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

Daylight saving time begins... contest is one hour later than usual in my area : )

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

I think your contest will be very interesting!

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

It's impossible to register out-of-competition.

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

div2 only.....what a pity..

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

Bugs or new rules ? I can't take part in it out-of-competition.

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

    If it be a new rule, tonight top 100 will be new users ! God help us ...

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

      It's working now. And I think most of Div1 coders will take part in it out-of-competition.

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

      Я первое место забил уже

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

The time is too late.

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

    if ur really dedicated, then u will participate no matter what the time and place!

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

hope out from newbie.

:D

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

hope , you will arrange more div1 cntests B|

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

The contest hasn't start yet, but server is already unavailable :)

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

For problem C, if multiple such sequences are possible, can we print any of them?

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

    Yes, but i advice you to use such a function as "Ask a question" :)

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

My solution was hacked, but didn't change color to red in the table. Did anyone have the same problem?

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

What's pretest #4 for E?

I spend lots of time to pass that test and haven't make it during the contest.

E is a very nice problem by the way.

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

what is the idea of problem D?

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

    I thought of a DP : (2^18)x(18)x(100) but obviously will fail x/

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

      Why fail? Actually it works well. 5978987 — AC in 1.637.

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

        Getting TLE on 38 :(, Submission link

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

          I managed to update your solution a little bit, so it passed TL: 5990582 and then 5990630.

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

            i didnt understand, why is some people need divide it by the factorial of sums each number, and while others isnt

            my old code got tle too http://codeforces.me/contest/401/submission/6011014

            then i tried just need use 1 array, separating value of old array and new array with the numbers of bits that's on

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

              Depends on whether your DP takes care of identical digits in the same level or not ..

              for test case 2, n = 223, it has 6 possible permutations, however it has 3 distinct numbers only.

              Therefore, if you make sure not to take duplicate numbers into consideration, you won't need to divide by sum of factorials. Otherwise you do.

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

                yes, that's what i thought too, but i failed to find in their code how is they managed to do it

                for example, like the code commented below, http://codeforces.me/contest/401/submission/5984009

                i just didnt see the part which is take care of leading zero, or duplicate numbers

                maybe i need much more training reading others code

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

                  I haven't understood the whole code, but he handles that, by the fact that he only loops from (0-9) each time he makes the update on his current state of DP. And as for the Leading zero, I believe it's handled somehow using the bool lz ..

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

        Dammit :\

        5990127

        Did not expect a ~10^9 solution to pass. Wasted 15 mins to find optimisations to bring it under ~10^8

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

          You may use CUSTOM INVOCATION to test execution time of your solution, if you are not sure. Just have to choose realy "worst case". For example, my friend failed this problem today, because he tested on 112233445566778899 100 and it worked well — but m=100 isn't worst case for this problem, 'cause with it most states can't be reached — some large prime like 97 will give much harder case.

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

    dp[i0][i1][i2][i3][i4][i5][i6][i7][i8][i9][r] = the number of ways to use i[j] j' to form a number without leading zero and mod m = r

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

      dp with 11 dimensions? I like it.

      Also, look at 5988053... It's realy nice one.

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

      I tried your solution but recursively the problem i faced is how i can dynamically create a global array (array with variable like your local one ). do you have a solution for that

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

        check my submission [submission:http://codeforces.me/contest/401/submission/5984009]

        using g++ you can do this:

        int n;
cin>>n;
int a[n];
        → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it -8 Vote: I do not like it

    dp[mask][k] = amount of close numbers to n such that they are compound by digits of n that appears in mask, and are congruent k with m. Complexity is 2 ^ 18 * 10 * 100. 5987971

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

When will ratings be updated ???

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

is it just me, or had this blog post suddenly disappeared for about 5-10 minutes? i didn't see it in the home page nor in the recent actions tab (both simple and detailed)!

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

Round Statistics
P.S. Hacks stats will be published after hacks page become available.

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

I think people in china can't connect to codeforces.com without goagent anymore after this contest......

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

    Why?

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

      Because the 1st place of this contest 's name is our president......

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

        Dude, are u serious..

        Now, all of his submissions are skipped...

        I think it's really very funny

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

          i think the actual reason for that is because he had registered on CF just recently, and was found to be a Div-1 participant who created a new account just to participate in today's contest!

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

          I think it's very funny too.......

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

GoodByeAhu

Registered 7 hours ago

XiJinping

Registered 12 hours ago

OrzSKYDEC

Registered 4 days ago

Isn't it strange?

All of them are unrated and registered a few days ago.

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

    i soved one problem successfully in div 2 round 235, still my rating is unchanged(stuck at 1410). Can u please explain why?

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

    As always...

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

    Why most of the contestants in top 100 are mostly unrated? Are they div1 candidates who just register to participate with new identity?

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

@Egor, @Author I don't understand, why questions B and C were so easy, also they needed implementation only I think, C was easier than B.

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

Our great president XiJinping has taken part in this round and did a good job (rank1 in unofficial). But now I cannot find him:-)

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

    His submissions are ignored :)

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

      President Xi must be very confused: why ignore me! Though I'm a president, I have the right to fight for codeforces!

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

Problem C (div 2) should contain algorithmic problems. Problems A and B are sufficient to test implementation, simulation or simple maths.

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

    Can you please explain me the rating system used in code forces. I participated in div2 round:235 and solved first problem successfully and submitted a wrong answer for second problem . My rating before the contest was 1410 and now it has been decreased to 1318. Can you please explain this because I think my rating should have increased!! Thanks in advance.

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

      the new rating depends on your previous rating and your current contest rank (and not on number of problems solved)

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

      In Russia, man who solved 1 problem in div2 is called RAK

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

        what is RAK?

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

          it's a person with low skills, but Bredor's not adequate enough, so don't pay attention

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

TOP-4 (2, 3, 4, 5 places) were unrated and registred some hours ago... :(

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

Problem E is from a past USACO gold contest. Problem statement

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

for problem 235A ,my code is showing different answer on ideone and different answer on compiler of codeforce...why is it so?? link for my code http://codeforces.me/contest/401/submission/6013925

→ Reply