MikeMirzayanov's blog

Codeforces Round 350
By MikeMirzayanov, history, 9 years ago, translation, In English

On May, 5, 16:05 (UTC) Codeforces Round 350 is going to start! Yes, pay attention to the non-standard start time.

I took advantage of my official position and the round is expected to be a bit experimental with an expanded set of problems. Perhaps for experienced participants (sorry, Div 1) it could seem easy. This time, emphasis was placed on the main target audience of the round: so in the round will be a lot of very simple problems, but even the top of the second division will find something interesting. In addition, one of the problems will be offered in two versions — in a simplified version with small constraints and in a harder version with greater constraints. Thus, if you immediately realize solution for large constraints, you can write and submit the same code on the both version.

The problem writers are me and fcspartakm. We hope that you will enjoy the problems and the round will be fun and useful!

The expected scoring is:

  • A: 500
  • B: 750
  • C: 1000
  • D1: 1000
  • D2: 500 (i.e. the complete solution of D is 1500 points)
  • E: 2000
  • F: 2500

Good luck!

UPD: As it was pointed in the comments we have a tricky point about hacks with problems D1/D2.

  1. To avoid the situation when participant locks the problem D1 and looks the solution of the problem D2 in his room, you are allowed to lock the problems D1/D2 only together in the same time and only if both of your solutions for this problems passed the pretests. In the other words, the possibility to lock D1/D2 will appears only after you solved both problems. The problems D1/D2 will be locked together in the same moment.

  2. To avoid the situation of double reward for hack of D1 and D2 of the same participant, the participant A after successful hack of the participant B on the problem D1 loses the possibility of the hack B on the problem D2. Similarly if the participant A successfully hacks the participant B on the problem D2, then A loses the possibility of the hack B on D1.

UPD 2: The round is over. My congratulations to the winners! Here are the heroes of the round.

The Top-5 among the official participants:

  1. xlk200
  2. TableEnterer_Lin
  3. cykhhq595
  4. xxxholic
  5. A_Navie_Moer

The Top-5 among the unofficial participants:

  1. anta
  2. -XraY-
  3. Um_nik
  4. halyavin
  5. Enchom

UPD 3: Problem analysis is now available.

Tags 350
  • Vote: I like it
  • +466
  • Vote: I do not like it

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

So is CodeForces trying to move towards larger problem sets for a contest? Cause I think it'd be a lot more fun if there were more problems to try and solve per round.

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

Will it be rated?

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

Will contest duration remain the same?

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

    /contests page shows it is 2 hours and 30 minutes.

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

If D2 score decrease 8 per minute (as a usual round) . then what will remain after 30 min?! only 250 points?!

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

    I thought that the decrease was dependent on the problems score? If a problem is worth 500, at the very end of the contest it will decrease to be 250 points. In a regular 2-hour contest, it decreases at 2 per minute, but in a 2.5-hour contest it will decrease at 1.67?

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

Also notice that problems are becoming harder and harder as the scoring distribution has also changed.

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

Having a problem with two subproblems in a regular Codeforces round with hacks may be exploited in a following way: suppose there are two coders in the room. One of then solves only D1 and successfully submits it, while second solves both D1 and D2 with the same source code. Then, if first coder locks his code, he is able to read a solution for larger constraints if he opens a solution of D1 by the second guy.

Something has to be tuned here. How about leaving a possibility to hack only for D2?

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

    Locking D as a whole should work too

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

    But if the first coder solved only D2, there may be people who submitted same solutions for D1 and D2 so if the first coder locks his D2 solution, he can find out the solution for D1 without being able to hack D1 solutions.

    UPD: vice versa for D2 and D1

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

      All correct D2 solutions will probably be correct D1 solutions

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

        Not necessarily. I have a correct D2 and an incorrect D1. When submitting D2 there was an overflow error which I forgot to fix in my D1 submission :(. Maybe D2 should have been worth at least as much as D1.

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

    There is also a possibility that D1 is "solve it" and D2 is "now write a checker".

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

      in a simplified version with small constraints and in a harder version with greater constraints

      I don't think so, I think it will be like write quadratic solution for D1 and quasi-linear for D2.

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

    What if a rule can be made like this "To hack any of the sub part of D you need to solve both of them first." ?

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

this gonna be Enjoyable , I'm in !

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

I have my Exam tomorrow.But this round looks interesting. I'm in!

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

I think this new form---one of the problems will be offered in two versions is very great!The equivalent of i could not finish big data algorithm can also get scores，right？For the beginners like us is really nice！I hope this form will be keep in the next rounds.I will support codeforces forever and i am expect codeforces can launch more good forms like this!Come on,codeforces!!!

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

Partial Marking. This is going to be pretty interesting. :)

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

