PrinceOfPersia's blog

Codeforces Round #362
By PrinceOfPersia, history, 8 years ago, In English

— Hey, It's me again. Plain to see again...

— Oh crap, it's PrinceOfPersia again :|

I'm here to introduce you: Codeforces round 362. It's gonna take place on 196th day of 2016.

I'm the writer of this round. Not as always, there are 6 problems. I hope you enjoy.

I want to thank LiTi and Haghani for testing this round, danilka.pro and GlebsHP for helping me prepare the problems and MikeMirzayanov for legendary platforms of Codeforces and Polygon.

The main character of this round is Barney Stinson (high five ;)) and you're gonna help him with his problem.

I wish you all lots of Accepted solutions and hope to see no Skipped solutions ;)

Scoring will be posted soon.

GL & HF!

UPD: We decided that the contest has 6 problems (in each division, 4 shared). Duration will be announced as soon as we decide, but It's gonna be between 2 and 2:30 (inclusive).

UPD1: Duration is 2:15.

UPD2: Scoring is standard in both divisions: 500 — 1000 — 1500 — 2000 — 2500 — 3000

UPD3: Check out the editorial!

UPD4: System testing is over. Congratulations to the winners!

Div.1 Winners are:

  1. jqdai0815
  2. jcvb
  3. sankear
  4. matthew99
  5. Zlobober
  6. Claris
  7. Endagorion
  8. Reyna

Div.2 Winners are:

  1. variance
  2. holy_collie
  3. kimiyuki
  4. O__________O
  5. hs484
  6. czllgzmzl
  7. kimden
  8. jtnydv25
  • Vote: I like it
  • +441
  • Vote: I do not like it

Comments Comments (160)
| Write comment?
»
8 years ago, # |
  Vote: I like it -36 Vote: I do not like it

Why are you talking to yourself? :/

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

    You know I am Chinese, and I hate to read the foreign names such as Stinson.It is too hard for me to pronounce, so I decide change it in to “诗汀尚” in my mind.it is good for me to understand the meaning of problems!

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

Nice to meet you again.

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

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

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

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

announcement shud have been --

The main character of this round is .... wait for it..................Barney Stinson

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

Please do not put minuses :(

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

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

It is Rated ??!

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

    I think if this round won't be rated, they would write Codeforces Round #362(unrated).

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

hoping for an interesting problemset.. :)

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

I hope non of the problems statments will be "you have to help Barney Stinson to meet your mother"

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

Hope to See a Problem about the Brocode now that is going to be interesting to solve :D

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

I hope the problems are translated properly to English. Some of the problem statements in the previous few contests could have been better.

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

I extremely believe this round will contain less math problems than your past ones.

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

Is it rated?!

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

Will it be possible to connect to codeforces.com during contest?

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

I counted, Barney Stinson is truly have two hands and ten fingers, let's high five :P

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

Today is 2016/07/14, and it's 14^2 = 196 day of year =))

Wish all contestants luck =))

anw, this contest is my 40th contest, and I nearly get Expert =))

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

So long that rng_58 has participated on CF. Waiting to see Petr and tourist too.

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

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

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

