Um_nik's blog

Codeforces Round #315
By Um_nik, history, 9 years ago, translation, In English

Hello everyone!

Codeforces Round #315 will take place soon. The authors of this round are students of Ural FU sivukhin and Um_nik. This is our second round. First one was in the black days of Codeforces and we hope that this will not happen again after our round :)

We want to thank Codeforces team for great Codeforces and Polygon platforms and Zlobober for helping us prepare this round.

Good luck!

UPD1:
Score distribution.
div2 : 500-1000-1500-2250-2750
div1 : 500-1000-1500-2250-2500
We strongly recommend you to read all the problems. We try our best to prepare different problems and some problems that hard for us can be easy for you.

UPD2:
Editorial

UPD3:
Congratulations to the winners!

div1:
1. KAN
2. Petr
3. enot110
4. tonyjjw
5. Konijntje

div2:
1. Lost
2. loser21
3. fyiwxp221
4. hqpwca
5. LazyWolfLin

Thank you for participating.

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

Comments Comments (192)
| Write comment?
»
9 years ago, # |
  Vote: I like it +51 Vote: I do not like it

One suggestion to Codeforces team, Please do not allow someone to name their handle which has slang or obscene word or may be their handles are part of it. Thanks.

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

    I don't really want to educate anybody here, but "sex" is the main thing why you exist.

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

where's your previous round? "I don't know what black days are."

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

Good luck to everyone!Wish you high rating! And thanks sivukhin and Um_nik for this round! It's good to have another chance to practice more!

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

Here's a suggestion: Please hold more contests at 17:00 ~ 19:00 Moscow time. That time is more available for Taiwanese and Chinese coders. There are many of them!

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

    __

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

    I agree with Ir1d. Taiwan is an inalienable part of the territory of China, always. Please be careful what you say.

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

    Jeffrey Taiwan is an inalienable part of the Chinese territory.

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

    There will be 2 sites. What wrong with site like codeforces?

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

    Taiwan is a part of China... Of course ,don't talk too much about politics

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

      Speaking from a country clouded by all sorts of censorship, your comment is so trustworthy!

      Okay I'm kidding, I kind of feel sorry for you,
      since you've been brainwashed by a corrupted government since your birth :)

      Of course, I still respect your freedom of neglecting the fact that Taiwan is an independent country and spitting out ignorant comments :)

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

        I do not think you really don't expect politics to be brought up on Codeforces as you said before. How dare you say Taiwan isn't corrupted? I'm so sorry but what you said is a joke. I won't argue about it anymore because history will give us the satisfied answer like HK and Macao.

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

        __

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

          You're the one being delusional.

          Feel like googling "Taiwan" and look it up on wikipedia?

          Oh wait, you can't :) (without using VPN, proxy)

          This is just pathetic.

          Oh and, this will be the last comment I made on this topic.

          Not interested in arguing with some politics zealots.

          Keep living in your own world where every country is yours essentially.

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

            hahahah, young man, so jump.

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

              i mean Inishan is so jump. his words are so impolite, but some people still vote up for him. i dont know why,it is just sarcasm, taunt and discrimination. then pretend to be aloof from politics after saying the words, and use":)" to show his "accomplishment". In a word, Inishan's words are so arrogant, and do his grandparents and ancestor know?

              I never talk about politics in public places, even this time. but plz mind ur words and be polite to every one. I dont mind my contribution, if u insist on supporting him, a ungratefulness and mean person.

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

                Does the word "jump" have the same meaning in English?

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

    I don't know much about Taiwan and China, I just want to say that starting time is a sensitive issue for us all.

    In Korea, we take 'regular(19:30 MSK)' Codeforces round at 01:30(Of course North Korea would have it 01:00 :p). When the round was at 17:00 MSK, we took it at 23:00, which was really great(you can see me excited here). Even a tiny shift was very convenient for me. However, at the 17:00 MSK contest, many people were embarrassed, as their schedule(job, school, etc.) hadn't ended. Many other shiftings were preferable for some people, and uncomfortable for others. I am lucky too, because it doesn't really overlap with my schedule — it's just too late, and I will probably fall asleep in morning class. Some people might have regular rounds in the middle of their day — for example, New York has it at 12:30.

    We are competitors from all over the world, yet users of Codeforces. Administrators of Codeforces don't realy have to make equality on opportunity. I personally would really like an early contest, but if it's not preferable, we can't request... I just 'hope'.

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

    Taiwan is just a part of China. Why so serious?

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

    The point is that earlier contest time is more friendly to coders in East Asia. I wanted to vote 'up' but misclicked it. Sorry bro. :)

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

    I agree with JeffreyHo. I'm from Vietnam and it is difficult for me to participate in a contest. It is usually held from 23:30pm to 1:30am. So, can you hold the contest earlier?

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

    I agree with JeffreyHo. I'm from Vietnam and it is very difficult for me to participate in a contest. It is usually held from 23:30pm to 1:30am. So, can you hold it earlier?

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

