Kniaz's blog

By Kniaz, 7 years ago, translation, In English

Hello everybody!

I am glad to announce that at 19 January 2017 18:05 MSK will take place Codeforces Round #392 for participants of Div.2. Participants from the Div.1 may participate out of the competition as usual.

You will be offered 6 problems and 2 hours for solving them.

Great thanks to Nikolay Kalinin (KAN) and Alexey Vistyazh (netman) for their help with the contest preparation, Tatiana Semenova (Tatiana_S) for translating the statements and Mike Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems and also for help with ideas of some problems and their preparation.

It's my second round and I hope that you like it more than the previous one. Fair rating to everyone!

UPD: Scoring 500 — 1000 — 1500 — 1750 — 2500 — 3000.

UPD: Editorial!!! I want to thank Mikhail Piklyaev (awoo) and Tatiana Semenova (Tatiana_S) for translation of tutorial!

Congrats to the winners!

Div. 2

I wolf29

II alexwice

III WhyamIhere

4 TaTaPiH

5 Life_chicken

6 RewriteHarvestFesta

7 djqtxdy

8 whzzt

9 Lucas97

10 Clayton

Div. 1

I W4yneb0t

II sd0061

III irkstepanov

4 wolf29

5 I_love_Tanya_Romanova

6 HellKitsune

7 kraskevich

8 kmjp

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

your last contest was really interesting Codeforces Round 378 (Div. 2) I hope we will see the same this time too :D

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

    Yeah Epidemic in Monstropolis was probably one of the most interesting problems I've done in contest.

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

    Driver's dissatisfaction also had a great idea within it.

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

    Looking at the problem statements, I hope everyone knows that 'Y' is a vowel.

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

      as long as he mentions it in the problem description, he can make 'Z' a vowel, or even a digit :3

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

    This contest was interesting(especially for E)!!! Thank you Sergey Kniaz Kniazevskiy.

»
7 years ago, # |
Rev. 3   Vote: I like it -56 Vote: I do not like it

magic

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

short announcement... I hope problem statements will be the same

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

    But what if... Kniaz had a limited number of symbols and wanted to use more of them in statements? Think about it!

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

      by 'short' I actually meant 'clear'. We expect a clear and well-understandable problem set.

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

        short means short

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

          Yes, short means short, but Least_but_not_the_last was not claiming that “short” equals “clear”. He was correcting a mistake in word choice. i.e. “I said short by mistake but I realy wanted to say clear”.

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

The usual question. Yes or no?

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

I really liked your last contest, especially the Problem F. Thanks for the contest again! :)

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

    But I really disappointed about this contest :(

    Anyway, please ignore me.. this is just a loser's comment.

    WHY THE HELL X and Y means row and column?!?!

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

I hope there will be shorter statement and more interesting solutions :P

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

I am in Korea so I need to get waked up at 00:05

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Score Distribution?? Not declared yet, 2 & half hour left

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Score Distribution??

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

This is the last CF round before the Central informatics test here...

I really hope that I can get to Div1 so I can impress everyone I know with a new color wish me luck!!!

:)

UPD:I'm gonna get my new color...sadly it will not be in DIV1 :(

Ahh well I'll try again in the next contest.

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Nice score distribution)

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

Score distribution? only 5 minutes left!

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

problem a submission failing pretest 1 if sync_with_stdio(false) and cin.tie(NULL) is present on c++11. accepted without those lines in c++14

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

    errors in pretest 1 are not counted anyways :)

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

      I know, but I had to re-check my code, remove endlines etc, before i tried this. not that it matters in the long run, but pretest 1 failure on problem A is a shock when you try to solve the next one asap.

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

        I am sorry to say this, but the reason for WA is not due to sync_with_stdio(false) and cin.tie(NULL). but because u did not set value of mx to 0. Try using the custom test next time to find out what's wrong.

»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