I hope problems will be prepared better than Hackerearth June Clash 2016 (which is still haven't been rejudged)

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

    Not my fault. shef_2318 prepared the checker for approximate problem(NOT ME) and we told admins to rejudge it and they did nothing :|

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

      Your fault is that despite my warnings during the contest you haven't found bug in your checker. It was very easy to find, you just mixed up 1-indexation and 0-indexation.

      Actually I don't want to offend you, just want to say, that quality of those contest was not high, despite the fact that the problems were the cool. Hope that this one will be better.

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

      It's nice etiquette to say "sorry" instead of "that guy fucked up". It's not the first time I see your comment saying that sth is someone else's fault. Do you want to be necessarily mentioned by other organizers after you make a mistake?

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

i'm excited for this unusual round with 6 problems i'll try my best to solve atleast 3 of them.

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

Hope that, Barney Stinson face easier problems than the previous (#361) Div2 Round.

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

hope to get plus rating. I can't progress and getting frustrated :(

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

I think it's going to be an awesome round because the awesome man is its main character!

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

is it just me whose codeforces is working very slow and sometimes not even opening? its working slow since last night's contest, every other website opens instantly except codeforces.

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

Hope for 6 problems involving queries... :D

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

I hope to turn to cyan color ! :D

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

I have two wishes: 1. The English statements being clear. 2. Problem A loads up before 10 people get AC and we are like loading.. :/

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

I'm lol about the duration time)

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

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

You were the author of round #326 and now it's round #362. Pretty much awesome :D :D :D

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

нестандартненько

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

It's going to be legen- wait for it......

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

Except for maybe two rounds years ago, it's going to be my first round on Windows. I'm trying to install some IDE right now. Wish me good luck!

#mylaptopbroke

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

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

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

there is an extra zero in "25000" :P

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


I just captured a legendary pokemon

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

Congratulations to yao981113 for getting a perfect score on IMO! Celebrating by doing cf

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

    Congrats ! Who is he IRL ? My student got silver and I'm also really happy.

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

'Barney consider a girl x to be better than a girl y if and only if: girl x has weight strictly less than girl y...'

That's how K-pop fans harm their idols by putting them on a diet and making them skinny. I miss their healthy bodies.

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

    1 kilogram is the ideal weight.

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

You should be able to resubmit your hacked solution even after you've locked it. I feel like this is unfair for all those people who either lock problems for fun or by accident. Please bring justice. I know some people may copy other people's code, so maybe say able to resubmit up to 10-15 minutes after solution was hacked?

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

    Wut?What if you copy someone's code? and btw you can't "lock" it by accident.

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

      Well if your solution is hacked, shouldn't you at least be able to have a chance to redeem yourself? How about when your solution is hacked, you can no longer view other people's solution for that problem? I feel bad for losing 750 points because of unable to resubmit...

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

        You should lock your code if you are really sure. I just lost ~950 points because I missed one case.

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

          I guess you guys are right. Unfortunate, yes, but I am new to hacking/locking so sorry for complaint. Was fairly surprised and frustrated when I found out I couldn't resubmit. Ok, will reconsider to lock problems or not in the future.

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

            If your problem is not locked, then you can resubmit if you are hacked. Resubmitting with a locked problem is totally unfair, because you could just upload another contestant's source code. Also, that's the beauty of it: "you can hack only if you lock, do you really want to?"

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

        You can still redeem yourself by hacking other's solutions though.

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

    This would be a very bad idea. If your not confident in your in your solution don't lock it. You can't allow someone to copy someone else's code in the middle of a competition.

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

0.0e0 made my place Kappa

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

    "**b can not be non-zero if a is zero**" That shouldn't be allowed

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

      read again, carefully

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

        I did, it means that either a or b must be positive, both of them can't be 0.

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

          "b can not be non-zero if a is zero"

          maybe this way: b has to be zero if a is zero

          so 0.0e0 is totally fine (unfortunately for me... ).

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

      0.0e0 a=0 d=0 b=0 what's wrong? b isn't non-zero

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

I believe DIV2 D is a really cool problem :D I got the idea what to do but I couldn't finish in time :'( Really nice problem btw :D Thanks PrinceOfPersia

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

What's the idea behind Div2D/Div 1B? Couldn't find the formula for a vertex :/ Edit: I messed the letter, meant Div 1B :D

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

    Div1A: You go up from each vertex up to their LCA. In query 1, you add cost to those paths, in query 2 you sum and print. I saw a nice trick to go up to LCA — at each step go to parent of the vertex with the largest index, until both vertices converge. But there are other ways, e.g. using set to find intersetction of two chains, or going up to root and then down to lca.

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

      I meant Div1B, I messed up, but thanks though :)

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

        In Div1B, you first compute all subtree sizes; then for each node the expected time will be time of the parent + 1 + (sum of all subtree sizes of siblings)/2. Because by linearity of expectation, any sibling will go before current child with probability 1/2 and dfsing that sibling will take time equal to size of the subtree.

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

          Thanks, I was not that far away from that :)

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

          Thanks for this, I found it much better to understand than the editorial

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

          thanks a lot! :)

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

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

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

