Warawreh's blog

By Warawreh, 5 weeks ago, In English,

Hi, Everyone!

At Jan/20/2019 15:05 (Moscow time) will start Codeforces Round #533 (Div. 2). Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in the contest out of competition.

The round will consist of 5 problems in which you will be helping some of my friends and you will be given two hours to help them.

I would like to thank MikeMirzayanov for the Codeforces and Polygon platforms, _kun_ for round coordination and help with preparation. Also thanks to V--gLaSsH0ldEr593--V, Aleks5d,Nebuchadnezzar, Arpa, mohammedehab2002 and osaaateiasavtnl. for help with preparation and testing round.

As usual score distribution will be announced shortly before the contest.

Good luck!

UPD1: I'll be on the Discord channel after the contest, so we will be able to discuss the problems.

UPD2: Score distribution : 500-1000-1500-2000-2500

UPD3: The Editorial is ready.

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

which you will be helping 5 of my friends

What does this mean?

And also... thank you for the contest!

Also... why is the time so early?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +42 Vote: I do not like it
    • In each problem you will be asked to help one of my friends by solving the problem
    • So it does not clash with codechef cookoff
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Oh okay, thanks! Then on Sunday I guess it's

      cuz I'll be taking USACO contest too. :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I knew it!!! The date of the contest would shift as there can't be 11 days gap b/w 2 Codeforces contests.

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

    I see your comments in contest discussions, but the last contest you participated was back in Aug 2018.
    Are you one of those guys who are worried about rating drops and watch contests like a football game? :thinking:

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Why are you so angry, bro? I will give the contest once I get hold of the topic I have been practicing!!!

»
5 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

best time for the contest... i will not miss my dinner

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

its much better than 18:05 thank.

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I believe that it would be a nice round Warawreh ;)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

During this time my neighbours are very loud :(

»
5 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Oh at 2 pm I will still be in church, maybe next time then, goodluck with your contest though hope it will be a success and codeforces like its problems.

»
5 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it

I am expecting a really great round ! warawreh

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I love the original rounds like this one more than any other modified rounds! :D

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

jordanian problem setters ، so excited to this contest

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

good luck everyone ... including me :D

»
5 weeks ago, # |
Rev. 3   Vote: I like it -41 Vote: I do not like it

bad timing

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

    I don't understand, why do you think a fine Sunday evening (for Indians) is a bad timing? :thinking:

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it -14 Vote: I do not like it

      Because maximum times contest is organized at night and that is the best time to give contest because you are relaxed from all the works. So comparatively it's bad time. That's it.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think,it is your first round in CF Warawreh.Hope no ambiguity in problem description.Good luck.

»
5 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Damn, I know that Americans are a minority on codeforces, but many of the recent contests have been at bad times (6 AM) for us in California, and this one is 4 AM as well. :'( Of course it doesn't make sense to base the timing off of americans, but I hope there will be one at a reasonable time for us soon!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    What? The 6 AM round is the best kind of round, because you can just wake up and play right away. No more anxious waiting. One and done.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Haha yeah, that's true. When I can wake up that early, 6 AM is good. But I like sleeping in too much to wake up that early these days.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 4   Vote: I like it +9 Vote: I do not like it

        In our country, many (recent) competitions start at 23:35(UTC+9). Most of the contests end at 01:35 or 02:05. I cannot sleep until then and sometimes I sleep later (at around 3 to 4 A.M.) in competitions where they have open hacking. Isn't it better for the competition to start at 6 a.m.?

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

          Your 6 is someone's 2.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            I think your reply should be posted in a different comment.

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

          Yeah, of course any time is good for some people and bad for some other people. I've just noticed that all the competitions recently are at this same time. I think I would just like to see some competitions at different times.

»
5 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

last minute information: codeforces admins are communists

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks god it's sunday otherwise i will be in college till 5:30pm (IST)

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it will be a great round.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I believe that it would be a nice round Warawreh ;)

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Jordanians problem setter, but it clashes with Jordan vs Vietnam match.

