Kniaz's blog

By Kniaz, 8 months 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 (PikMike) 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 D0zingBear

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  

»
8 months 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

  • »
    »
    8 months 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.

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

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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

  • »
    »
    8 months 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.

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

magic

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months 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!

    • »
      »
      »
      8 months 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.

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

        short means short

        • »
          »
          »
          »
          »
          8 months 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”.

»
8 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Expecting High Rating this time .... #happy_coding #high_rating

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The usual question. Yes or no?

»
8 months 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! :)

  • »
    »
    8 months 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?!?!

»
8 months 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

»
8 months 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

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck for All ;

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Score Distribution??

»
8 months 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.

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

    Good luck!)

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

    you just need 250 points, good luck ;

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

      I think 250 points is kinda a lot....

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

        Less than the difference between Petr and tourist ;)

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          not saying it's impossible. but u need to be about top 15? gl guys! :)

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I know but, who know what will happen :)

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

        Well it's not a challenge if it isn't hard...Am I right ?

        Good luck.

        :)

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

    I want you to know that you're in my friends list, because you're one of the guys I'm competing with :)

»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Nice score distribution)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution? only 5 minutes left!

»
8 months 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

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

    errors in pretest 1 are not counted anyways :)

    • »
      »
      »
      8 months 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.

      • »
        »
        »
        »
        8 months 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.

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

          Yes . I already found out. It 's an unforgivable ommission on my behalf and an equally thoughtless comment afterwards. To be frank, I really was under the impression that the compiler by default initializes all concrete types to zero.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I dont know why I took 01:47 to solve problem B. Need more practice, Bye rating :(

»
8 months ago, # |
  Vote: I like it +2 Vote: I do not like it

not say unrated for B :((

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

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

»
8 months 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?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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.

      • »
        »
        »
        »
        8 months 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?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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 :)

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could be overflow. I got pretest 9 due to overflow

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Any idea of pretest 14 in problem C ?

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

    not sure. but did u consider n=2?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hack cases for problem C?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I solved with recursion. Is it correct?

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    To maintain the property that every 4 bulbs in the sequence must be different , we will get a permutation of {R,G,Y,B} which repeats to form the sequence . All we need to do is count the no. of '!' in i%4 , (i+1)%4 , (i+2)%4 and (i+3)%4 places and link them with the permutation .

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any counterexample for greedy for problem D?

  • »
    »
    8 months 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)

    • »
      »
      »
      8 months 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.

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

      Well you assumed right, but my solution gives 23.

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

    Yup there is, WA 100 :(

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the case?

      • »
        »
        »
        »
        8 months 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

    • »
      »
      »
      8 months 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.

»
8 months 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.

»
8 months 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

  • »
    »
    8 months 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.

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

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

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

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

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The correct term is "stupid time waster".

          • »
            »
            »
            »
            »
            »
            8 months 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.

            • »
              »
              »
              »
              »
              »
              »
              8 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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 :)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I don't need motivation. I need time.

              • »
                »
                »
                »
                »
                »
                »
                »
                8 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months 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.

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

        I really hate that kind of problems

    • »
      »
      »
      8 months 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.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your DFS, BFS, Dijkstra, KMP, GCD, ... all this knowledge means shit when you can't even solve basic implementation problems

  • »
    »
    8 months 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).

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Who all math lovers here?

»
8 months 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;
}

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How do you solve?

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          8 months 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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        8 months 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.

      • »
        »
        »
        »
        8 months 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

  • »
    »
    8 months 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.

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

seconds away from submitting D :/

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

no hacks this time!! :-)

»
8 months 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.

  • »
    »
    8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you handle overflows?

  • »
    »
    8 months 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.

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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).

        • »
          »
          »
          »
          »
          8 months 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.

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        can you explain with an example?

  • »
    »
    8 months 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.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can smb explain the idea behind F?

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain how to do C?

  • »
    »
    8 months 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).

    • »
      »
      »
      8 months 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.

  • »
    »
    8 months 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?

  • »
    »
    8 months 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

»
8 months 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?

»
8 months 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. :(

»
8 months 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 .

  • »
    »
    8 months 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

  • »
    »
    8 months 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.

»
8 months 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. :(

»
8 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Please don't make it unrated :(

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

still 'Pending system testing'!!! :(

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

    They need to decide how they will rejudge problem B.. That takes time.

»
8 months 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.

»
8 months 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

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

    lol :D :D

  • »
    »
    8 months 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...

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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...

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Open his source code, when suddenly...

    cin>>fuck

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    his code is funny

  • »
    »
    8 months 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"

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

System test?

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

I like the last sample test for problem div2C.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months 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 !

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

      I think that a lot of people failed system test on C...

»
8 months 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.

»
8 months 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 .

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same problem here

  • »
    »
    8 months 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 :'(

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

153 Lines for problem B :/ Much time wasted there

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How much time for upsolving?

»
8 months 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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Did you understand test 100? o.O It didn't made sense to me.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, my problem was an overflow in the base variable I used to convert to int.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Waiting for rating change

»
8 months 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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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...

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months 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

    • »
      »
      »
      8 months 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.

  • »
    »
    8 months 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.

»
8 months 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???????

»
8 months 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.

»
8 months 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?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WhyamIinthewinnerlist lmao Nice contest thanks :D

»
8 months 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.

»
8 months 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?

»
8 months ago, # |
  Vote: I like it +25 Vote: I do not like it

When will be rating updated?

»
8 months 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

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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 :)

      • »
        »
        »
        »
        8 months 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) :'(

»
8 months 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.

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

wish some points!

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

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

»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Waiting for the rating update -.-'

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will it be unrated?????

»
8 months ago, # |
  Vote: I like it -6 Vote: I do not like it

*** *****?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

rating will update soon?

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

Tired of refreshing !

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

0 Rating change thank you .:)

»
8 months 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.

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Why did the rating changes get rollbacked? :/

»
8 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why the heck did u take the ratings back?

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
8 months 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 :(

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Detailed information about contests : Click

  • »
    »
    8 months 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

»
8 months 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

»
8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the Venture Cup final on Sunday rated for Div2 ?