josdas's blog

Codeforces Round #316 (Div. 2)
By josdas, history, 9 years ago, translation, In English

Greetings to the Codeforces community!

Regular Codeforces round #316 for participants from the second division will take place on August 13, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my first round on Codeforces. Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD: The score distribution is standard, 500-1000-1500-2000-2500

Good luck!

UPD: Contest is finished. Thank you everyone!

Congratulations to the winners!

UPD Editorial

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

Comments Comments (149)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it -63 Vote: I do not like it

great contest :))

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

    I'd prefer 11:30 pm than 9:30 am (my local time), when I need to be in the office working.

    No reason to complain, guys — this is Internet (i.e. INTERnational NETwork) and international site. Get used to it.

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

      I almost thought Internet stands for International Network :)

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

    In my city is 00:30 pm QAQ

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

      Me,too.And I had to wake up at night to join the contest.

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

Is it rated?

please answer me for this important problem :))

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

i just don't want to see unrated paticipants as first & second & so on ...

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

get it

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

in my city is too late,it start at 00:30

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

    wo zai zhe li yong pingyin ying gai zhi you ni neng kand de dong le~

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

What about the point distribution???

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

Lets hope this round features a variety of problems with less math :P unlike the previous round

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

    Why? Math is love, Math is live!:D

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

    You won't gain anything Erilyth if all the problems are a piece of cake (except high rating).. It's better to learn something new and this doesn't mean necessarily a low rating by the way :)

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

    I'm alright with math. I just hope the problem statements are a little bit easier to understand.

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

I think the good round should include problems from different topics ... because if you are not good at a topic you can find another problem with a topic you are good at .. and this will be fair:)... but also math is very important and any programmer should be good at it.

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

I haven't solved a single good question this week. How do you guys stay motivated? Please give me tips. I love coding, but sometimes, I just don't feel like it, but that won't do. Please help :)

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

    The key is to upsolve once the competition is finished. In other words — read the editorial and solve everything you weren't able to solve during the competition. This way you learn from your mistakes and get better.

    My main motivation is that I'm getting better with each competition. When I started Codeforces I struggled to solve A and B, now I'm consistently solving C and pushing towards Div1.

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

      2 hours is a very small amount of time to think about all the 5 problems. Then editorial comes within the next hour, so, 3 hours in all. Shouldn't you spend at least a day before jumping to editorials? Besides, looking at editorials suck out the joy of solving a difficult problem! I like to give the problem a fair shot before I open editorial. Why is your method more effective than mine, can you explain?

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

        I might have expressed myself wrong. I don't look at the editorial immediately after the competition, and if I manage to get some kind of an idea (or anything to work around) within an hour or two, I try to solve it without an editorial.

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

        Let's look at it in a different way: don't you think that wasting whole day on a problem is bad, because you might spend that day on learning much more things instead of reinventing the wheel?

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

          If I can re-invent wheel, who knows what else I can invent! In terms of ratings and contest performance, I can see my method is hardly efficient......but it is so much fun! I learned DP(whatever much I know about it) almost on my own... I learned LIS in n log n on my own.... and just a few others.....

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

            I heard similar ideas from people who are performing much better than me, so the fact that your method doesn't work for you (at least so far) doesn't mean that it is bad method in general. Maybe you need more time, maybe you simply aren't trying hard enough.

            From my point of view — it may make sense when you already know all basics and you are currently working on improving some "thinking skills" or stuff like that — but at the very beginning, when you simply need to learn a lot of different stuff, it doesn't make much sense for me.

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

              I know I lose motivation easily(I don't practice hard) .....that's what my first comment was..... :/

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

      congrats you finally got into div1 !! Happy for you ! and i m experiencing the same too !

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

This will be the best contest of this week

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

I think this is the last contest of August.

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

591 unrated users and counting.. ok.

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

Hi guys! This is my first contest and I hope not the last. I hope that one day we will take part in CF-International:D GL && HF!

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

Woke up in the middle of the night, and find out that I didn't register after finishing problem A...

Cheers!

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

How to solve D?

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

E was almost exactly http://www.usaco.org/index.php?page=viewproblem2&cpid=553

Only difference was it was a rectangle, not a square...same constraints, modulo, and all.

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

too many hacks on problem B

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

The contest was really nice, especially C and E.

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

Hacking Contest!! it's very nice :D

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

Thank you josdas. Nice problem statements, and not strong pretests -> posibility to hack :)

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