Sorry Jordan, we don't have a jordanian codeforces round set up by my friend every day XD.

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Please just order problems correctly by their difficulty, because lately many round setters didn't :D

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

    One of these rounds you are talking about D/E had the same score so do try to check the score instead of letters before saying that https://codeforces.com/contest/1100/standings

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That contest may have failed to control the difficulty level because the problem setter set problem for the first time. (But it was a bit harsh. The difference in the rating between problem C and problem D was 1100.)

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

      That's not one of the contests I have in mind. I will give you 2 examples I was referring to:

      1. Educational Codeforces Round 58 Where Problem E was far easier than both problems C and D. Yes I know this is an educational round and it's based on ICPC rules, but still that's not a good thing given that it's traditional for problem E to be harder than both C and D.

      2. Hello 2019 problem F is easier than problem E.

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

        Fair enough. For Hello 2019 it's a bit less clear since a huge part of the problem was that the O(N * sqrt(N) * log(N)) intended solution works fast enough. That educational E was really a joke tho...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I would participate on this contest but for Sorry I have a final exam the day after tomorrow

I'm so sad god damn exams

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

The first time I see Codeforces Round at 7h00 pm in Vietnam. However, Vietnam National Football team is going to have a match at 6h00 pm. "Viet Nam Vo Dich"

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Clashing with Atcoder contest

»
4 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

Some guys said ustat is dead,

Tell them, the ustat is back.

»
4 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

I think the author made a mistake in the title. It should be "Codeforces Round #533 (Div. 3)".

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve C ?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    dp[n][3]

    dp[i][j] is the number of ways to make an i digit number, having remainder j

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

      Can you explain it little detailed ?

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

        suppose you have an i digit number that sum of its digit modulo 3 is j then if you write digit x in the end of that,then you have an i + 1 digit number that has sum (x + j) % 3 so you can say : dp[i + 1][(j + x) % 3] += dp[i][j]

        you can calculate this dp in O(n) because x have only 3 general states,and at the end, the answer is dp[n][0]

        sorry for my poor english

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

This comment was helpful for problem E :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E:Helping Hiasat

No, I don't want to help him, he is so hypocritical.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

4th test for E?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    It fails when you no of connected components.

    Maybe -
    12 4
    1
    2 a
    1
    2 b
    1
    2 c
    1
    2 a
    2 c
    1
    2 b
    2 c

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Я правильно понял, что E это втупую поиск максимальной клики?

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

15th test on D?

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

    I think it had something to do with needing to do a multi source BFS instead of a single source BFS.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone tell me why I am getting TLE on pretest 6 on C? Submission

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

    Slow input caused by cin

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Nope, I submitted 6 times, with cin optimizations, without them, with scanf, etc. All TLE. Besides, it's only 3 numbers.

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

        True, had problem D in my mind with that large input. Didn't remember C only had 3 numbers, my bad.

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

          But cin is ok for problem D.

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

            If you don't use the sync_with_stdio line I don't think it is

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

              I think so,but why not use it

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

                The solution he had linked had that line commented, hence it would have TLEd for a large input problem. That's where I mixed things up and thought problem C had a large input and that was the reason for the TL.

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

    2 1 1 try this one

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

      Excuse me while I go kill myself.

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

    i've got TL 6 with same bug. while(r % 3 != mod) r--; in c++ negative number % x is negative.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Nice problemset!

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Is E something like building a graph of friends that can't both be picked (i.e. there's an edge between two friends if they both cant be satisfied) and then doing meet in the middle on that to try and find the best valid subset of friends?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    Use meet in the middle to speedup the naive algorithm for finding maximum independent set.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Do anyone passing the pretest for problem E using randomized algorithm for Maximum Independent Set (MIS)?

