cyand1317's blog

By cyand1317, history, 3 months ago, In English,

Hi!

I’d like to invite you to Codeforces Round #431 which takes place at 16:35 MSK on 1 September. Please note that the timing is again unusual.

One of the problems is created by adedalic and KAN, while the others are authored by me. This is my second round here, and it couldn’t have been realized without efforts of: AlexFetisov, ifsmirnov, Tommyr7, winger and wu_qing who tested the problems; KAN who appears to be a meticulous guide throughout the preparation process; and MikeMirzayanov with the supercalifragilisticexpialidocious Codeforces and Polygon platforms — my deep gratitude to you!

Both divisions are welcomed as rated contestants and will have five problems to solve in two hours. The scoring will be announced later.

Once upon a time, in a virtual galaxy far, far away, there was a lovely young singer by the name of Hatsune Miku. One lovely day, Miku got a job as a vocalist in Vocaloid, and that was very exciting. People said, “Oh, Miku, you sing so accurately! And so emotive, too!” Soon everyone was talking about Miku, and there were songs and paintings and even lives for Miku. Miku liked that.

And you, are to start a journey following the emotions in Miku’s voice. Oh, by the way, a late Happy Birthday to her — August 31 is (was) her tenth anniversary.

See you then, and wish everyone few bugs and fair ratings.

UPD 1 Scoring will be:

  • 500-1000-1500-2000-2500 for Division 2;
  • 500-1000-1750-1750-2500 for Division 1.

UPD 2 System test is done. Congratulations to the winners!

Division 1

  1. dotorya
  2. Reyna
  3. SkyDec
  4. V--o_o--V
  5. koosaga

Division 2

  1. lmmortalCO (solved all problems!)
  2. ltg2030
  3. FoolMike
  4. HatsuneMiku
  5. MisakaKuma

Also, thanks to all who participated! Nicely done!

Check out the editorial with hints!

UPD 3 Complete tutorials and behind-the-scene fragments are out. Problem packages may be published soon, stay tuned!

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

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

Miku? I'm in!!

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

    Miku? I'm DEFINATELY in!!

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

    Bad luck. Solution for A and C was correct. If these two got rated then.... Alas! they got skipped.

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

want some downvotes, just ask is it rated? Just see my downvotes.

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

"supercalifragilisticexpialidocious" what ? :|

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

Two Faced Lovers <3. Tell your World <3. Miku Hatsune <3. Rated Div 1 contest <3.

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

I am new to codeforces... So can i join the contest? Because its asking for ratings...

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

    Yes, you should register in Div2 contest. However, you should not ask if the contest is rated unless you want to get -2137 contribution.

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

I just realised Hatsune Miku literally means first sound from the future.

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

I as well would like to know in the fullist if this contest on the code force will count towards my codeforce rating on the codeforces.com webite on the internet on the wires that are inside the tubes that the internet is made of.

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

Happy Eid for you all :D

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

Probably the best english I've read in a long time on CF, hope the problems will be as easy to read as the announcement :D

»
3 months ago, # |
  Vote: I like it -7 Vote: I do not like it

6:35 AM? Seriously? Gonna participate it for Miku Hope this round will not be a typical China round :P

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

bilibili (゜-゜)つロ che.... Oh wait wrong platform.

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

"Soon everyone was talking about Miku, and there were songs and paintings and even lives for Miku.

I'm sorry, what?

Have I missed the weekly sacrifice? I thought it was called off.

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

I think Miku will hire all the participants and solve her problems.But If she hire me and I solve any problem of her,In return, I will ask her to sing a song for me. So, I need her address and a spaceship. Wait, a spaceship will be slower. No problem, I will ask Mr.Tesla to build a inter_galaxy_traveler for me. For this Mr.Tesla will hire all the participants to help him build a inter_galaxy_traveler. Miku, you may live far, far away but no one except God will/can stop me to hear your sweet voice. Miku, You just have to wait for the payment untill I become an expert. I promice you it won't be long.

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