Div 1 E: Heavy Light Decomposition?

Find the minimum on each path and then set that node to Infinity?

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

How can I avoid TLE in C? I made a program with matrix dynamic, So My program's time complexity is(KlogN) but It got TLE...

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

    The formula is 1 / 3 * (1 + ( - 1)k / 2k - 1). You just need to exponentiate 2^k modulo. Other computations are fast.

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

      I got it. Matrix Computation was slower than I thought... Thanks!

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

        Alternatively, you can note that it is sufficient to know the exponent for prime p, so you only need to do log(mod) exponentiation, instead of log(N).

        EDIT: 19131411

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

          Hi, does that property works also for matrices? I mean if A is a square matrix and I the identity matris, then A^(MOD-1) = I mod MOD?

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

            Hmm, it seems I assumed it works during contest, and I have no proof or idea for proof. Will try to google around to find whether property is actually true.

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

              I also assumed that, it worked. In yesterday's contest I tried to used in problem C but doesn't work. I already searched and that property doesn't apply for matrices. I would like to understand why in this particular problem it worked

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

      can you explain how to get such formula?

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

        Consider the matrix approach. The matrix is something like [[1 1 0][1 0 1][0 0 1]], and it equals to ([[1 1 1][1 1 1][1 1 1]]-I). Expand it.

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