not say unrated for B :((

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

Great problems, I really enjoyed them. Thanks for contest Kniaz

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

Made 17 submissions but getting wrong answer of pretest 8 for problem D. Any reason?

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

    Did you check for 64-bit integer overflows? Something like if (f[i] <= INT64 / n) before an f[i + 1] = f[i] * n update.

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

      I checked whether num>=0 && num<=1e18; If it would have overflowed it might become negative or >1e18. AM i right?

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

        Not really… If it by accident equals k × 263 + C where k is an integer and C falls into [0, 1018] then you'll probably do incorrect updates.

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

        you can't have a string of consecutive 0s in your dp(example if k is 100000, you can't select '000' or '00'. But you can select '0').

        have you taken care of this?

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

          Yes mitsuki I have. Not only zeroes, you cant have "002" i.e. any number with leading zeroes.

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

            Yes I meant all starting with a 0 (except '0' itself).

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

      The result is guaranteed to fit into 64-bit int, so I don't get why you would need to check that?

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

        In some implementations we calculate some value as is described above, and then compare it with another value to do updates. It's perfectly fine if this isn't involved in your implementation :)

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

          Yes, sorry, I didn't realize there are non-greedy solutions :)

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

            Nor did I realize there are greedy solutions… (●—●)

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

    Could be overflow. I got pretest 9 due to overflow

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any idea of pretest 14 in problem C ?

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

    not sure. but did u consider n=2?

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

      In this test min = 0 (my first submission failed on it)

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Any idea as to what was pretest 6 in problem D?

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hack cases for problem C?

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

How to solve B? I feel very emberrased asking this question.

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

    The idea is that the color of light bulbs will be same in positions 0, 4, 8...similarly same in 1, 5, 9, ...and for sequences of 4 * K + 2 and 4 * k + 3. Since there is atleast 1 light bulb working for every color, you can know which sequence corresponds to which color.

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

      Oh no. I am feeling gray right now or even below than that.

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

Is there any counterexample for greedy for problem D?

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

    Should output 23 (= 1 * 12^1 + 11 * 12^0). (I assumed you meant greedily pick the largest portion < n)

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

      That's exactly what my greedy algorithm outputs. I greedily pick the largest number (from the right obviously) in each step.

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

      Well you assumed right, but my solution gives 23.

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

    Yup there is, WA 100 :(

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

      What is the case?

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

        2 10000000000000000000000000 but I think it is more like a bug in our code than it is the problem w greedy UPD: I just debug my greedy and it AC. so greedy works

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

      That's not a counterexample to greedy but rather to either not handling overflows or 0's correctly. Also, greedy does work.

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

Loved the problem set. Thanks for the contest. Really scared about clearing the system tests this time though.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Guys, what is a type of problem C today? Is it math or just implementation? I have difficulties with this kind of problems

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

    DFS, BFS, Dijkstra, KMP, GCD, ... all this knowledge means shit when confronted with such kinds of problems :(
    I don't even know how to study in order to be able to solve them.

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

      Absolutely agree) I think this type of problems is named as "constructive"

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

        I go for 'destructive", took me an hour to solve...

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

          The correct term is "stupid time waster".

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

            I don't think it's stupid and red guys solved this problem in 10 minutes. We should at least strive to perform like them.
            The only problem for me is that I don't know how to train to be able to solve such problems.

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

              It's called "stupid time waster" because: 1) the solution is obvious: you remove the cycles in O(1) then simulate the rest; and 2) there's a lot of corner cases to deal with (this is the part that wastes your time). And nothing better than "stupid" to call a problem that is both obvious and wastes your time.

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

                There is exactly one corner case (n = 1) in my solution. I believe its what can be feasibly called an implementation problem due to the solution being pretty obvious. The time you spend is mostly spent on writing the code, not thinking about the problem.

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

                  That's just what "time waster" means to me.

                  A and B usually are time wasters, but this C is over 9000.

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

                  It is interesting for how long this point of view will serve you as a source of motivation :)

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

                  I don't need motivation. I need time.

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

                By the way, if someone is interested, it is possible to write the code without any corner cases: 24112753

                Exactly one if() for the whole program.

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

                  Nice, it took only a week! Now I'm so convinced that this is not a time waster problem!

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

                  Sorry, I didn't want to provoke you. I just wanted to share with my finding and it looked like this is a good place.

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

                  There's a "Write comment?" button up there ^

                  If this is not a provocation, you should've used that instead of replying one of my comments. It really seemed like you we're trying to provoke me. But you explained yourself, so okay, no problem. Just use the button in the next time.

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

        I really hate that kind of problems

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

      Cannot agree more. I found these types of problems very irritating.
      I made 6 submissions and all failed on pretest 5, maybe I was missing an easy corner case.

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

    It's a combination of math and implementation — you need to get the period idea to make the solution O(nm).

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

    Who all math lovers here?

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

Do we need Big integer in div2 D ? Passed pretest but it may fail due to multiplication overflow.