My birthday.Oh yeah! I'll be glad to with you in codeforces.>w<

»
3 months ago, # |
  Vote: I like it -21 Vote: I do not like it

Winner Winder Dinner Chicken

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

Hope for good quality problems :)

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

Codeforces with Miku is so good!I will be definitely in!!!(Although I 'm so weak...)

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

Happy birthday to HatsuneMiku! =w=

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

Am I the only one who doesn't know about Hastune Miku?

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

    Are you serious? ._.

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

      Well he/she may be a famous person in your country but I really had never heard this name before.

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

        You can serach her name in niconico or bilibili douga(douga is a website with many acg cultural videos).

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

    You can read more in Wikipedia, but feel free just to enjoy the problems without such background knowledge.

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

    before your comment I was thinking I'm the only one.

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

I like Miku~It must be an interesting contest!

»
3 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Please don't use these hard names in problems please. It makes difficult to understand also is it rated?

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

Eager to participate after a long time -> See Miku in the blog -> Decided to go to sleep instead.

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

Awesome feature of showing rating change in leader-board during the contest.

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

i hope there won't be long stories about Miku in the statements..

»
3 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I know a sentence to get lots of downvotes,but I will not say

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

Happy birthday, Hatsune Miku! Thank you for bringing so many wonderful songs to us!

»
3 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Codeforces means nothing, Miku means everything.

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

bilibili (゜-゜)つロ chess!!!Happy birthday Hatsune Miku!!!

»
3 months ago, # |
  Vote: I like it -76 Vote: I do not like it

Buy Baby Products_Your text to link here..._ Online India at Best Prices.

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

Last line of the blog : "wish everyone few bugs and fair ratings." :(

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

    Good news for hacker :(

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

    "few" means "not a lot", "a few" means "some", so in fact wishing few bugs is wishing well, while wishing a few bugs is wishing bad.

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

I am getting error : 502 bad gateway..

If it is problem of the site please check it so that it wont effect the competition.

Happy Coding!

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

Hope this round be rated!

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

    Hope this contest goes well!

»
3 months ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

Another anime-contest?) This year have many anime-contests)

Maybe next year will have >= contests with anime theme? Does someone else want it? :)

Good luck everyone! 502 will not stop us!

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

Please, don't start the contest till you fix the problem 502 Bad Gateway

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

    I am not sure, but looks like it was fixed(I tried refreshing 20 times).

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

      Now the issue will return because everyone who will read your comment will try to refresh 20 times :D

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

      This is not how you check it :)
      They need to look at nginx access.log.

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

Eid Mubarak to everyone :-)

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

Hope, 502 Bad Gateway don't appear during contests!

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

Scoring?

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

Miku~

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

And the count down starts...10, 9, 8, 7,...0

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

a

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

let it begins

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

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

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

Not able to hack ..... page is stuck at reloading again and again...

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

    This is experienced by some contestants. We're working on this, please go on to other problems first. Sorry for the issue.

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

    same issue here, and i am 90% sure i can't solve any of the other problems. also i am 100% sure the code i am trying to hack is incorrect. :-(

    EDIT: after refreshing about 20 times, i was able to successfully hack the above mentioned code. :-)

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

There are no memes in the comment section?

spits coffee

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

so after forty minutes i didnt solve problem a or problem b