**Update: System test Accepted ;)

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

    You must have some balls of steels to submit it in a rated contest. If this isn't rated for me I would have tried to use this opportunity to test my simplex template.

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

      Well, I'm just trying whatever I know because I don't know any other algorithm to solve MIS problem :(

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

    Bruteforce was too slow, but I was lucky to find the correct solution before. Just a timer to exit the search early if necessary. 48631423

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Yes, my randomized brute passed, but it was not at all the intended soution.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

48635541 I actually got stuck during the contest, why did my submission of problem C get time limit exceeded ?

»
4 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

Was D just an implementation problem or there was some observation to do for speed-up? I implemented (naive) multi-source BFS but still getting TLE

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

    BFS is good enough.

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

    I tried to calculate the distances of every free cell to each player (using the speed information) and calculate for each cell, the first player to reach them. But i got WA because there are some cases where a player can block other and reach a cell first even having to play more rounds. So i thought the right solution was the naive BFS and didn't have time to implement it. Now i'm curious too =)

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

    BFS with early break out should be good enough, because each cell will be pushed to the queue no more than once, and will be visited extra no more than 4 times (you can "bump" into each square once from each direction).

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

      yep, that's exactly what I thought. How do you deal with 'speed of expansion'? I implemented a lower-level BFS that will expand until distance_from_local_source < player_speed, probably that got me a TLE

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Try this testcase

        3 3 3

        ...

        ###

        123

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

          BFS stops at first iteration for every player because the queue doesn't get any new element pushed? Was that your point?

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

The contest reminds me of how much do I hate hacking in div2 contests -- A problem is either trivial and submitted by a lot of people, making it boring to go through all of them, or there are very few people who submitted it...

Yes, I am salty about losing 5 hacks to another roommate who only started hacking 30 minutes before I started. ;_;

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Shouldn't this solution give Runtime error? on 1 1 a https://codeforces.com/contest/1105/submission/48622609

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

    a[i+1] for i = 0 will give garbage value, it'll work without RE

»
4 weeks ago, # |
Rev. 3   Vote: I like it -15 Vote: I do not like it

