Sereja's blog

Codeforces Round #215
By Sereja, 10 years ago, translation, In English

Hello everyone!

Codeforces Round #215 will take place on Tuesday, November 26th at 19:30 MSK. This is my ninth Codeforces round and I hope not the last.

I'd like to thank Gerald, Berezin, Aksenov239, MikeMirzayanov and Cenadar for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problem point values div1: 500-1000-1500-2000-2000
Problem point values div2: 500-1000-1500-2000-2500

Gl & hf ! :)

Contest is over, thank you for participation. Sorry for mistake in problem A. Hope, that problems were interesting for you, also I hope that bugs didn't spoil your mood.
Have a nice evening! :)

Also I'd like to congratulate rng_58, he have 3010 rating now!

Tutorial.

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This Contest and previous one from the same street as Berezin said :)

When I read the previous round post I say to myself yea no recommendation for reading all problems But I found this statement

Sergii sends greetings and strongly recommend to read ALL tasks. :)

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

Why another round for Div1 takes place at Tuesday? Sadly I'm not able to take part in any round at Tuesday, I prefer Saturdays/Sundays and I think I'm not alone with that opinion.

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

Although I hate the time (19:30 MSK, means 23:30 Peking time) because it means I cannot go to bed until nearly 2:30 am, I still like taking part in the contest.... I hope more contest starting earlier...How about at noon in MSK?

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

    I think this time is chosen by considering most places in the world.

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

      But 19:30 MSK is not rational enough, because most coders don't like contests between 00:00 am and 13:00 pm, but not just between 00:00 am and 8:00 am.

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

        I agree, are there any other suitable time?

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

      right. for this is a russian website actually. thought that if the round can start a little earlier, only 30min is ok...perhaps i'm a little selfish.having contest after having supper isn't a nice thing, right?

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

Most probably last round before Dhaka site regional ... :)

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

I really like your contests than others, thanks a lot.

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

Project presentation tomorrow ... but sereja's rounds have so interesting questions that I can' leave it :)

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

    I have my last presentation for university :3! In 4 hours... Ahh Codeforces habe become a vicious fot me last week xD!

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

Damn!! Cannot participate cause of overtime at work.. Anyway, all the very best to everyone.

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

Wow! almost 3 people participated per second! (in the last 3 minutes before end of registration)

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

Hey! Your not using PHP 5.4 as you state in FAQ. Array short syntax [] causes compilation error. Update PHP or your docs.

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

I spent lots of time trying to use method mentioned here to hack submission 5246996, but failed to generate the anti-hash sequence in time.

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

Whats wrong with my code (5256546) for 367A - Сережа и алгоритм? I'counting 10e5 steps, but still get time limit exceeded?

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

    Maybe it's because you used "cout" and "scanf". I think I have read one time that "cout and cin" and "printf and scanf" can have problems when used together...

    I tried with only cin and cout, and it is accepted: http://codeforces.com/contest/367/submission/5259184

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

    Actually, its because your solution is O(n^2) and not O(n) as it looks. That's because you're calling strlen(s) in the for loop, for each iteration, which is itself O(n). Call strlen once, keep its value in a variable and use it in the for loop.

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

I can not even imagine how author come up these ideas for problems? Sereja Can you please give us some idea about how did you think about setting about these problems, so that it might be good for upcoming setters ??

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

It seems that many people got tricked when solving Problem A,Div.2.I got tricked,too.Although I found it in the last few minutes,I still lost a lot of score.I think it's a good lesson for us who want to solve the easy problems as fast as possible.Nice job,Sereja.

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

Can anybody please tell me how he solved problem C div 1? I tried to count what's the minimum required N to use K different values, so I tried to find the maximum K <= M such that the found N is less than or equal to the given N and pick the largest K costs from input, but I couldn't pass pretests.

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

    The idea is just like that ... Seems you have got the implementation wrong.

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

    F(K) is the minimum required N to use K different values. If k%2=1 => f[k]=k*(k-1)/2 + 1. If k%2=0 => f[k]=k*(k-1)/2 + k/2.

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

      What's the proof?

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

        It's about Euler path in Complete Graph. There are K vertices and a edge is a condition, you want to go through all edges. If k%2=1 => k vertices with even degree. If k%2=0 => k vertices with odd degree. You can think about it that way.

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

          During the contest it looked like a Chinese Postman problem in complete graph to me. In Euler Path edges can't be visited more than once, aren't we allowed to do that here (even in optimal solution) ?

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

            If k%2=1, all vertices have even degree so we can go through all edges and finish in start vertice. That's why f[k]=number of edge + 1 in this case. If k%2=0, we have k vertices with odd degree, so just add an edge between 2 vertices have odd degree, we add in total k/2 new edges. After that we can go through all edge but not finish in start vertice (be cause the last edge is the added edge and we already go through the original edge).So F[k]=total number of edge (new edges and original edges) for this case.

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

              Thanks, nice explanation.

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

What's the source of the problem with problem div1-A? How is it even possible to have the judge solution for the first problem in the contest fail pretests? Have you tested the problemset at all?

I only saw the announcement around ~30 minutes into the contest (since the popup opens in a random open window of CodeForces, not necessarily the one you're looking at), and spent the whole time "debugging" my A. Then at the end I missed the chance to submit D by seconds :(

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

    We had 3 solutions. All of them were wrong :( Sorry for such situation.

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

      Good thing my D TLEs anyway, I guess ;)

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

    Whole time "debugging" your A ???
    you submit it after 12 minute :) :)

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

      Yes, and it was correct, but it got WA on pretest 3 then. 3-7 minutes later, the judge solution was corrected, but I only saw the announcement about this (and that my solution now has pretests-passed) 18 minutes later.

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