i give up :( i should stop doing cp

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

    This contest looks to be difficult

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

      Welp,not only you, this contest difficulty gap seemed kinda much for Div2 contest..

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

Is was contest rate plz I need now teechr will fail my?\

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

Moderator I hacked the solution of user — "redcpp". verdict is saying unsuccessful but in his logs its written that his solution is hacked by me. Update marks.

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

Titles are all Hatsune Miku songs~

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

Currently 22 minutes left until the end of the contest, and I have been trying to hack one of roommate's codes for the last 5 minutes (with this error).

EDIT: I was eventually able to (successfully) hack this code, however I couldn't hack the (incorrect) code of another participant due to this error. And after repeatedly refreshing the page I saw that the participant had resubmitted a correct code (without being hacked by anybody else).

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

Div. 2 + Div. 1 round? More like Div. 1 + Div. 0 round. RIP Rating.

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

    I also think so, I couldn't even understand statements of c, d and skipped to E(Hope it passes though, or I will get -200 rating change).

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

      Ima get -100 at least for sure. E looks like a problem I can solve, but I just didn't read it. Now I have only A :(

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

    Pretest 3 on C is k = 0.

    Your code prints nothing but it should print a single character :(

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

      Oh yeah. I guess this isn't my day :( If I found that bug I would've solved it in the first 30 minutes.

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

    rip rating too , hate geometry so much :C

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

How to solve div2 d?

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

    sort

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

    for horizontal , consider the point to be at ( - ti, yi)
    for vertical , consider the point to be at (xi,  - ti)
    Now consider each diagonal (Same x + y) at a time
    Only points among the same diagonal will collide and each point's direction will alternate after each collision.

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

    First notice that instead of looking at time the person starts, you can simply set their x/y coordinate to -t (depending on what way the person is facing). Then notice that instead of imitating a collision, you can just swap the indexes of the people colliding, since they just swap trajectories. Then also notice, that you can place people in buckets based on the sum of their x and y coordinate (people with the same x+y go into the same bucket). In those buckets, every vertical person will collide with every horizontal person, and vice versa. Now, next thing to notice is that every horizontal person will hit vertical people in the order of their x coordinate. Therefore, the last index that carries that trajectory will be the index of the furthest right vertical person. Yes, there's a lot of noticing in this task. At this point you could probably implement it, but there are a few more things to notice if you want to have a nice, clean implementation, but I don't know how to explain what I did, so I'll leave it as practice (if someone really wants to I can try to explain)

    Also, cyand1317, I absolutely loved this task, thanks!

    Edit: while I typed this someone already answered. I hope this will still be helpful to someone!

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

      Thanks for the explanation, for me it's much easier to grasp than official editorial. Only last step (how to properly sort dancers and final points, then match them) is to be applied to your solution to get ACC. It's described in editorial, but if you don't mind I will explain it here to finish your solution.

      If you sort all dancers in one bucket wrt their initial x positions (for horizontal dancers it will be -t_i, and x_i for vertical ones), and sort all final points for this bucket in order (0, h)->(w, h)->(w, 0), you may realize the next thing:

      1. Dancer with leftmost x position will be always horizontal and it will end in the first (at the top of field and leftmost one) final point for this bucket (because when it collides with some dancer it immediately goes up with no collisions)
      2. The second dancer is actually the one who will make this only collision with the first dancer (then the first dancer goes at the top of the field). Then, if there are more final points at the top of the field, then second dancer will collide some vertical dancer and will go to this point. If there no such final points, second dancer will have no mroe collisions and goes to the second final point (with coordinates (w, y_i))

      The same logic could be applied to the next dancers... Just imagine the picture and you will get the idea.

      I hope this would be helpful for someone who doesn't want to spend 5 hours on this problem:)

      My submission.

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

        Thanks for completing my comment, here's my submission too, if someone's interested: 29986966

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

Supercalifragilisticexpialidocious problem C. (E div 2). Thanks >__<

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

The first time getting rank 25 in div.2

:)Happy

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

Did anyone pass problem DIV1 C with Mo algorithm working in O(n^(5/3))?

Btw by n^(5/3) I mean this optimization : http://codeforces.com/blog/entry/44711?#comment-292040

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

How to solve div1B? I feel so stupid

  • »
    »
    3 months ago, # ^ |
    Rev. 6   Vote: I like it +11 Vote: I do not like it

    Suppose a dancer travelling vertically having position Xi and wait time Wi, and a dancer travelling horizontally having position Yj and wait time Wj meet at time T. Hence,

    (Wi + T) = Yj and (Wj + T) = Xi

    This will be used to check collision condition and time.

    (Xi - Wi) = (Yj - Wj) and T = (Xi + Wj)

    Now, sort dancers travelling vertically by Xi and dancers travelling horizontally by Wj. Store dancer indices for each distinct difference (Xi - Wi) and (Yj - Wj) for each type of travellers.

    For one particular difference, consider 2 vectors, 1 of horizontal travellers and 1 of vertical travellers, each element of 1st vector will intersect with each element of 2nd vector. Final positions of dancers from these 2 vector will just interchange among themselves independent of other dancers.

    Collision happens in sequential order. That is i from vector 1 will intersect with j1 and j2 from vector 2 in order of j1 and j2, same holds other way.

    This sequential order can be used to decide final position of each traveller of these 2 vectors combined in O(n). You just need to traverse these 2 vectors in particular order. Sorting the travellers takes O(n * log(n)) time.

    Code

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

    Don't, it was pretty hard (IMO).

    You can group the people, so in one group all possible collisions happen, and no collision happens between groups. You have to group by pi - ti. The previous statements can be proved, for same and different pi - tis. After that, you can solve the problem for one person in O(1). I'll leave that thinking to you :)

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

How to solve div1C?

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

    Let's change find sum of max-min into sum of nxti-i where nxti is next element with value equal ai and nxti <= r. Now it's a very standart problem, I did it with bit and sqrt decomposition

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

      I came up with this, but you need to subtract the values on the first apparition of an element, how to do that? I'm shit at data structures :P

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

        Actually, only 2 or 3 values will get changed, so you can update it easily.

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

          Nvm I missunderstood your comment, now i get it, thx :D

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

I am surprised that I found Div-2 C pretty hard, but still more than 1000 participants solved it. Looking forward to the solution.

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

    a => 0 aa => 1 aaa => 3 aaaa => 6 ... a(n) => (n)*(n+1)/2

    16 = 10 + 6 => aaaaa bbbb 12 = 10 + 1 + 1 => aaaaa bb cc

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

      Although I cannot assure this is the right solution, I pass pretest in this way.

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

        Here is the proof that this approach is indeed correct. Firstly, breaking the given sum into characters, it is evident that we can compute the cost of merging characters of one type, and sum across all characters at the end.

        Now, we claim that in order to merge n of one character, the cost required is always regardless of how we merge. We prove this by strong induction on n,  the base case being obvious.

        Now if the last merge is merging a string of length x with a string with length y,  by induction hypothesis we get that the cost so far is Now the last merge itself costs xy so the total cost becomes as claimed.

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

    First, we'll find the minimum accumulative cost of a string. In fact, we will prove something more: the accumulative cost of a string doesn't depend on the order they are combined.

    Imagine that between every pair of identical letters, we have a tune. Thus for example, in the example string abababab, each pair of a's have a tune between them, and so as each pair of b's. That's a total of 12 tunes. We claim that the accumulative cost is simply the sum of all tunes.

    To do so, we will remove a tune at the moment that the pair of letters are merged into the same string. For example, when we merge aba and ac, the two pairs of a's (pick either a in aba, and pick the a in ac) will lose their tunes (the pair of a's formed by taking both a's in aba has already lost its tune). It's obvious that each tune is removed exactly once, since at the beginning no letter is in a string with any other letter, and at the end every letter is in the same string. It remains to show that each tune does contribute exactly 1 to the accumulative cost.

    Consider f(s, c) × f(t, c). Look at each occurrence of the character c in s, and another occurrence of the character c in t. They have a tune between them (because they haven't been merged). There are f(s, c) × f(t, c) ways to pick this pair of c's, and so f(s, c) × f(t, c) tunes as well. All these tunes will be lost when they are merged, and it costs the same amount to merge them. Summing over all c proves the claim.


    Now that we have shown that we can compute the minimum accumulation cost of a string from just counting how many times each character appears. If there are n of a character, then they have tunes among them; simply sum over all characters to obtain the accumulation cost.

    Now, constructing a string is easy. Just take n as large as possible while keeping ; now we have n a's. Subtract k by and set that as the new value of k. Take n as large as possible again; we have n b's. Repeat until we're done. For k ≤ 100000, it can be proven that this greedy strategy works (it's impossible to have k > 0 after using all 26 letters).

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

Problem C is shit: simple idea, but difficult implementation. And with TL like this it's not obvious what will/will not pass...

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

    Am I the only one who thinks like "I saw many problem such like this, but I always couldn't come up with idea on this type of problem (simple range query, but also update) so I can't solve this." ?

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

    It's no rocket science to realize that nlg^2n will pass :D

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

      My solution (segment tree of treaps) didn't pass.

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

        I also hate when my sln is rejected for constant issues, but.. Man, nlg^2n is <30M by rule of thumb, and my lazy solution runs in 1.45s. Not to mention that there was several n^1.5lgn AC solutions — it's too much for authors to consider anything which is even slower than n^1.5lgn solution.

        And tbh I'm not surprised to hear that segment tree of treaps don't pass..

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

WTF, it was?

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

Am I the only one who was stuck on div2 A for a very long time?

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

In 2C cannot we do it as {1,3,6,10,15,21...} and find n as a sum of elements of this set?

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

    yes, it turns out that the order of merges don't matter, and we can consider merges of different characters separately and sum at the end so this approach works. The proof of the above claim stems from the identity

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

please help me :( my code got MLE on first test (D div2) but I didnt use much memory on it.

http://codeforces.com/contest/849/submission/29990097

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

Harder round than usual.

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

How to solve Div2(B)? Any ideas?

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

    maintain a map of slopes.

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

    Choose one point as p1.

    For each point p2 in the point set except p1, caculate k1 and b1 for line p1p2(y = k1x + b1), then for each point in the point set, test if the point in the line p1p2(abs(k1x + b1 — y) < eps). We can tolerate at least 1 point(since the line must pass at least one point) not in the line p1p2. If we found two points(p3, p4) not in p1p2, then they can form another line p3p4(y = k2x + b2), if k1 == k2, for the rest points we only need to check if it is in p1p2 or p3p4.

    Since the p1 we choose may be the only one point in a line, we need to try again with another point as p1 to cover this corner case.

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

Is there an easy solution for C? I came up with a that I can't finish coding in 30 minutes (probably 200 lines of code).

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

    Hope my solution doesn't FST...(upd: Passed System Test!)

    For any two points i, j that ai = aj, if there doesn't exist i < k < j that ai = ak, then we create an interval [i, j]. The query just asks the sum of lengths of all intervals that lie in [l, r], and update changes O(1) intervals.

    Let's take an interval [l, r] as a point (l, r) on the 2D plane, and its weight is r - l. A query [l, r] asks about the sum of weights of all points (x, y) that l ≤ x, y ≤ r.

    You can write a DS that supports add/delete 2D points and 2D rectangle sum query. I used Fenwick tree + balanced search tree. The time complexity is and space complexity is .

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

    As long as you know how to code 2d segment trees, it is. Consider the points of coordinates (prev[i], i) with values i — prev[i]. In one query (L, R), you're interested in the sum of the values of the points with L <= x and y <= R. When you modify a value, at most 3 prevs change

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

    90 lines only 29981295

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

Am I the only one who took 20 minutes in C to avoid using map with 2d fenwick tree (and didn't succeed)? I had a solution involving any sort of 2d segment tree and didn't know how to properly code it (I though of offline solution that would normalize stuff), but any implementation has, besides the log^2 complexity and extra log or pretty big constant (maybe if we use instead of map some better hash). So, I wasted time and got nervous, but at least I can learn something out of this experience. Can anybody tell me how to properly code 2d segment trees so that you don't need an extra log or hash to access memory spaces? I do know how to do that with a segment tree with binary search trees (treaps more precisely) in nodes, but that is neither elegant, nor constant-friendly:))any help?

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

    fenwick tree is superfast and it was likely that it would get accepted (and it did :)))) btw, even n sqrt log with fenwick gets accepted here
    so i think there was no reason to get nervous as TL was pretty big

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