Div2C test 3 and Div2B hack? ;(

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

Kind of silly that a linear solution to Div2 A passes when such a nice O(1) solution exists.

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

Problem C: 5.0e0 hah. After an hour and before locking i realized my solution will fail such thing so fixed + submitted again. But then another guy in the room already did 11 hacks :| so couldn't make use of this to full extent

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

I think pretest for problem B is very very not good :( :(

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

I think Time Limit for Div1\C was too strict, at least my solution is O(k * log(a) * matrix_multiplication), which I thought was fine, but I need extra optimization to pass pretest. 19127740. I guess it will be TLE on final Test :(

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

I don't know why, but codeforces said that my input for a hack is invalid, however, it is valid, please check.

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

Thank you for the quick editorial !

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

Sorry I am wondering what is wrong with these two solutions... Please tell me what is my mistake div2B 19118037 div2C 19132537

Edit: i saw what i missed on div 2 b

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

    Since you are using map, there needs to be a comparator function to compare its keys ie pair of bitset or bitset in this case. Apparently, there is no comparator function. Hence, the compilation error. You can either implement a comparator yourself and use it or change key of map to pair<long long,long long>.

    Here is how to make comparator function: here (Although there is error in your logic as that gives WA)

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

Dayum, first contest in div 1, problem A scared me, I thought I needed to do Lowest common ancestor, then I realized it was easy when 30 minutes remained. but I wrote v/x instead of v%x in my code, and realized 1 minute after contest ended :(

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

I've always sucked at texting girls, so I didn't even bother with Div1D

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

Div 2. B: someone tried to overcome 0.0e0 hack: "for(; i < posE; i++){ sum += string[i] }; if(sum % 48 != 0){ print '.', ... }"; 0.888888e0 xD

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

whats the idea in Div2 D ?? how in general to approach probability questions ??

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

    Learn math ;)

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

    There's no "general approach".

    But an important thing you should know is that expected value has linearity, i.e. you can add them directly. Then if you want to know the expected order of a node u, you can check how many nodes are visited before this node. There are 3 cases:

    1. u's ancestors: they are always visited before u

    2. u's decendants: they are always visited before u

    3. else: they are visited before u with probability 0.5

    Then the answer is simply 0.5(n-u's decendants+u's ancestors+1).

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

You should improve pretest quality. It really weak this time.

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

    Very strong pretests would make hacking much harder and an interesting feature of CF would be rendered useless. I assume, that in some cases problem setters might even avoid particular corner cases on purpose.

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

tricky case in div2 B all digits are 0 including answer :)

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

Couldn't hack Div.2 A C++ solutions with 0 2 1_000_000_000 :'(, only one Java.

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

Wasted an hour on precomputing for small values of n and trying to debug this whole thing in Div2 D only to find out that I have completely forgotten about the case when no additional subtrees are visited prior to entering the vertex.

Managed to correct the solution, didn't manage to submit it in time. Damn.

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

if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;
if (!prod) cout << 1/1;

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

I tried to hack two solution on problem A_Div2 which use while loop with this test case :

1 2 1000000000

but I failed , I think it must give TLE on such solutions :\

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

    10^9 simple iterations is easy for CF servers

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

      If I've known this earlier, it could've saved me from getting WA53 with formula :p Thanks for the information.

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

This round's problems is so interesting! I like this round although i don't get many points

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

too much hacking in one round

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

Why so strict limits for div 1 B? I used double variables for answer and O(n) complexity and my solution runs in 750 ms(C++).

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

Ques 2nd should be rejudged. Your test cases don't contain 0.3e2. The solution 030 is also passed.

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

    if the number before this decimal is zero, then the number after 'e' must be zero. Read the problem statement.

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

The problem statement on Div1 B says "The second line contains n - 1 integers". This implies that there is a second line (just with 0 integers). Yet we are not given a blank second line. This is the only thing that broke my submission, isn't this test data invalid?

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

The feeling when you have almost coded Div1F when the contest ends, and it would have passed the tests.

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

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

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

Can someone help me understand why my B gives TLE? it should be linear.

Your text to link here...

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

    I found it.

    what I did was manually add for each node v, the sum S[w]+1 of the number of sons of each vertex w which is a son of the father F[v] which is not v.

    I should have just done S[F[v]]-S[v]-1. fail, sigh.

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

WA on pretest 1 in Div2B. Any ideas?

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

    Maybe it contains invisible characters.

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

    In your solution, line number #52.

    It should be "a < len". Why would you like to run till "a <= len"?

    Update:

    After correcting above mentioned error in your code, I was able to get AC on it. 19134004

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

    You reminded me of this blog when I first started CP

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

    After running your code locally, it has character with code 0 after the output but before the newline.

    38 35 34 2E 39 00 0D 0A
    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Ehh... Thank you :/ I thought I would destroy my laptop after 10th submission :P I think that these types of invisible characters should be ingnored by the checker like it is done with "endl" at the end. It would be nice.

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

hey something is seriously wrong with the final testings.I submitted the same code again after the contest and it gives correct ans on on your system and my PC too.Please recheck it.You could even compare both codes.Problem "DIV2B"

During Contest- http://codeforces.net/contest/697/submission/19126571

After Contest- http://codeforces.net/contest/697/submission/19133631

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

Unlucky for me... If you use fermat little theorem on div2E... if you have a multiple of mod-1 then you cant let it stay at 0 to use formula... must say if (n==0) n=mod-1;

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

Why did I think that all strings are unique in div1D? :-(

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

Another one easiest way to drop 200 places! 19126039 19134075

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

    Forget to write "if (y < 0) y += MOD — 1" and lost C.
    Thought that all strings are unique and wrote c[x] = a[i] instead of c[x] += a[i] and lost D.

    GGWP :D

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

Really nice round, and a great problem set!

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

Did anybody else find the problem statements, well, just "too much"?

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

    I found it was kind of bitter sweet. I enjoyed the puns ("slapsgiving" in A was also nice). I also did not like that it took the focus out of the problem.

    BTW, isn't it the three eyed raven who has time traveling capabilities. Is Jon Snow the next three eyed raven? Can't wait for next season!

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

How to fuck up your computer in three simple steps:

  1. Read Div2C/Div1A

  2. Assigns two huge vectors after seeing MAXU and MAXV

  3. Profit

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

I am new to python,and I wonder if there a way to read data like using freopen in cplusplus?

if it has, need I delete the input code before I submit the code? Or it there if a way that I don't need to delete the input code like using ifdef definition in cplusplus?

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

    You can use sys.stdin.readline().strip() to read your lines.

    import sys
sys.stdin = open('thing.in', 'r')  # comment this out when submitting
stuff = sys.stdin.readline()
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi can someone help me out why this solution for DIV II/Problem C is failing on testcase 39. I tried with lot of smaller test cases but couldn't figure out mistake.

http://codeforces.net/contest/697/submission/19167786

→ Reply