This round was very interesting thanks to the 'Hacks'. I've never seen Div. 2 this passionate about hacking.

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

Did anyone solve E with hashes??

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

    How would you do it? There is too many possible paths = too many strings to hash.

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

    I tried hashing, but my solution exceeded the memory limit. In hindsight, it obviously wasn't going to work as there could be (500 * 500 / 2) ^ 2 pairs of positions, which is well over 256MB when hashed into longs.

    Did your solution work?

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

      Isn't it something like 2^500? How could you achieve (500*500/2)^2?

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

        My submission

        I kept track of two positions while running a DFS, with one starting at (0, 0) and the other at (N — 1, M — 1) and continuing until either the two positions met up in the middle or passed each other. To take care of overlapping paths, I hashed each pair of locations. There are (500 * 500 / 2) possible locations for each the first and second positions, giving a total of (500 * 500 / 2) ^ 2 possible pairs.

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

          ok, it makes sense. Though I don't see a way to improve this solution (cutting memore consumption for example).

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

Wasn't E too basic/known? At least, I have thought of the same problem a few times when I don't have what to do :D However, it was a nice contest, I liked D :)

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

For D, how to make projection of arbitrary point to arbitrary depth?

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

D has offline solution, right?

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

great contest ! thanks ":))

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

This contest had a really good difficulty curve.

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

    A,B,C easy, D,E very tough (if you never solved something similar)

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

      It's a lot better than the usual CF contests, which have ~3000, ~2000, and then ~500 solutions, because it let's beginners solve more problems than usual. Although I do agree that D and E were very tough relative to A,B, and C, moreso than usual.

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

Room topper for the first time :D

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