Rule number 2 is not good ! In case someone submitted same code twice and I hacked one code in 90% of cases it means the second code is also not good. So some other will see it and receive points for second subtask despite he didn't find bug after first chacking.

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

    Also there can be 2 completely different solutions, why hacking one of them prevents from hacking another?

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

      I think that better option is receiving 200 points for hacking both solutions, or not allow hacks for D task.

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

You forgot to thank yourself.

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

Test #11 is Evil

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

well, look at this

Desperation on a whole new level :v

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

What a Binary Search Round! Enjoyed it to the core...

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

Too easy IMO.

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

How to pass test 4 in problem F? Easy problem, but I can't find bug in my code :(

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

    Same. test 4 for F killed me.

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

    Maybe this test can help you: 330055 33,the answer is 33005

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

      Weak tests at F,my solution doesn't work for 323445 32,didn't have time to fix that,feel so bad...

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

        My solution works for both but failed Pretest 4. T_T

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

          in pretest 4,you put the second string first,and after that the rest of digits,i know that for sure

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

      What is the substring?

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

        fixed

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

          I pass both "330055 33" and "323445 32", but still fail on pretest 4.

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

            Same. LOL. Magic test 4

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

            don't know what is your mistake,i checked these tests and after fixing my bug i got pretests passed

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

    I suppose pretest 4 is huge. I've tested my solution with test generator, still no idea what fails.

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

how to solve Div2 A?

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

    First of all we are bound to have 2 off days in each week , so first find the number of weeks and multiply it by 2. Next in case total days are not divisible by 7 we need to see if there are any remaining days or not (i.e. total days % 7) Now if there are 1 extra days if we are unlucky it will not be an off day , thus min off day is unchanged , but if we are lucky it will be an off day thus max off day is incremented by 1 , again if there are 2 extra days those 2 may not be off days thus min day is the same , but those two can be off days so max day is incremented again ( i.e. week*2 + 2 ) This logic extends up to extra day = 5 , but if the extra day =6 we are bound to have 1 off day so min day will be incremented then and max off day as before incremented twice ( i.e. week*2 + 2).

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

halyavin used my successful challenge of D2 to identify the wrong solution and got challenge of D1. :)

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

Interesting

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

Does this happen alot??? But still it was a great round.

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

What do you say when you try to submit and the contest gets over — "Every second counts"

Just a heartbeat away. RIP Question F.

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

    Bro there is high chance of getting it wrong still :P

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

Can string k contains 0 digits in last task ?

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

Am I the only one who miss-read E's statement (such that you need to delete just the pair of brackets but not the whole substring) and implemented an implicit treap?

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

I think it should be a better contest but ...!!! :)

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

spent so much time writing nice code for E

http://codeforces.net/contest/670/submission/17746555

only to forget to change the size of the segment tree

I feel like shit

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

    Next time generate maxtest & check your solution before submit.

    It helps me avoid this mistake.)

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

Problem E why my solution Got Tle on test 12 Here is code:code..

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

how did a O(n log(n)^2) in problem C gets TLE on test 125 17726278 ?!!!!

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

I think test data for D is weak, 17727910 can be broken with an overflow, with large N, large Ai, and small Bi.

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

Problem C got TLEd with O(n+m) Solution, But passes with scanf and stdio sync off.

Maybe the problem setters shouldnt keep it that borderline where 2 solutions of the same complexity have different result cause of I/O Methods.