UPDATE:
FST, got accepted after checking overflow
if (mul2 && mul1 >= LINF / mul2)
{
return LINF;
}

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

    Alexander guarantees that the answer exists and does not exceed 10^18.

    So if we do it the right way, we shouldn't need Big Integer

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

      But there can be cases that the minimum answer < 10^18 and the maximum answer > 10^18, and my solution may choose the maximum answer due to multiplication overflow

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

        You don't consider cases where answer is more than 10^18.

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

          In my solution I do multiplication such as curNum * exp, where exp can be big like 9e17, it's easy to overflow and I didn't find a way to avoid it.

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

        So you didn't do greedy? How did you solve it?

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

          didn't find a greedy solution and do O(len^2) dp

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

        Not sure how your solution works. But looking through my code and with constraint such as (2 ≤ n ≤ 10^9), I dont see anywhere I could overflow. I could be wrong though.

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

        In such situations, you can use a long double. It can store up to 1e18 perfectly, and so the answer will be reported correctly with full precision. If it goes above 1e18, you will lose precision but comparisons will still be correct enough. And in this case you don't require precision because it is not the answer anyway.

        23960455

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

    No you don't need big int, check my solution: http://codeforces.com/contest/758/submission/23960101

    The idea is: you want the minimum amount of digits on the base N, if there's a tie, getting the smallest possible digit on the most significant digit is the smallest answer.

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

seconds away from submitting D :/

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

no hacks this time!! :-)

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Anyone passed D with a DP solution? I was doing dp(i,j) as the minimum decimal number when consider i-th position the beginning of j-th part. I am pretty sure about this approach but it received WA on pretest 7 however.

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

    I passed with dp solution. You may have a problem with the 0's

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

    Did you handle overflows?

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

    I was also doing DP soln and WA on pretest 8. I think my error was due to overflow.

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

    I tried to solve it in the samw way. However, there are some tricky cases. For instance, when the choosen number starts with 0(2 — 0 — 16 is ok, but 2 — 016 isn't). There should be some other similar cases.

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

      Yippiee, my solution is wrong! (Came about 15 seconds short.) But i think getting digits greedy from least to most significant should work?

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

        This time greedy should lead to WA, try testcase

        320

        222408

        My dp solution gives 2329608 but yours will give 22745608 (if i dont misunderstand your greedy solution).

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

          I get the same answer as you. I start from the least significant side and try to find the biggest possible digit: 8 — 240 — 22

          UPDATE: Greedy is accepted.

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

    where do you have base power in your dp state? I had dp state as DP(i,j,pw).

    PS — I got WA too

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

      beginning of j-th part can be used to uniquely identify the base power... I think your states are redundant

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

    You could use a dp(pos) it tells you the minimun length of this number in the base,so after that you make a dp reconstruction as the statement tell you it fits in a long long you would make the reconstruction safely without overflow.

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

    Pretest 7 might be the case that the result is 10^18

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

Can smb explain the idea behind F?

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

    I'm sure you can solve it with n = 1 or n = 2. So, let's assume n >  = 3. Now, let r = x / y be the ratio of the progression( gcd(x, y) = 1) . WLOG, r > 1. Then, xn - 1 <  = r because yn - 1 divides to a0. So, you can brute force x and y up to 3200( sqrt(10^ 7)). After that, you find bounds for a0 and you just need to add the difference of those bounds plus 1 to the answer.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain how to do C?

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

    The rows (1,2,3,...,n,n-1,n-2,...2) form a sort of cycle that is repeated. The total amount of questions in the cycle is m*(2n-2).

    And after that you're left with k%(m(2n-2)) questions which is less than m(2n-2) < 100*200 < 1e5 which you can fill out manually.

    Since 2*1-2=0 n = 1 is a special case (i dont exactly know if this is avoidable).

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

      Me also treated n = 1 as a special case. There is nothing like n+1 or n-1 here. Maybe modulus arithmetic can do some trick though.

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

    There is lots of way to fail. Consider some variable.

    MD = 2n-2
    P = k/m
    Z = P/MD
    R = (P%MD)*m+k%m

    Can you explain what variable holding which information? Do you see the pattern?

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

    1) Calculate how many times the classroom (matrix) will be covered. Let it take 'cover' number of times. This can be calculated as: For 1st round: n*m For 2nd round: (n-1)*m (Won't ask the last row in second round) For 3rd round: (n-1)*m . For 'cover'th round : (n-1)*m

    Summing them up: n*m*cover — m*cover +m (Eq-1) Equate this to k and solve for 'cover'. cover = (k-m)/(n*m-m) Check whether k<m. If it is then cover = 0.

    2) Now the 'left' can be calculate easily by subtracting k with (Eq-1).

    3) If cover=0, then left = k, and we can simulate by giving 'left' number of questions to students in the way described in the question.

    4) Now, a)Initialize the top row by (cover/2)+1 [1st round = 1 time visited 2nd round = 2 3rd = 2 and so on.] b)Initialize the last row by (cover+1/2) [1st round = 1 time visited 2nd round = 1 3rd = 2 and so on.] c)Initialize others by(except first and last row) by cover

    5) If cover%2==0, start from top and stimulate the process otherwise from last row, till left=0

    6) Calculate max,min and a[x][y] from the matrix.

    Consider n=1 separately, for which cover = k/m and left = k%m. Initialize it with cover and then increment the row until left=0

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