problem D strict time limit :/

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

    No. For D there is a O(N + Q*logN) algo. Your code is O(Q*26*logN) which should be TLE.

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

      Can you describe the basic idea of the solution? Thanks

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

        Key steps:

        • For each height, store all the nodes of that height.
        • For each query, use binary search to find the range of the nodes that is in subtree of v at height h. If you don't know how to do this, you should probably read some code (maybe FatalEagle), it is not very easy to explain this step.
        • When you know the range of nodes, you have several choices. One is to use a cummulative array, which leads to either Q*26*log or Q*(26 + log), depending on how you implement it. You can also read my code using bitmask trick for Q*log.
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +3 Vote: I do not like it

          FatalEagle got AC with Q*26*logn complexity. See 12502770
          My code with same complexity got TLE'ed. :(

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

            My solution is the same U_U , but i got TLE.

            Submission

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

            I figured that the constant is low enough so fast input should make it work (input can be very huge).

            Your solution with fast input works too: 12517730

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

              I have seen that using the upper and lower bound of C++STL directly in the main , is faster than make a function calling upper and lower bound.

              TLE

              AC

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

              I got AC by defining my array as 5*10^5 * 26 rather than 26 * 5*10^5. But for similar situation on Codechef defining like the latter one had less overhead than first one. My AC'ed submission after making these changes. 12517583
              This was the codechef ques where we had to do the opposite to get 100 points. Codechef Ques
              Not sure what is happening here. o.O

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

                You get more cache hits in the first way, since you want each letter of each level instead of each level of each letter (in which case 26 * 5*10^5 would be the better way of declaring the array).

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

              is using lower_bound/upper_bound STL faster than implementing binary search? because with the same complexity as yours, mine get TLE.. my submission

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

      mine O(Q*26*logN) solution got TLE What is correct approach though?

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

        Time Limit was weird. My code with the same O(26QlogN) complexity passes in 1980 ms . This seems unfair towards many participants .

        Link : 12513092

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

          yeah, I had same implementation with vectors and STL lower/upper_bound functions. I got TL when submitted it, and decided that it should work fine if I remove vectors and STL lower/upper_bound functions, but this did not help either. :( I do not really understand why my solution has bigger constant though :( I'd like to understand it.

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

      Very nice idea with bitwise xor's!

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

        Nevertheless, my solution similar to yours gets TL. Could you tell me why?

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

      Unnecessary strict constraint i think , a improve of a 26 constant is not a big improve in my opinion . BTW the problem was very interesting.

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

        I think you misunderstood my comment. It was NOT 26 --> log, it was 26*log --> log, which makes the program 26 time faster.

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

          oh, I think I got it. We have to use bitmasks. thanks for the hint.

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

          I mean a 26 constant improve is not a big improve in my opinion , i think a nice improve is taking for example improving n^3 to n^2 , and if someone really like improving some kind of things of contasts , there is a lot of problems in SPOJ that you can solve , i know that my algo is 26 n log n and it past pretest , but fail in system test.

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

        It's improvement big enough to distinguish solutions by time. So it is a big improvement.

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

      my O(Q*26*logN) got AC :)

      how to optimize it to O(N + Q*logN)?

      UPD: sorry my code is O( Q*( 26+ log(n) ) ), but it took about 1800 , strange!

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

        Unfortunately mine not.. To take away 26 you make xor sum on BIT,and every character is represented as a bit.

        If the answer on interval has more than two 1 bits in its binary configuration the answer is no.

        Xor helps you for parity,because 2 bits of the same (two 1's) make each other disappear.

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

        Really strange. I have the same idea. 12517064 — 967 ms.

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

    i upsolved D using this thing: "if there r no letters X in subtree of vertex V -> continue;" passed in 1300 ms

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

    http://mirror.codeforces.com/blog/entry/19753?#comment-245981

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

    Changing 26 * N array to N * 26 array gave changed TLE to AC :/

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

Haven't read B statement to the end. I can't understand what the importance to the player of which number he chooses — bigger or lesser if it gives the same probability to win...

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

Are future contests going to be scheduled on weekends? I know many of us have school starting soon.

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

    Agree x100000. These contests are in the middle of school for me at 11:00 or 11:30 AM. Would be really nice to have them on the weekends.

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

The only thing I've thought about in D was to cache the parity of all descendants of a node on all child layers in that node. This could occupy a single int per node per layer, if encoded as a bit string. However, this wouldn't be enough, since it's obviously an O(n^2) solution in terms of both memory and time, so it is definitely not feasible when n=500 000. How did you solve it?

UPD: The shortest submission 12506489 is also quite clear. I guess using a DFS clock and then binary searching on each layer is a standard technique.

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

one of my friends :

here

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

    I think i can relate to it.

    Not reading whole problem, or reading it incorrectly is a major issue for me. I don't know what happens during a contest, so i got three WA in problem A.

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

Codeforces Round #Hack (Div. 2)

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

What were the states and transitions for the problem E dp?

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

    dp[x_first][y_first][x_second][y_second], but this will TLE and ML.
    So we can convert the state into dp[x_first][x_second][len] witch is O(N ^ 3) Memory and Time.

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

      Can you please explain in a bit more detail, the DP solution for E?

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

Thank you for such a wonderful contest!

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

How did someone hack 24 solutions? can we hack people's solution from other rooms ?

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

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

    You can easily open a room and see that there are more than 24 users in a room

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

      There are 26 contestants (at least submit once) in our room, including myself, and only 23 of them pass at least a problem's pretest :)

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

        But you can hack one person more than once.

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

          Yes, so i am just pointing out that the number of users can be less than the number of hacks.

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

    you can hack a person more than once and you can hack more than one problem .

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

    Also, it's possible to hack someone's solution twice. Submit, hack, resubmit, hack. Of course, the hacks must be distinct cases because resubmitting requires the submission to pass previous hacks.

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

Why this code http://mirror.codeforces.com/contest/570/submission/12498380 passed system test ???

It should be wrong answer. For 11 6 test it will be generate garbage value.

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

    try 5 3 , it should generate garbage but it gives 4 !! can anyone explain why this happens ?

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

      Try custom invocation. Miraculously it gives correct ans for this and all other cases -_-

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

    I think compiler removed "if(l>r)" since "a" wasn't initialized anyway.

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

http://mirror.codeforces.com/contest/570/submission/12515787
Code works fine on my pc as well as [on ideone].
However, same code gives tle on codeforces for same test case of n=5. What is the reason? (http://ideone.com/G1AApF)

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

    I guess you have some bug (like checking array[-1]) and it causes undefined behaviour. Then everything could happen.

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

      I can't find it! :(

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

        E.g. here is checking s[n] — "while(s[i]=='.' && i<s.size())". Use custom invocation to debut 5th test. You can comment part of your solution and check if you still have TLE.

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

This may be a dumb question but .. is the 'problem set' page temporarily blocked during a contest ?

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

josdas Thank you for this contest , keep going :)

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

Got five successful hacks on B using the "1 1" test case.

After system tests: WA on "1 1" case.

Dammit.

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

Problem C = KISS

Keep It Simple, Stupid!

:( I never learn

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

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).

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

That moment when you make 3 problems in one hour and you realise that you did the first problem wrong because you did not analised the simple case ..... So disappointing. But still my rating raised. A positive note though.

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

thank you for contest!:)) we want Editorial fast :((

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

By the way, the second problem from here is pretty cool: http://mirror.codeforces.com/blog/entry/17291?#comment-221267 :D Seems like this was the source of my thoughts about such problem.

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

How to solve E?

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

    You will start travelling in both directions (from the upper-left to the lower-right and from the lower-right to the upper-left). For making it simpler, we can make a copy of the input matrix and rotate it on 180 degrees so we move in the same direction in both of the matrices. The dp state will be dp[row1][col1][row2] (the number of ways to reach those cells and have the same strings so far) since from this we can get col2=row1+col1-row2. We can notice that if a[row1][col1]!=b[row2][col2], then dp[row1][col1][row2]=0. Otherwise dp[row1][col1][row2]=dp[row1-1][col1][row2]+dp[row1-1][col1][row2-1]+dp[row1][col1-1][row2]+dp[row1][col1-1][row2-1] so we need the information only for row2-1 so we can store only the last two tables. You can take a look at my submission for more details, although it looks really crappy.

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

Although this may seem stupid, but can anyone explain how to solve Div2 Problem B?

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

    There are two main cases we can check:

    Either there will be more numbers between N and M, or there will be more numbers between 1 and M

    Take this set of numbers, for N = 10, M = 3

    1, 2, 3, 4, 5, 6, 7, 8, 9, 10

    M is 3^

    Notice that choosing 2 will mean you win on 1 or 2 Now look at what happens if you choose 4: You will win on any choice from 4 to 10.

    In this way, you want to choose either (m+1) or (m-1), based on what would give more winning numbers Some code might look like

    if (n — m > m — 1) print m + 1 else print m — 1

    .... and don't forget to print 1 when n = 1

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

Auto comment: topic has been updated by josdas (previous revision, new revision, compare).

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

D had a very simple offline solution too in O ( N + Q * 26 ) !! here is the link to it http://mirror.codeforces.com/contest/570/submission/12505776

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

Hi,

I can't figure out what's wrong with my solution for D... Here it is: http://mirror.codeforces.com/contest/570/submission/12521712 Please help!

→ Reply