EDIT: I was wrong, It is not the IO, but the use of map instead of unordered_map, but that still confuses me, even more so.

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

    Choosing I/O is the same as choosing data structures for the problem. There are more comfortable ones, and less comfortable but faster

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

    Regular cin/cout is hella slow — it's one of the first things you learn when competing. If you were to complain, for example, that sync off didn't pass while only scanf did, that'd be somewhat reasonable — but using regular cin/cout on 400,000+ numbers? Come on.

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

      it may pass only reading but there is also unordered_map,in genereal all the unordered_map solutions don't pass the test 132.

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

      EDIT 2: It's not inserts it's the access
      see this on unordered_map documentation

      time to go and punish myself for misjudging :)

      EDIT 1: It's definitely unordered_map's hashing
      So many inserts on a map must have been done in amortized constant
      map passed but all unordered_map solutions TLE

      I am not sure if I/O is taking time or is it unordered_map's hashing. Eh, I feel like it was a brutal test My stdio sync was off http://codeforces.net/contest/670/submission/17737941 Still TLEd I am going to test Python with raw_input(), it that passes , then cin,cout with sync off should have been allowed to pass

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

        There is an anti-unordered_map test (I hope mine is #132).

        The reading part should not be the problem.

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

wat

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

    Ouch. It is better go to sleep, rather than waiting for the end of systests.

    tnx.

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

    same :/

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

Great contest.
Very soft increase in the difficulty of the problems.

I want to repeat the experience :)

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

I'm gonna ask a very professional question: how do you use your time efficiently till system testing end? (except pressing f5 rapidly which I'm doing right now)

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

    switching between friend standing and common standing :)

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

      That's what I am doing too, actually. It works well, I must say!

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

    Instead of pressing f5 clicking the refresh button of your browser =D

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

How come this submission gave TLE on the C problem? 17725819

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

    Maybe it has something to do with mixing cin and scanf?

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

      Maybe because of unordered_map?Change into map and see what happens.

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

    I used the same algorithm:

    17733793

    but, i prefeer use only "cin" and "cout"

    and add: "std::ios::sync_with_stdio(false);"

    UPD: in worst case: MAP: O(log(N))

    UNORDERED_MAP: O(N)

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

What is the difference between simple map and unordered map ? I see many people prefer using the later.

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

    I said shit. I've learnt my lesson :(

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

    map is balanced bst (red black tree), the other one unordered is hasing based. While map guarantees O(log n) access, unordered_map generally gives constant time access however in worst case can lead to O(n) per access too

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

      Thanks that was helpful. BTW, in which cases unordered map can lead to O(n) per access .Any general idea ?

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

Too slow............System Testing?

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

    Because 100+ tests for each problem.

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

    Actually, it is better to have more complete testing rather than fast and accepting wrong solutions.

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