I missed those black days of codeforces,but happy to witness black days of topcoder :)
Hope they will overcome too.

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

    when did that happened ??

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

      if you are asking about codeforces black days you can find it here, but if you are asking about topcoder I would say almost every SRMs of topcoder had some issues these days. So, I told it as black days for topcoder.

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

        You are right.

        It seems that the little issues that pops out almost every TC round is as critical as the black day's of CF, "which I'v witnessed on my third Round by the way".

        However I started to get a more fan of TC than CF, hope they work out these issues :D

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

World Consumer Rights Day Round!

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

    Happy Skyscraper Appreciation Day :D

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

    Today:

    1) Independence Day in Ecuador
    2) Day of signing Panama Canal Zone accord
    3) Day of returning Hong Kong in China
    4) Day of St. Lawrence
    5) Day of city in Naberezhnye Chelny, russian city.

    Are you sure that this round must be named World Consumer Rights Day?

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

      Surely you can give it more funnny name :-P Looking forwart to the round!

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

      Sorry sir. But I have to remind you. The day of Hong Kong's returning isn't today. It was July 1st,1997.

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

Your problems in the previous round were very interesting I hope this round will be the same :)

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

This round shuld be called #NotPI :)

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

This time they told Score distribution SOON ;) THANK YOU |: ################################################################################

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

You know, Div 2 contestants should not compete in Div 2-only rounds....the irony!

Edit:I know this is a div1+div2 round, just saying...

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

"U contest" sounds good to me. Because Organised by "U"mqra and "U"m_nik of "U"ral "U"niversity .

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

Problem E costs 2750, it going to be interesting!

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

hope to not see Succesful Hacks on Div 1.A :D

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

I was away from CF for few weeks and what's this? They are no longer declaring the score distribution at last moment! When did people started playing safe?

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

WTH with A?

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

​

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

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

      Very disturbing one!

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

      Xellos I usually like your memes very much but this picture is very distasteful please can you remove it ?

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

        I don't find it distasteful, I don't care about getting downvotes and since it's getting plenty, it's going to be invisible by default soon, so I don't even need to do anything.

        And I can't delete the comment at this point anyway.

        But if you can't bear it existing even hidden, there's always the option of walking away from the screen.

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

          Actually, its so "distasteful" that its actually funny :p

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

          "I can't delete the comment at this point anyway"

          Couldn't you edit your comment? Learn from him how to hide your comment.

          And, "I don't care about downvotes" — means you don't care this community! Mind your words...

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

            Couldn't you edit your comment?

            "it's going to be invisible by default soon, so I don't even need to do anything" — logic is there if you don't take things out of context

            "I don't care about downvotes" — means you don't care this community!

            No.

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

    ?

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

Codeforces is hanging. Can't read codes of roommates.

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

When B has more solves than A...

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

Is the answer for DIV1B this sequence?

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

    Yes sir, first difference of the bell numbers.

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

    yes,it was also 2nd number sequance of bell -_-

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

      Awesome! Is there anybody here, who discovered this sequence by calculating the answer for 1..5 using bruteforce?

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

        I did :D but no time to impement :D

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

        I've bruteforced for all n < 7, then OEIS it. Got 2 sequences, first one's formula is a little hard, so I thought second one is what I need. Accepted :D1.

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

          How did you bruteforced n = 6?
          It has 2^36 variants to analyze..

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

            2^(6*7/2) = 2^21 values.

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

        I tried all sequences, then found thr right one, but I could not implement that.

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

    This is why I hate a single-input problem. People that has no idea at all can just do bruteforce, find the several first number of the sequence, google the sequence and get the answer.

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

      There were two sequences corresponding to 1..5 answers. It was difficult to choose between them :)

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

      Why do you think this is an approach that should not be available? It looks quite creative and risky to me.

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

      It can be even worse than that! The sequence in question is number 4 increasing sequence from the search based just on the 3 given problem examples: https://oeis.org/search?q=1%2C+3%2C+10

      And the other (wrong) sequences could be rejected by simply copy pasting and running them against pretests. Shame on me, but that's what I did after I failed to "invent" this sequence on my own. Still, bruteforcing via pretests cost me quite a few points.

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