Is int32 (int in C++) enough for problem B div 2 ?

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

    Yes, int = 2^32 = 4*10^9

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

      Isn't max_int in C++ 231 (one bit of memory for sign)? The coordinates here can be negative. Either way, it should be good enough.

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

      Sorry for my non-clear question, because I think everyone using pair of fraction. But as I see, people use double instead. So I wonder if using fraction to store, could we get integer overflow for multiple operation.

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

    If you do all operations without double, then long long is safer.

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

Why div 2 B ? ...

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

My first div1 contest and i think i'm going back to div2(((

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

    Don't worry, you are safe:) your new rating is 1916

»
3 months ago, # |
  Vote: I like it +35 Vote: I do not like it
  1. Stare at a problem A for 10 minutes.
  2. Write dp solution.
  3. Check whether I turned up in Div1 by accident.
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't even solve problem a in div2.. How to solve that?

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
                string answer = "No";
                if (N % 2 == 1 && A[0] % 2 == 1 && A[N - 1] % 2 == 1)
                    answer = "Yes";
    

    Idea: 1. the sequence must have odd length 2. the first and last elements must be odd

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

Failed on tests 5 6 7 8 9

Image and video hosting by TinyPic

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

Hacks for Div. 2 A and B?

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

    Div2a
    6
    1 0 1 0 0 1
    Answer is no.

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

    For Div-2 A, even this code (surprisingly) passes Pretests, so ez hack is: n=3 and a=[1,3,4].

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

    In problem A my code passed pretests without handling the n=1 case. (Luckily I noticed before getting hacked)

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