Problem D1 gives more points than D2, but it's actually the easy one. Isn't it?

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

    The idea is if you pass the large one you can submit it to both... so D2 is basically a bonus for passing the large input.

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

      I get your point, but how that could be better? It decreases the value of solving the hard version (if it turned out to be pretty hard, then it should be optimal to skip it and just submit the easy version, and your score wouldn't change significantly) IMO. Maybe I'm missing something.

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

        Doofenschmirtz Evil Incorporated!

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

Slowest System Testing EVER!!!

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

Is multiset much slower than map ? I got TLE for C due to multiset. I was trying something new and now it failed. :(

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

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

I got WA for setting High=1e9 in binary search for D2 . How to calculate maximum value High can get ?

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

    Didn't it failed on pretests? The first pretest had 2000000000 as answer

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

      NO it didn't . I first calculated the number of dish I can make assuming value of k to be 0 . then I BSed the answer with k involved and sum of the 2 was the answer . (For pretest 2e9 can be accomplished using k=0 and 0 after consider k so total ans =2e9 >.<)

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

    You can prove that 2e9 is the highest value of hi.

    If n=1 k=1e9 a[0]=1 b[0]=1e9 then the ans is 2e9 , and note that there can be no worse case than this.

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

    Suppose all ai's are equal to 1 All bi's are equal to 1e9

    k is equal to 1e9

    In this case the answer will be 1e9+1 but you have set high already lower than this so you will get wa. Above comments show that max hi = 2e9

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

    I was lazy to calculate it so I just set:

    High = (sum of all bi + k)/(sum of all ai) + 2

    (the +2 is redundant but you can never be too safe). This is a simple and obviously correct estimate. Using only that estimate we can conclude that High at about 1014 should for sure do the job.

    (ofc you can get better bounds but ain't nobody got time for that)

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

      >.< funny How 1 character makes a difference .

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

      For D1 I just used 1e9 (WANTED to be safe) for the upper bound and failed cause I wasn't aware of int overflow due to such small inputs! (But passed D2...) T_T

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

    The top possible value is 2e9. This can be seen by an example with one ingredient, where you have 1e9 of the ingredient and 1e9 of the magic powder, and you need 1 of the ingredient to make a cookie. You can then make 2e9 cookies with what you have.

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

    It's 2e9 + some const, but be patient, 2e9 + C not anytime is equal to 200...00 + C due to floating point precision error

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

Can someone explain me why I got TLE on pretest with this (problem B)? I used std::sqrt, don't think it will work so slow... http://codeforces.net/contest/670/submission/17732164

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

    I don't know if it is ok, to read long long with %ld?

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

    %ld is for long, which in most cases is equal to int by size, for long long you need to use %lld, reading by %ld gave you some trash inside n and k — http://ideone.com/NDPC4R

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

I liked the round, but if the system tests have to be this long, then no, just stick to the regular rounds.

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

DAMN!!! tomorrow is comming,but there're only 75% checked !!! So slooooww!!

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

To be safe,I set the high in D2 to 4e9. But my code fails on test #128 T-T

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

Can someone explain why have i got RE13 on B with this code http://codeforces.net/contest/670/submission/17726464/. It literally ruined this round for me.

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

    When i*(i+1)/2 == k you would get data[-1]

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

      Nope. I would get data[i-1]. i*(i+1)/2 — i*(i-1)/2 = i.

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

Waiting for system test to end like...

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

Why is there a penalty for Wrong Answer for pretest 2 in D2? Pretests 1 and 2 don't have penalties right?

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

    as far as i know , Only Pretest 1 does not cost u penalty .

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

like a boss! problem E:

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

    I did it the same way , it took me 20 mins of coding and more than 40 mins of debugging :)

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

That hash table hit me HARD!! What a great lesson by the problem writers :). Thank you, you guys make me learn something new.

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

Shouldn't this solution:http://codeforces.net/contest/670/submission/17745728 Fail on cases like "(((((.....)))))" if you start deleting right from the middle of the string this solution would keep iterating over all of the characters in the original string?

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

anti-hash table test was MESSED up...

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

Why did this solution — http://www.codeforces.com/contest/670/submission/17743870 receive a compilation error?

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

I know that it is unbelievable but I sure that it is happen, during the system test after all my problems have been test I found my rank is 644 and after the contest finished I found it 640 HOW!!!

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

    This already happened to me. I don't have any explanation.

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

D1 should be of 500 points and D2 should be of 1000 points. Higher constraints problem should ideally be having more points.

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

    And I automatically agree with you since I failed D1 but not D2 LOL

    But to not be biased, I think either scoring is fine. In the way it is it seems the large input is just a bonus score. Those who solve D2 are supposed to also solve D1 correctly anyway. (Well, except in the case of some overflows which many and I have overlooked because of small inputs...)

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

Nice

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

So tell me how the problem setters (or a contestant?) generated anti-unordered_map case? How to prevent our solutions from being hacked (´･_･`)

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

    I googled and tried to read gcc headers, but it's too sophisticated. What I could understood are:

    • unordered_map has a normal hash table implementation; it divides items into some bucket by its hash value and items with the same hash value are stored by linked list in same bucket.
    • hash function for int is just identical function (hash(x) = x).
    • item x seems to be stored at (hash(x) mod the number of bucket)-th bucket.
    • the number of buckets sometimes changes by rehashing operation.
    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D2. Not able to find any error in my solution. It fails in test case 128. Can someone please help in finding out the error. I uploaded the same code for D1 which got accepted. Here is my solution. Please help :p http://codeforces.net/contest/670/submission/17734861

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

I've been doing F and my code got Runtime_error after cout the output nad I dont know why. Here's my code: http://codeforces.net/contest/670/submission/17828267 Anyone can help, pls?? P/s: my English is not good sry if u mind.

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

In problem D2 if I take the value of "r" for binary search as 1e10 then I get AC but if I use r=1e12 initially then I get WA as the answer comes something arbitrary like 350488137400 in place of 0 .Is there any constraint on choosing the value of r in binary search as I have been stuck on quite a few questions where probably the problem was that my value of r was near the likes of 1e15 or higher?

WA on test case 2 with r=1e12:237333175.

AC on keeping r=1e10: 237326598.

Could anyone please help me out with this?

Edit: I figured out that my variable "a" was having an overflow despite being long long which gave me the error.

→ Reply