why are most of the nowadays contests in Sundays or in Tuesdays? I count and find that there are about five contests in this month that they were in Sunday or Tuesday. Unfortunately I have a class these days and I lost these contests. Is it fair? I wish next contest will not be in Sunday or in Tuesday. I wish ...:) (I want to write this comment before the contest but I arrive home now!)

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

Problem B in Div 2: The question defines the sequence as "li, li + 1, ..., ln" but shouldn't this be "li, li + 1, ..., n" according to the second explanation which says "a(li), a(li + 1), ..., an" I got a WA because of this since I assumed it was "li, li+1 , ..., ln"...

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

what a good contest! :D really cool, good problems

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

Wow, the system judged very fast today.

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

Integer overflow on Problem B again ARGHHHHH

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

Finally 3000! :)

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

    Congratulations!

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

      Thank you!

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

        IT'S OVER 3000! (refer to my template: #define OVER9000 1234567890 :D)

        Yet another CF target is born.

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

    Congratulation for being second CF TARGET !!! :)

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

What a good problem A! 7 successful hacks!

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

Very interesting round, waiting for the tutorial..

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

Thanks Sereja! It's a nice round: Solutions are short and clear. And the overall difficulty is not too low as I thought (Because it has some tricks in implementation, I failed 2 tasks by it.).

Maybe we can have more rounds like this, do you think so?

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

    It is not so easy to make such rounds :) But I will try.

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

In problem Sereja and Algorithm, here the constrain is "string q, which doesn't equal to either string "zyx", "xzy", "yxz". If q doesn't contain any such subsequence, terminate the algorithm, otherwise go to step 2." But when I see the testcase then I'm confused, because answer is "YES" when q contains such substring like "zyx", "xzy", "yxz". Why? My code is AC after the contest because in contest time I was confused.

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

Div1-pB is almost as same as IIUPC 2013 pH which occured on contest of UVa Online Judge today!

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

I got AC on Sereja ans Anagrams with this code: 5261631. Yet, I am getting WA with this 5261332. This two codes are virtually same except for in one I am using

(WA) if ( good == mp.size() ) // Here mp is a map < long long, int > mp
(AC) if ( good == dif ) // Here dif = mp.size() right after inserting things in map.

The reason I am getting WA is because the size of mp changes at the end of the process. But it shouldn't since I am not inserting anything after the beginning. Can somebody explain this bizarre situation? It would suck if I ever have to face such situation during contest time!

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

    When you use map[num], it will add new element in map if num isn't already in it (example). So, if array A has some elements that B dosen't have, size of map will be changed.

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

    Run this code. May b this might help you. int main() { map<int,int>M; int sz=M.size(); cout << sz << " " << M.size() << endl; if(M[5]==1)cout << "i m not gonna print" << endl; sz=M.size(); cout << sz << " " << M.size() << endl; return 0; }

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

This is my submission of Problems B. Div 2

http://codeforces.com/contest/368/submission/5266990

I confused why the output of test 2 was different from it was on my computer and Ideone.com. Any body can help me ? Tks for all :)

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

    I test your code for test 2 it's WA your program give me 3 2 1 also it's basically seem WA can you explain your solution ?

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

      For each l[i], I put a[l[i]] into a Set in C++, and the set only holds distinct numbers, so I simply print the size of this set

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

        In your solution you're only counting the number of different integers amongst alm, alm - 1, ..., al1. Instead, the problem asks you to find the number of distinct numbers amongst ali, ali + 1, ..., an, for each of li.

        On a side note, I would discourage the use of preprocessor directives like these:

        #define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FRD(i, a, b) for(int i = a; i >= b; --i)

        Essentially, the main goal for the majority of participants here is to improve their problem solving skills. Even if less typing saves an extra 3 minutes per match for you or me, it is somewhat unlikely to make any difference. Rather than that, it's all about learning to find the solutions for increasingly harder problems in increasingly smaller amount of time. And especially if you're only beginning to practice solving programming contests, writing a clear code (without macros) will only help you to maintain a better clarity of mind.

        But that's just my own opinion. I realize some people will disagree, and at some skill level this coding "style" may become more useful.

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

          I like these macros and would recommend them. I think the code is much clearer (for the given participant, at least). Also, you'll never make a mistake like:

          for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++i) {
        // ...
    }
}

          which is really hard to find (at least, just by looking at the code).

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

Hi everybody, sorry to bother, but I don't understand why I get different outputs between the online judge and my computer

http://codeforces.com/contest/368/submission/5275044

That's my solution, and it works fine when I try it... but it doesn't seem to work in the online judge... Any ideas? :(

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

    Aren't you going out of bounds with this line, when your loop enters for the 1st time?

    arri[i] = arri[i + 1] + 1;

    so arri[i + 1] will have some random value in the memory, since you declared the array localy?

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

I think there is some problem with Problem C in DIV2 to be fixed or the changes which were made during contest are not being reflected in here !!

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

    Everything is good with the problem. Just be more careful while reading as statement can be a bit difficult to understand at first. Cost me 5 WAs before finally getting it AC. Hats off to Sereja for the problems though.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

I am confused about a testcase given for Div2-C: Sereja and Algorithm.

q=zyxxxxxxyyz (input string) s=zyxx (query substring)

The explanation for the says — "...you can get string "xzyx" on which the algorithm will terminate" However, the problem states that 'zyx' should not be present in the query string.

In fact, the permutation 'zxyx' would be allowed, but not 'xzyx'.

Am I missing something?

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

    Yes, you're making up additional constraints. There is nothing in the problem statement saying that there can't be 'zyx' present in the input string. It only states that 'zyx' won't be rearranged.

    → Reply