Probably the worst round in Codeforces history, imbalanced and not interesting problems, didn't expect it from such a noname.

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

    ShutUp..!! It was good.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      I bet you think so just because you didn't try to solve anything except ABC

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it -24 Vote: I do not like it

        ...

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

          How is your phrase related to my comment?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 2   Vote: I like it -27 Vote: I do not like it

            ..

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

              I don't understand what you want to say. I didn't state anywhere that I'm good at something. It was said, that this round is bad, and your performance depends only on your hands

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      Only because you did well

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

    I don't think so.

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

      D is prue implementation, and E is a classic algorithm just using Meet-In-The-Middle. Jf course, if your level is at ABC, you won't feel that anything's wrong with DE and so on, but that doesn't make these tasks good and worthy for Codeforces

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

        That's true to some extent, but there were even worse competitions.

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

          Okay, I agree, maybe it's not the worth, but one of them obviously

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Is E just finding size of maximal independent set with meet-in-the-middle? If so why do you do things like this?(((

»
4 weeks ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

warawreh's hit contest

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Someone please help me, For problem A
I tried a hack on the solution.
This solution initializes s[n+1] but uses s[t] somewhere between the code.
For a test case like:

2  
88 100 

s[] should overflow because, t can take values from 88 to 100, but s[] is initialized only for 0 to 1.
But my hack failed. Why is his solution still printing the right answer?
UPD: He failed main tests :/ . Still it was my first ever hack and learnt about how overflow actually works :)

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

    I suppose that only s[3] and s[4] is corrupted due to overflow, you need a testcase to trick the code into reading these two slots.

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

      Oh so is that how overflow works?
      I thought any number greater than the limit would have created overflow...
      Can u explain me in detail?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        This is what my Operation System course taught me:

        So, when the C++ code writes "s[n+1]", the OS allocates some memory to the code, and the same thing happened when it asked for memory for p and j. The OS make use of the stack and use the 2 records right after s[n+1], which, pointer arithemetic tells you that it is equivalent to s[3] and s[4] (Or around s[3], I am not entirely sure about this tbh. Perhaps since s[3] is allocated to the array to store '\0' so it is actually s[4] and s[5]).

        Then, when s[88] is called, it look into *(s+88), which is not occupied by anyone. Luckily, this is also not out of the memory bounds that the OS allocated to the process, so calling s[88] will neither access corrupted memory nor trigger segmentation fault.

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

          Thank you for the explanation. It was my first hack (though it failed), I learnt something new :)

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Any clue to get past pretest 5 on D?

»
4 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

People like thinking during a contest, do not take away this opportunity from them

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is so cool for me. Thanks for this contest, its very nice! :D

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

I have to say that problem D is really really really inappropriate to be D. May be C and D could have been swapped.

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

    BTW pretests are too weak, my friend failed both B and D. Hope that will never happen again next time.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hmm... this is weird...
but anyone have any ideas of pretest 15 of D?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

"have a castle their"

»
4 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Also, this maybe a bit too much, but I'd be glad if the part one or more castles in statement of problem D is written in bold or italic to emphasize it.

I wasted 3 failed submissions and half an hour by misreading this part, thinking each player will only start with one castle. It's not that I want to blame, but such crucial information should be emphasized.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are there so many Failed System Test in problem A?

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

    Some people only checked for t = values of the given array for some reason.

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

      ... Okay, but I think other reasons also exist.

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

    many sort the array pick the middle and calculate the ans.

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

    Many players assign x to the median of array a

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

I suggest that the key words should be BOLD in the statement.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I got accepted on problem B with DP solution

Seems too overkill

»
4 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

Div. 2.5

»
4 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

Congrats Warawreh.

Impresive Debut as a problem setter in CF.

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Does 1.0 * clock() / CLOCKS_PER_SEC actually give the time the program took to run? For question B, I was getting TLE on pretest 12. (link) Since the test case is too big, it's not shown completely but I think the string is 200000 z's. When I tried such an input on my computer, it shows 0.016 seconds. Why am I getting TLE there?

edit: ok never mind, I changed a few characters randomly in the string and it took more than ~5s on my computer.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the combinatorial solution for C? Anyone explain please.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

How come c++17 is much faster than c++14?

Here 2 codes for D First Submission Second One

A whole half second seems rather cruel despite using scanf

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

    This is just too cruel.

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

      Yeah totally shitty,candidate master gone cause of a simple weird mistake

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretest 5 of D:

4 4 2

1 1000000000

....

....

..2.

...1

Can someone explain why the final state of the board is:

2222

2222

2221

2211

rather than

2222

2221

2221

2111

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

    And why would it be the second one? first player will only expand 1 cell up and 1 cell left in the first move (as his expansion speed is 1), and then the second player will fill out the board with his huge expansion speed.

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

      Oh, I misunderstood this problem. I didn't realize that player i could take any square that was si distance away, I thought the problem meant that it could taken any squares si distance in the direction left, up, down, or right (i.e. could only expand in straight lines).

      I suppose I was confused because the problem said "castle", and I immediately imagined rooks from chess. Definitely much more my fault than the problem setter's, but still very annoying because I spent an hour of the contest looking for a bug in my code.

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

        Alternating moves was not clear from neither the statement nor the sample tests, but they made an announcement regarding this.

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

          Oh that's right, I do remember them making a statement about D. I was working on E and forgot about it. Stupid mistake.

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

    The first player only has 1 speed expansion, that means the state of board after the first player play is:
    ....
    ....
    ..21
    ..11

    Then, the second player plays filling the rest of the board.
    2222
    2222
    2221
    2211

»
4 weeks ago, # |
Rev. 2   Vote: I like it -9 Vote: I do not like it

Why t can't be 0 in problem A ?

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

    From problem statement:

    "The value of t is not fixed in advance and you can choose it as any integer."

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

      Thanks man. I wish I had seen it :(

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

      I too got WA first time. So read the question again and found this.

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

It was a good contest with clear explanation of the problem.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me find bug in this code for Div2D : 48619139

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

Could anyone solve C using combinatorics (without DP)?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What a nice planning. I have to wait just 2 days for comeback :D

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why this code for problem D get WA on test 38? https://codeforces.com/contest/1105/submission/48642621

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

For problem C:

I kept on trying it with stars and bars method, DP didn't occur to me.

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

    I used divide and conquer with memoization.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think worst case complexity of D will be O(n*m) (In each chance if we acquire a cell) Player x will not play again in subsequent rounds if he wasn't able to play in previous round.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it just me, or this div2 round was a lot more accessible than most of other div2 rounds (even considering only the div2 only rounds)? I am curious about other people's opinions!

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

    i agree with you strike ,it seems problem c was easier as more than 2000 contestants were able to solve it and problem b was also easier than a lot of div 2 rounds

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem A, I got many WA because tried to find the minimum changing cost first. Tutorial say that we should find "t" value first. Why?

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

    because it is easier to find the value of the required "t" ,i also was doing the same then i realised that the constraints allow us to calculate the min value for all the possible values of "t" as "t" can only vary from 1 to 100 according to the values given in array , so our solution is just calculating all the min values for all the "t" keeping the one with min value as our solution which will give us time complexity of t*n.

»
4 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

Deleted

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

time limit for D was too strict, no python solution passed the TLE during the contest.

you can check out my python2 implementation of intended solutions gets TLE at test case 13

also all these other solutions from other users in python3 got TLE even if most of them are correct as in the editorial TLE test case 13

TLE test case 13

TLE test case 13

EDIT: I implemented a solution using collections.deque but still gets TLE, is anyone able to get AC on problem D using Python? up to now no one did.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B, Zuhair and Strings.

Is n=200000 and k = 100000 a special case? If yes, I don't get it.

After contest, I just added this case, and it is accepted(without any change of logic in previous submissions)

Link: https://codeforces.com/contest/1105/submission/48648864

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

    No, n=200000 and k = 100000 is not a special case. I tried to run your submission with this testcase "6 3 abaaba" and it gave 2 as a result. the correct answer should be zero. "all characters of these x substrings are the same (i.e. each substring contains only one distinct character and this character is the same for all the substrings)."

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Such a strangle thing. After contest I submit haosc1212's submission.48632510.And I got TLE.But the code accepted with 1600ms.How can this happen? Oh,C++17 is much faster than C++11.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

What is testcase 45 of problem D?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Generator's source code
»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can test inputs and outputs be found somewhere on Codeforces after a contest ends? As you know, for large input or output, all of it may not be displayed on submission pages. Actually it's not related only to this contest.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't understand why I got TLE in problem D. I have attached both my contest time code (in which I got TLE in main test) and AC code written after contest.

The only difference is I added this line " if(v[cur].empty()) return ret; " at the beginning inside bfs() function. But if I don't do this it should return the same "ret" since both v[cur] and q should be empty and no while loop should run. But adding this line is giving me AC in 0.5 sec while skipping this giving TLE with 2 sec+. What's the reason behind this significant difference in time?

TLE Code: 48636948 AC Code: 48646138

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

    It may got optimized. C++ is very hard to understand completely.

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

    in case 45, bfs is called around nmp times, now each time you call bfs you create a new queue, I don't know the details, but creating a queue in c++ is not very fast which is why you get tle, changing that queue to global should greatly decrease the running time.

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

      The default container for a queue is deque, and for some reason it is more heavy than other data structures. The size of an empty queue (with deque container) is 80 bytes, while if we change the container to list, it will be 24 bytes.

      The same solution gets accepted after changing the container to list: queue <PLL,list<PLL>> q48669305.

      So I think it is mainly memory allocation / deallocation that makes it too slow. The solution is declaring around 80 * 9 * 106  =  ~686 MB while using list container would declare 0.3 of that.

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

      I use C++11 and then I got failed on system test.(i.e.TLE in test 45).And when I changed to use C++17.I got Accepted with 1600ms.How can C++11 and C++17 have so big differences. Maybe C++17 std::queue is optimized