ODDS&ENDS by. supercell ( ryo )

Tell Your World by. 8 Prince

From Y to Y by. OneRoom

Rooter's Song by. DECO*27

Goodbye Souvenir by. Toa

Miku is the best.

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

    shake it! by emon(Tes.), and Hanairo Biyori by Natsume Chiaki

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

Am I the only one who found Div2 C easier than Div2 A and Div2 B??? :|

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

I think div1C can be solved in this way in O(nlogn) but I suck at implementing it — spent 90 mins and got nothing. :(

The answer of each query is equal to the accumulated value of nxt[i]-i for l <= i <= r where nxt[i] is the smallest value which satisfies a[nxt[i]] == a[i]. (Let nxt[i] = n if there is no candidate for the sake of implementation), minus nxt[i]-i the rightmost elements of each values

nxt[i]-i can be maintained with a trivial fenwick tree.

Denote red[i] to be the sum of values to be reduced for queries [l,r] where r == i, this value could also be maintained with any range structure. (Just increment red[i..nxt[i]] by nxt-i)

My buggy code for the brief idea: https://ideone.com/NPDI0p

Edit: Nvm, I think it fails to handle elements which are not contained within the query range

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

    I think it won't work because "minus nxt[i]-i the rightmost elements of each values" don't really match with red[i]. (didn't see the implementation, so I might be wrong)

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

It feels good when System Testing is so fast =P =D

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

Super fast system test! Great!

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

It seems that there are many solutions and complexities in Div.1 C.

Which complexity did you use?

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

I have an impression that when score distribution is like "x-y-1750-1750-z" or "x-y-z-2250-2250" it almost always turns out it would have been better to have standard one. Like this contest or here: http://codeforces.com/contest/830

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

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

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

A moment of silence for those who solved A then jumped to C but couldn't finish debugging it on time :(

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

When ur python code can't perform 1e6 operations in 2s and gives TLE :(

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

    Python should be able to perform around 107 arithmetic operations in 2 seconds. Your solution might be inefficient. (For example, did you know concatenating strings is ? If you concatenated so much, your estimation of the number of operations might be off. It might be something like that.)

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

    You can try submitting in PyPy, it runs a lot faster.

»
3 months ago, # |
  Vote: I like it -91 Vote: I do not like it

I must say, extremely bad problemset. Would require one hell of a disinterested person to write such bad problems.

»
3 months ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

EDIT: The editorial is already up, wow. Well, I'll leave it here anyway.

I didn't come up with a complete solution for Div1D, but this is my idea:

For convenience, suppose a change involves the edge (u, v), and vertex w and edges (u, w), (w, v) are added. Then we say w is built on top of (u, v). We also say (u, w), (w, v) are children of (u, v). We say (x, y) is a descendant of (u, v) if (x, y) is a child of a child of ... of a child of (u, v) (with any positive number of levels). Let cut(u, v) be the minimum (u, v)-cut in the subgraph made of (u, v) and its descendants, minus 1 (the edge (u, v) itself). This minus one make things much cleaner.

First, suppose u1, u2, u3, ..., up are all the vertices built on top of (s, t). Then ; this can easily be proven by induction (and the base case itself is easy to see: either you cut from s to u1, or cut u1 to t).

Given this, we can use dynamic programming to solve it. An attempt is to set dp[n][m] to be the number of possible worlds where there are n changes and cut(s, t) = m. (Since we don't count (s, t) itself in cut(s, t), given input n, m our answer is dp[n][m - 1].) If we could somehow take care of the similarity condition, this would work:

  • Fix p (the number of vertices built on top of (s, t)).
  • Fix n'1, n'2, ..., n'p, n"1, n"2, ..., n"p: n'i denotes the number of changes made on top of (s, ui) or a descendant of it, and n"i denotes the number of changes made on top of (ui, t) or a descendant of it. The condition is that (n'i + n"i) = n - p (we already made p changes, u1, u2, ..., up).
  • Fix m'1, m'2, ..., m'p, m"1, m"2, ..., m"p: m'i = cut(s, ui), and m"i = cut(ui, t). The condition is that min {m'i, m"i} = m - p.
  • The base case is dp[0][0] = 1 (no change needed), dp[n][0] = 0 for n ≥ 1 (we may not make any cut, but we must make some change), and dp[0][m] = 0 for m ≥ 1 (we cannot make any change, but we must add a cut).
  • Compute (dp[n'i][m'i] × dp[n"i][m"i]).
  • Iterate over all possible values of them and sum it all. (Take modulo 109 + 7.)

The similarity condition makes things hard, however, since we need to take care not to count the same thing twice. As an example, suppose n'1 = n'2, n"1 = n"2, m'1 = m'2, m"1 = m"2, and yet the subgraph built on top of (s, u1) or its descendant, say H, and the subgraph built on top of (s, u2) or its descendant, say H', are different. Then we will get another valid graph by swapping H and H'. This gives the same graph, but our naive DP algorithm will count them as different. So we need to take care of that.

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

My solutions for the problem is perfectly okay but they were rejected during the contest for no reason.
Look at the two solutions below 2991746, 29991714 the only different is at line 153.
Everything is exactly the same. Even the output is same.
Can anybody explain?

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

    It seems that p(x) prints an extra trailing space.

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

      29991794

      This is a solution, with extra space that gets passed.

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

        Perhaps in practice the checker is not so strict.

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

        It seemed to me that p() prints \n only. As your wrong answer states, the verdict is wrong answer Line "o " doesn't correspond to pattern "[a-z]{1,100000}" You may observe that there is an space after o... So I went to look at the code when n = 0, and turn out that p("o") is different from cout << "o"); p();

        TL;DR: A single space hurts :(

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

          p("o") prints a new line too.

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

            I print extra new lines all the time. This has never happened.

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

            Output for p("o"); is o \n; and

            output for cout << "o"; p(); is o\n.

            So the only different is really the space. I think the checker this time is strict tho, as normally the checker would trim your output first...

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

    The difference is that you are printing an extra SPACE in the second code. But I agree that this shouldn't be a reason to get WA if the rest of the code is correct.

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

Nice problems!

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

my mind was blowing in 2nd question.. :(

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

super contest !!!

»
3 months ago, # |
Rev. 3   Vote: I like it +26 Vote: I do not like it

I got AC on Div. 1 D after contest (I couldn't get it to pass during contest because I wasted time on Div. 1 C). Here's my solution :

Let dp[i][j][k] denote the number of distinct graphs that can be formed after applying the operation i times so that the max flow is j, and k is something we will describe later. We iterate through x, the number of times we use the edge s-e to construct a new vertex where k flow will flow through it. Iterate through y, the total number of operations spent on this part of the graph (the current edges and all the edges that will occur after it). We need to find the number of ways to use y operations to create x pairs of graphs of the same type such that for each pair of graphs (A, B), the minimum of max flow of A and the max flow of B is exactly k. Suppose we know the answer to this is X. Then, we can increment dp[i - x - y][j - kx][min(j - kx, k - 1)]·X to dp[i][j][k].

Let dp2[i][j] denote the number of ordered pairs of graphs (A, B) we can form such that the minimum of max flow of A and the max flow of B is exactly j and a total of i operations are used. Then, we can iterate through all k, denoting that we use k operations to form A, and all pairs (l, m) with min(l, m) = j and add dp[k][l][ldp[i - k][m][m] to dp2[i][j].

Finally, let dp3[i][j][k][mx] denote the number of multisets of ordered pairs of graphs (A, B) we can form such that the minimum of max flow of A and the max flow of B is exactly j and a total of i operations are used, assuming that we can only use at most mx operations for each pair of graphs. Iterate through l, the number of pairs where we use exactly mx operations. Let C = dp2[mx][j]. There are C ways to choose one pair, and we need to choose l pairs, possibly with repetitions. The number of ways to do this is by the balls in urns formula, and this value can be computed in O(n) time since l ≤ n. Thus, we add to dp3[i][j][k][mx]. We can use the value of dp3 to find the X we need for dp above.

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

I know Div1C N * sqrt(N) solution but I did not have time to finish writing it :( Offensively

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

I solved only one problem on a round for Miku.

I'm feeling terrible.

Just take my score. :(

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

WTF!!

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

    It's like game of thrones. The more you have, the easier you can lose it!

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

All my solutions were "skipped" and I was not given a contest rank.I did not plagiarize any code from anyone ....

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

    maybe you used some public online IDE like ideone and someone copied and submitted that code before you did!

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

      Ya i just realised that. I hadn't privated my code on ideone. Pretty damn unfortunate .....

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

      Bad luck. Solution for A and C was correct. If these two got rated then.... Alas! they got skipped.

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

        I think my B was rit too cause i got AC in the system test round and then it later got converted to Skipped. But i guess ders no use crying over spilt milk....

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

Bad luck. Solution for A and C was correct. If these two got rated then.... Alas! they got skipped.

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

    I'd like to have my solutions skipped... =)

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

Nice problems!

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

can someone tell,why WA it's working for the same input on ideone — http://codeforces.com/contest/849/submission/29996525

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

    You are setting the flag to false when the endpoints are odd, you need to set the flag to false when they are even.

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

      Run the same code in custom invocation, you'll get "yes" instead of "No"

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

thank you ♂sir

»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

昨晚有点崩,本人hack了,以后一定要稳定心态,加油!

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

    Good luck next time!

    Also, on CF people write English so that everyone will understand. You can translate it.

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

Dongda District so many people want to play codeforces, but only the middle of the night to play, hoping to like that last night that time, or later can, or every time the second day of class are listless.

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

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