Why 10^9 in div1A is AC? I am about the solution without Sieve of Eratosthenes.

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

    It's kinda not 1e9, because not all the prime numbers are 1,2*1e6 and if it's like divisible by 2, that is finished in 2 iterations(assuming isprime breaks at right time).

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

    Actually, it's not 10^9 because of rare up to square root computations.

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

a bit hard contest , Just a Bit

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

Funnily enough, I solved A but not B. Can someone help me find the bug in my code (I keep getting a runtime error on test 7)? http://pastebin.com/tYXaAaEx

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

    try this case maybe you r not checking for numbers out of range 5 5 4 37 4 4

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

      Thanks! That was the issue. All I had to do was change "<= n" to "<= 100005" in line 25!

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

Guys, why SolveB was easier then A? More people solve B!

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

    For me, the description of the problem A was very confusing.

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

    I think that many people didn't think enough on A.

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

    The authors forgot to mention in problem A that the song continues to download as it's playing. Their mistake is understandable -- what they meant is reflective of real life -- but I can definitely see how it confused people.

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

    A becomes more easier when you realize a statement, and much more easier when you realize a solution.

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

How to solve B(div1)?

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

    bell_number

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

    Let's say that equivalent numbers have same color. And all numbers such that they are not equivalent to themself have color 0. Let Fi be the number of ways you can color n points in exactly i colors. Then it is easy to see that . Now the answer is because order of colors except 0 doesn't matter here.

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

Problem A has the worst statement i have ever seen in my life, i don't want to ofend you guys, but it was really bad, poorly explained, i don't like to do try/error on contests, even the clarification did not help much either.

Overall felt the contest was rushed and not tested enough (statements where not good) that is my opinion , of course people that guess the tasks only by input and output are going to give me negatives, but i don't care, had to speak up.

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

    I agree with you lol

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

    I agree with you about Div2 A, but the rest of the contest seemed ok to me, just a bit harder than usual.

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

    Definitely agree. The examples didn't make much sense, and the clarification was pretty much exactly the explanation for the example(which was also confusing). Maybe a picture would have helped.

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

    You are right, problem B was solved by more people than A! I wonder, how hard it was! (I don't know how hard because I am still unable to understand the problem.)

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

      I guess A must have a bunch of tricky test cases, so even though I got the statement in one go, I preferred not to submit.

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

Does anyone have something better than randomization for div1 D?

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

What is solution to Div1C? Is 2-sat involved?

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

    Exactly. You can use 2-SAT to check if there is any correct word with given prefix.

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

That moment,when there are two cheaters in your room and u hack both of them :)

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

problem statement for problem A.(MUSIC) was very poor had to find meaning from test cases

→ Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it
  • Why were the TLs in C-Div1 so strict? I lost much time optimizing my 2-SAT in order to pass the pretests.
  • Also, D is very similar to this task on Polish SPOJ: http://pl.spoj.com/problems/AL_09_04/. Translation: There are n points on the plane. Can you cover them using k lines? By the way, has anyone tried solving the problem using meet-in-the-middle technique?
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    tfw you optimise againt TLE and get RE instead

    also tfw I know I'm going to get WA

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

    There is no need to iterate through all characters from 'a' to 'z' while finding next symbol. One can observe that we can change any vowel to other vowel, and any consonant to other consonant, and the status of the transfromed string will be the same, e.g. whether it's in language ot not. So, finding next symbol requires exactly two 2-SAT checkings and therefore, you can solve this problem in O(NM),

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

      I had this optimization from the very beginning.

      What I did later was: (a) change the adjacency list in 2-SAT into adjacency matrix, (b) return -1 if M > 3N(N - 1). It worked something like two times faster and it passed pretests. (Of course consonant-only alphabets killed me...)

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

      I wasn't iterating through all characters and still barely managed to fit within TL, spending 35 minutes and 10 attempts to make it :)

      Rough bound which I got: 200*200*4=160000 rules; 160000*2=320000 edges in my graph. 320000 on DFS + 320000 on RDFS=640000 operations on getting strongly connected components.

      200*2=400 calls of 2SAT while looking for LCP of answer and word from input; 200*2=400 more calls of 2SAT while restoring answer.

      640k*800=5.12*10^8.

      Quite a lot, now I am not surprised with TL16 :)

      I am pretty sure that it can be implemented much better (and I'll look at other implementations to learn how to make it faster, thanks to authors), but looking at list of attempts with TL16 during contest — I am not the only one who struggled with it :)

      At some moment, looking at guys with time <0.1 on pretests, I thought "OK, I screwed up with wasting a lot of time on implementing obvious solution while I had to come up with something smart".:)

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

        mnbvmar, I_love_Tanya_Romanova, I see you. Indeed, I didn't think straightforward approach could lead to TLE. Sometimes it's better to spend more time to think and use not the very 2-SAT algorithm, but only ideas from it)

        We can find transitive closure of 2-SAT graph in O(NM) before processing string, and the only information we use from it is reachability from a to !a and vice versa.

        Now, when we have some prefix, we can fix vertices that must be visited in any case (respective to positions in prefix), and after that, while processing two vertices correspoding to other positions in string, we can use information about reachability to decide whether vertex to use.

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