Was D solvable using greedy: http://ideone.com/lgOWrh And, the last 30 seconds the sumbmit button wasn't working. Is it only for me or somebody else got the same problem?

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

Does anyone have some good test cases for C? I got WA on 10. :(

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

What if my B solution is right ! It token me most contest time searching for the wrong after hacking. I hope that to be unrated contest or for who faced the same problem only .

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

    My O(n2) solution got TLE in Hack. !

    I think the case was something like these —

    !!!! or 
    !!!B 
    

    Where they don't contain G,R,B,Y at least once

    Also I solved D just 1 minute after the contest.. And my friend solutions are almost same to me.. But I didn't able to submit

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

    The validator in this problem was incomplete. There were some hacks that uses invalid inputs but were processed. All of them will be rolled back. Sorry for it.

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This contest should be unrated only for those who suffered in problem B. :(

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Please don't make it unrated :(

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

still 'Pending system testing'!!! :(

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Thanks Kniaz for writing problems. I like tasks A, B, E, F very much, D is OK, but problem C is terrible. I hate this type. A lot of commands 'if', 'else'. But it's only my liking. So excluding problem C contest was pretty good.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

WTF is this!! This guy's all solutions got hacked!

http://codeforces.com/submissions/Fuck_Anas_Abbas

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

    lol :D :D

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

    Maybe someone is cheating and has two accounts: at one he sends wrong solutions, and from another he hacks...

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

      But how can he make sure they will be in the same room?

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

        OK, it's small probability. But if he has more than 50 accounts? Mabye there is a person who starts in contests to have a high rating...

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

      as the one who hacked him:

      i laughed when i opened his code for the first time

      but now i think i've made an enemy for life

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

        I am pretty sure that when you will see those hacking attempt you will find "Anas Abbas has been fucked"

        lol :P :P

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

    Open his source code, when suddenly...

    cin>>fuck

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

    his code is funny

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

    This guy should write a book on "HOW TO PASS THE PRETESTS AND HACKS LIKE A SIR"

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

I like the last sample test for problem div2C.

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

Kniaz why are your Pretests this weak?!!!!!

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

    Come on! The pretests for B and C were awsome and i think few people passed the pretests and failed the sys test !

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

Is this how to solve F?

First, insert in a fenwick tree values of antilog( log(x / n-1) )

Then, simply use these values to calculate the number of GP for a certain b(b has values from 2 to r)

The GP will be of the form xa^n-1,xa^n-2b,....,xb^n-1.

Finally, multiply by 2, and handle n=1 separately.

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

Please fix problem B validator/solution as there are alot of participants who solved the problem and their solution should pass the time limit constraints my solution was : Submission for Problem B

the test case that gives time limit for alot of participants is test case 17 : R!!Y!!B!!G! which is invalid ! as stated in the input section .

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

    Same problem here

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

    Also many one didn't get time to submit another problem solution which they were capable of :'(

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

    I don't think that case is invalid:

    Consider the string RGBYRGBYRGB

    Then the bulbs at 2nd, 3rd, 5th, 6th, 8th, 9th, 11th positions become dead The new string is

    R!!Y!!B!!G!

    "The string s can not contain other symbols except those five which were described.

    It is guaranteed that in the given string at least once there is each of four letters 'R', 'B', 'Y' and 'G'.

    It is guaranteed that the string s is correct garland with some blown light bulbs"

    None of these conditions fail.

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

153 Lines for problem B :/ Much time wasted there

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

How much time for upsolving?

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

How many tests for D are there? Failed test 100 :(

edit: there are 102 :D

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

What is solution for "R!!Y!!B!!G!" test 17 for B?

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

    RGBYRGBYRGB is the sequence, output is — 2 2 1 2 Edit: Forgot the actual numbers, only put the sequence.

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

    The resulting sequence will be — RGBYRGBYRGB so answer will be 2 2 1 2

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

    2 2 1 2

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Waiting for rating change

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

ok, can someone explain test 100 to me for problem D? 2 10000000000000000000000000

Answer: 33554432

But how? As I see it, there is only one possible way to write this number in base 2 :O o.O

Plz someone explain

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

    Exactly, the only way is to consider that is as 2^25 in base 2, which is 33554432 in decimal. I think you're confused about what you had to print as the answer.

    You had to print the decimal representation (smallest) of the given number, not the number of possible decimal representations.

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

      Why do we so many solution overflow on that case? I dont see why they would...

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

        I assume they must have tried picking up consecutive zeroes, kept increasing the multiplier by 10 while going to the left causing it to overflow.

        The many zeroes would mean that the actual number would remain zero, so a check to see if that has overflowed would be futile.

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

          It is possible to have a solution without checking overflows.. Like I didn't check overflow but got AC — 23971526

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

      Yes, thank you. I was not confused about what I had to print as my answer. It was just a stupid typecasting error.... And after seeing the test, I thought without counting the number of zeroes, that this number is greater than 10^18. I came back as soon as I realized my stupidity to delete the comment , but you had already replied :v Thanks anyway.

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

    I failed with the same case, while calculating number backward from last digit to get maximum number less than n, should break before getting overflow, here it overflows after 18 digits of 0.

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

Wrong answer on test case 84 — wrong answer 2nd numbers differ — expected: '14084507042253521', found: '14084507042253522' why???????

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

Is there a way to see submissions made using a particular language for a problem? I want to see Python submissions for Problem C.

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

What was so hard about E? Don't you just have to calculate the shortage at each edge, and then try to fulfill the shortage from the deepest node you can reach?

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

WhyamIinthewinnerlist lmao Nice contest thanks :D

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

Does anyone know why my code for D gets different veredicts if I switch between C++ and C++14?

GNU C++14: Wrong answer on test 28

GNU C++: Accepted

Edit: it might be because signed integer overflow causes undefined behaviour.

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

Could somebody explain the verdict seen here 23954999.

My code outputs the correct result locally, yet the judge gives some strange error which does not seem to be my fault.

edit: Perhaps MikeMirzayanov could shed some light on this problem?

»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

When will be rating updated?

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

Please can anybody help me with D .I am getting Wa on pretest 8 because of oveflow.. Here is my code

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

    Try using unsigned long long. I got AC without handling any king of overflow and using unsigned long long — 23971526

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

      Thanx man just changed that and got ac... i wish i had done this in the contest :)

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

        I finished this solution just before 30second of the end of the contest but didn't managed to submit it >:(

        My Solution B got Hacked :( :( And now rating change (-48) :'(

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

Stupid time waster problems like C should worth 5000 score, for the patience you must have to solve them.

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

    Not really that much stupid. Everything I needed is to see the number of student will be at most 100*100. Though lost too much time before seeing the value of n and m.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

wish some points!

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

When will the ratings will be updated ??? Wating and wating .......

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

Waiting for the rating update -.-'

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

Will it be unrated?????

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

    No. It's going to be rated

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

*** *****?

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

rating will update soon?

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

Tired of refreshing !

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

0 Rating change thank you .:)

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

Why is wolf29 in Div1 in your post? He was blue before the contest.

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Why did the rating changes get rollbacked? :/

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why the heck did u take the ratings back?

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

Why are the ratings reverted back to the previous one??

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

I'm new here, so tell pardon me if i said something stupid. When the contest was over, I had 3 problems solved. I came back some time later and found out it shows 2 problems solved and one wrong solution. Is there a way to evaluate a persons code even after the contest is over. If so, can you tell me what do they really do?

pardon my English :(

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

    It is about the main tests There are two kind of tests, pretests and main tests the main tests are used in system testing and sometimes it happens that you pass the pretests but fail the main tests

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Both my submissions http://codeforces.com/contest/758/submission/23964519 http://codeforces.com/contest/758/submission/23963310 are correct when I test them in "Custom Invocation"

"Input" RYBGRYBGR

Output 0 0 0 0

But in pretest I got Verdict — "Wrong answer on pretest 1" and Output 0 1 1 0

Why I get different result in Custom Invocation and System test? I think it is not my fault

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Finally BLUE again :D

I'll try to enjoy the feeling before losing it the next contest :3

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

Is the Venture Cup final on Sunday rated for Div2 ?