Looks like about half of the solutions for div2 A are failing...wow...

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

    Is this the first time the A problem has had less than half the solves of the B problem?

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

O(n^2) space complexity solutions are getting accepted for Div. 1 B ? Like seriously ?

EDIT : so wow , much butthurt. I should write these kind of opinions on the complexity of solutions more often just to see the "butthurt impact" it has on people.

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

    Why not? n = 4000, n^2 = 16e6?

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

    "I can't calculate or try custom test, but it's totally not my fault."

    your post in a nutshell

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

      Do me/you a favor and multiply that number by 2 and "calculate" the difference between 256 and that number. Then use the acquired info to understand that two arrays of that size + bunch of other stuff won't fit in 256mbs of space.

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

        You only need binomial coefficients in a 2D array. Why multiply by two?

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

        why "two arrays" ?
        there is only one 2-d array, another one is linear.

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

          I was not going to code "your" solution was I ?

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

Thanks for the awesome contest (especially D and E)!

To get D accepted, I need to add "if (k == 0) return;" to my solution. First I lost Yandex because of a bug in the prime number generation, then this :(

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

    What you did wrong in prime number generation?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it 
      int n = (int) 1e6;
int[] pr = new int[n + 1];
Arrays.fill(pr, 0);
for (int i = 2; i * i <= n; ++i) if (pr[i] == 0) {
    pr[i] = i;
    for (int j = i * i; j <= n; j += i) pr[j] = i;
}
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        and where is bug ? It looks like the algorithm described on wikipedia https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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

          for (int i = 2; i * i <= n; ++i)

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

            ? On the wikipedia is the same for i = 2, 3, 4, ..., not exceeding √n: , but Petr used trick i*i <= n

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

              For p prime greater than n1 / 2, pr[p] = 0.

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

              so all the prime numbers greater than square root won't be processed.

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

        Ohh, I did the same mistake in Hacker Cup initial round, but first of all experience programmed like you did and specially in final which result in giving you 2nd spot. As I_love_Tanya_Romanova said, you are really unlucky in problem C for last couple of years.

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

        I was actually curious what problems people would see with this code. I see the following:

        1. Hardcoding n=1e6 is a bad idea. Had I not done that, I would've noticed the bug on the sample input.
        2. Using two different types of special values (pr[i] == 0 and pr[i] == i) to denote the same thing is a bad idea. I should've just filled with pr[i] == i initially.
        3. Issue 2 has appeared because I've initially had the code written with boolean array "pr", then converted it to integer array since I needed any divisor in the solution below. Had I thought the solution through before starting coding, this wouldn't have happened.
        4. I forget to convert actual pr[i] == 0 special values above sqrt(n) into pr[i] == i — this is the "final bug", but I think it's important to notice the three above issues that have led to it appearing and going unnoticed.
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          Actually I was also quite surprise by the fact the you initialize the value of array with 0 as default value which is not needed indeed. Then these two things comes into my mind.

          1. You started with initializing all the array values with -1 then changed it to 0.

          2. You had the boolean array(which is least likely) and changed it to int array as you use IDE so it suggest where you need to change.

          And btw I think p[i] == i, and initially filling the array value as its index would have been a better idea, it would have reduced your chances of making mistakes but you know better than me and sometimes minor details decide the result.

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

          If you remove just this line — pr[i] = i; and replace it with if (pr[i] == 0) the resulting array will be filled with 0 for primes and lowest divisors for non-primes.

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

Can someone explain what did DIV 2 A want us to do? I spent around 60+ minutes, and found it very unclear/contradicting. Not complaining about problem statements, but can someone explain it? Not the editorial, but phrase it in a better way.

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

    You have to sum the infinite geometric series with the initial value being the current amount downloaded and the rate being (q — 1) / q repeatedly until the current downloaded is greater than or equal to the total length of the song.

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

      Thanks chaosagent :)

      It is a shame for me that I designed this algorithm but discarded it for the reason of precision errors may take place :/

      I should have tried :|

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

        I actually failed the system tests because of floating point precision... I just deleted a few zeroes and now it works and I am very very pissed off lol

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

Bad luck!... Get AC after change EPS from 1e-9 to 1e-6 :( ...

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

Waiting for Editorial. I want to see jury solution of Div1. D.

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

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

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

Hoped to stay in Div 1 this time, but because of a really stupid mistake in Div1A, will probably go back to Div 2. :(

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

I only submitted B, and got a rating rise :D

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

    Actually I believe problem A was Harder than problem B.

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

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

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

it was the worse A that have been prepared !!!!! i solved B in 7 min and C in 20 min But not A !

but other problems were fantastic!!! WOW ;)

thanks for reading!

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

Not my best performance, plus part of code editing is hidden under Chrome, but still — screencast

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

I had an unusual and impressive experience in this contest. My program for problem C outputs -1 after running about 1.9s. And I allocated a block of memory with the size of 1000000. In my computer, my program only used 1/3 of the memory I allocated. During the contest I tested my program and everything went well. However on the grader, it runs much more faster and used all the memory within only about 1.8s seconds so it got RE before it output -1.

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

Amount of accepted solutions to A which had "Palindromic tree is better than splay tree" in code is damn too high!

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

    It's almost like a magical formula that gets solutions AC'd :D

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

    We've added this phrase just for fun (:

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

      Yeah, surely I know, but my point was that having this in code in most cases tells that people don't have an idea what is going on in this task and still managed to produce a correct code :P.

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

        Why take chances, that's why! Suppose some guy solved it without adding that line, and then got pretests failed for some reason, panics and adds that line, just in case it was the reason for wrong answer. Submits again, gets pretests failed again, realizes that line doesn't matter, but still, leaves it there, just to be safe, or maybe cause he forgets to comment it in a hurry.

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

For 569C - Primes or Palindromes?, reading the problem statement, how can one determine — "Up to which number he should calculate the number of prime and number of palindrome number" ?

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

    Editorial of the contest gives the mathematical proof that n < 107 even for maximum A = 42. So you can run once in your computer for A = 42 precomputing primes upto 107 to get the exact limit .

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

I forgot to use long long and get Wrong answer in problem 568A. TAT

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

    It seems many other people took this mistake too. What a trick!

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

I can't understand 3rd sample test case in B div1 "B. Symmetric and Transitive"

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

    1)empty set 2){x, x} 3){y, y} 4){z, z} 5){x, x}, {y, y} 6){x, x}, {z, z} 7){y, y}, {z, z} 8){x, x}, {y, y}, {x, y}, {y, x} 9){x, x}, {z, z}, {x, z}, {z, x} 10){y, y}, {z, z}, {y, z}, {z, y}

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

i think problem "E" can be solved by "divide and conquer & DP". there is a problem with much similar idea ( http://mirror.codeforces.com/problemset/problem/101/E ) with my solution ( http://mirror.codeforces.com/contest/101/submission/13598464 ) .

The basic idea for this problem is to maintain a DP for each index i which store the maximum of length of LCS from i to n. if array has gap at i, then store for every m numbers , otherwise store for only one number array[i]. TimeComplexity : (m*k) which looks fine. Space Complexity : O(m*k+n) ~ 10^8 > 128MB. to resolve this problem, we can divide the array into blocks of size SQRT. now, store all the DP states for 1st Block , then 2nd Block and so on. so Space Complexity : O(sqrt(n)*m) ~ 3*10^7 , which looks passable. decide the bucket size accordingly.

Edit : Space Complexity does not passes. looks slightly greater than expected.

→ Reply