Блог пользователя ed1d1a8d

Автор ed1d1a8d, история, 9 лет назад, По-английски

Greetings! CodeForces Round #336 welcomes both divisions this Wednesday, December 23, 2015 at 16:35:00 UTC. The round is authored by me, Amor727, Chilli, and GlebsHP. We hope you'll like the problems. Scoring and score distribution: Not Dynamic; Div1: 500 — 1250 — 1500 — 2000 — 3000; Div2: 500 — 1000 — 1500 — 2250 — 2500

Much thanks to Amor727 and Chilli for writing and editing problems, GlebsHP for organizing the competition and for his very helpful attitude, Delinur for translations, winger for testing, Marina Kruglikova for statement fixes, and MikeMirzayanov for his amazing CF and Polygon platforms.

During this contest you will be assisting Genos from the series One Punch Man. His master Saitama will also make some appearances. We wish everyone good luck and high rating in assisting the two. From the contest crew and the two fellows below, happy holidays!

Congratulations to the winners:

Division 1:

  1. matthew99

  2. tourist

  3. ACRush

  4. jqdai0815

Division 2:

  1. Hansuzu

  2. ajjack999888

  3. platypus179

  4. Petru

  5. Mihaell

Editorial of round: /blog/entry/22256

  • Проголосовать: нравится
  • +427
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

I love ONEPUNCHMAN, I was waiting for this for ages!!!! GL && HF!

P.S Hoping for some funny jokes.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -28 Проголосовать: не нравится

hardest contest, hardest life.

»
9 лет назад, # |
  Проголосовать: нравится +86 Проголосовать: не нравится

Div 1 contest being prepared by a Specialist? I can imagine contest setting going like this:

-GlebsHP: Seriously? A Div 1 contest being prepared by two purples and a specialist? Who do you think you are?
-ed1d1a8d, Amor727 & Chilli:

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

like One Punch Man very much!!!

»
9 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Hi again guys!

Thanks for support :D

GL & HF!

P.S. When I firstly have seen this blog I thought that it was Xephy's :)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

Saitama is like a reference to tourist xD. Onecodeman ;DDD

»
9 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Code until you go bald :P

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Hope to celebrate the Christmas by becoming specialist :)

»
9 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Accepted from one submit. (c) One Submit Man

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

To train for this contest, every day for a year I did 100 pushups 100 situps and 10km running

»
9 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

OneCodingMan

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +102 Проголосовать: не нравится

tourist vs jqdai0815
that would be interesting.

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

who looks like ONE PUNCH MAN in codeforces ??

»
9 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

this contest will be amazing ☺ !

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

It would be interesting if tourist jqdai0815 rng_58 and Petr all participate in this contest ;)

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

So addictive site ^_^

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

One Punch Man...!! Who'd be the "One Code Man" of this contest.....??

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

GL & HF !

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

The problem will be like determine the minimum strength of the monsters that can beat Saitama :D

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    in the last line, this description make the answer obvious : print -1 if it doesnt exist.

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

My first round on codeforces . I hope that I will will enjoy :)

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

tourist and jqdai0815 are online, looks like they will participate . Guys get ready for the ULTIMATE CLASH OF 2015 .

»
9 лет назад, # |
Rev. 6   Проголосовать: нравится +7 Проголосовать: не нравится

deleted (i had a mistake about times)

»
9 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -76 Проголосовать: не нравится

ANIME is the WORST ONE I HAVE SEEN

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I dont think so

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    All of my friends who watch anime said it is at least best of the season one. On myanimelist it is placed #10 in top. So I guess you have watched only #1-9 before that one? :-P

»
9 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Nice, I've just watched first two episodes of this anime today. Guess I'm ready for this round now :D

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

Standard ? really ? 500 — 1250 — 1500 — 2000 — 3000 is standard now ?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Am I the only one here who doesn't watch this show?

»
9 лет назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

i think we will hope for the many math problems!

»
9 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

On an unrelated note, what do you guys think is more important? Learning more and more concepts or mastering what you know?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well i don't have much experience but i think whenever we learn a new concept we should try to solve a few problems related to it to make it clear to us . This way, we do both the things simultaneously upto a level .

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

 Dota 2 version!(Not everyone will understand...)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +28 Проголосовать: не нравится

In all rooms...

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +21 Проголосовать: не нравится

Что-то пошло не так

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

 Seems to be a bug in codeforces

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually I don't think it's a bug. Maybe it's a new feature to see all the other participants with hacks. I think it's actually pretty useful.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      The thing is that these people made successful challenge without submitting a problem :) I think it's a bug in standings, though.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone else keep getting a runtime error for Div2C/Div1A?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve B? Is the solution is keeping remove the largest palindrome subsequence until the string become empty?

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

B seemed much harder than C...

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yeah. Worst case complexity is 10^10 (a=10^5,b=2*10^5). How did people do it in time ?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Seems obvious that solution with such complexity won't work :)

      I suspect that correct one would be like O(len(b)), however I didn't find the correct one.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Look at each character in A and count how many opposite characters in B it will have to pass as you shift A across B.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      because you shouldn't solve it 10^10

      The correct solution is like that:

      Take a note, that you asked about the sum of "differences", not to count all differences. This leads to following approach. Fix some position in second string, and the first string will be shifting relatively to second one. Actually the positions, which are opposites to our fixed position, are making a subsegment in first string. And you just need to count how much exist chars different to fixed one in this subsegment.

      When you step from currently fixed position to next one, the subsegment is moving to the right. So just maintain the count of chars of each type in current segment and advance it carefully.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Even better. Make a segment tree to count 1 and 0, and call for each index in a.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        "Fix some position in second string, and the first string will be shifting relatively to second one."
        How the first string is shifting relatively to the second string if the position in the second string is fixed?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          I mean imagine the process of taking differences of A and substrings in B as imposing A to some place in B. You can shift such a place and the imposing part is shifting too, consider all shifts, which overlay fixed position.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The same for me.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Если D решается динамикой по подотрезкам, то у меня походу бомбанёт, что мне не хватило минут 5 отдебажить код =\ P. S. Ещё из-за плохого копипаста не прошла C :(

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    именно так она и решается)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да сам виноват, поздно понял, что эта задача очень похожа на ту, которую решал буквально 2 месяца назад :( Больше всего раздражает, что у меня выходило где-то 7-8 разных случаев, и в каждом нужно убедиться, что не ошибся где-то на единицу.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -18 Проголосовать: не нравится

How to solve Div2D? I think it is dp[from][to] but I kept getting WA #14 :)

PS: I realized where my mistake was :)

»
9 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Well, no need to wait for systests, it's back to Div 2 for me.

I'll try to boost my self-esteem with a virtual contest...

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Lagged at the last 10 sec and couldn't submit B. I think the solution is correct. I hate when something like this happens :/

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

when will the system test start?

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I solved B Div2 with prefix sums

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Your code looks sharp and understandable to me.
    Could you, please, explain how did you come up with the solution?
    Do you have some napkin drawings left? :)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

Can someone help me figure out where my code fails for 2C? https://code.hackerearth.com/a0bb04m?key=71b2fc5852347cfd361c5a3802736190

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I solved problem C(div2) by binary search? How do you think will it pass?

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Could someone tell me what's wrong with my code for div2 C? http://mirror.codeforces.com/contest/608/submission/14957339

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks every one...

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

 I wanna be the best hero!

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

tourist come back............? tourist.........3374 TooSimple...... 3112

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Rating changes please.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

thanks for completed quickly system testing and also will be so happY if rating update quickly.

»
9 лет назад, # |
  Проголосовать: нравится +254 Проголосовать: не нравится
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +84 Проголосовать: не нравится

    -_-.....

    How poor testing must have been so that such solution passes :|??

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +41 Проголосовать: не нравится

    LOL. The test setter probably thought that div 1 guys know complexities well and would not attempt to write such a solution :)

    Even funnier is that these ineffective solutions have the best running time :D Don't waste your time preprocessing, mr. coder.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    The slowest it gets is 171 ms with a TL of 3.5s. That's messed up.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    I was in charge of tests for this problem and made the mistake of generating queries randomly, which gives them on average a very low complexity. We failed to catch this during our internal testing due to the fact that our sample brute force had O(N) updates and O(1) queries (instead of the O(1), O(N) like here). My deepest apologies, I'll definitely be more careful in the future.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится -31 Проголосовать: не нравится

    Blue -> purple -> yellow :) Just in 3 contests

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone tell me how to solve div2 C?I think it is at least not bad to boom ith beacon if activate it will destroy k beacons(k>1),so I do it by something like Prefix sum ,but keep WAing on test#11 QAQ.Is my thought totally wrong for this problem?

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Don't get your solution, but my AC was like that:

    For each beacon from 0 to n calc how much beacons would be destroyed if i-th beacon is starting one, using dynamic programming (we have calced all lower ones before i-th, so could be reused) and binary search (to find how many beacons destroyed by i-th). Complexity here is O(n * logN).

    After that try to disable from 1 to n beacons and calc best sum using data from the previous step. Complexity here is O(n).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    my AC was : http://ideone.com/z8dqVj ( No Binary Search )
    consider this dp state ,
    dp[present_pos] = total_beacons_affected_by_present_beacon + dp[previous_unaffected_beacon]
    here, previous unaffected beacon means the beacon which is unaffected by the present beacon
    After that try to disable beacons from present pos to n and calc best using the previous data
    i.e., min of total_beacons-total_beacons_until_this_beacon+dp[present_beacon] all positions .

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

matthew99 first. LOL:))

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Hi everyone, this is my first contest on codeforces. Someone could tell me when the editorial will be posted? And when the ranks are updated?

»
9 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Rating is a precalculated result.But why every time it should be given so late. Above 2 hours..but it should not be updated.

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

And after every contest there is a dilemma: go to sleep or wait until raitings are updated...

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Ratings updated.

»
9 лет назад, # |
  Проголосовать: нравится +72 Проголосовать: не нравится

Why DemiGuo's rating did not change being in TOP 5?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    It seems that her submits are skipped... so strange! it's impossible! She was 1st for a while in contest! MikeMirzayanov , what's going on?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +151 Проголосовать: не нравится

    I'll be happy to read explanations about the submissions:

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится -26 Проголосовать: не нравится

      I'd wager coincidence! The programs are small, and it seems highly unlikely for someone in Demi's position to consider cheating. Sadly I also can't offer much towards improving cheat detection.

      Edit: a friend of mine thinks the similarity is "clearly not a coincidence". Sigh... how does one reason about the probabilities involved here? Could be a scientific research question. Perhaps the users involved will make a statement, unclear what good that would do. I thought it better to give the benefit of the doubt, but hey at least we're not banning users.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +35 Проголосовать: не нравится

        Have you taken a closer look?

        These parts:

        	p = 0;
        	for (int i = 2; i <= n; i++) {
        		for (; p && A[p + 1] != A[i]; p = Next[p]);
        		if (A[p + 1] == A[i])
        			p += 1;
        		Next[i] = p;
        	}
        	p = 0;
        	for (int i = 1; i <= n; i++) {
        		for (; p && A[p + 1] != B[i]; p = Next[p]);
        		if (A[p + 1] == B[i])
        			p += 1;
        	}
        	if (p)
        		printf("NO\n");
        	else
        		printf("YES\n");
        

        differ only by replacing a with A, b with B and nxt with Next. This is NOT a coincidence.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

          Also, they both have unused variables named now1 and now2. As much as I want to believe this is a coincidence, this is really hard to explain away.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 9   Проголосовать: нравится 0 Проголосовать: не нравится

          It's possible you're right; it just seems weird from a psychology angle. Keep in mind there are a lot of pairwise comparisons to be made on Codeforces, so unlikely events can happen. A lot of the similarities are very natural simplifying choices to make (i.e. low entropy). We should check for stylistic consistency with her other submissions; that might "explain away" some of the coincidences.

          I'm just having trouble imagining someone with legit skills wanting to do this (especially when you're female so the whole world is watching you as sort of an example); even if it were, the code could have been disguised a lot better.

          Edit: I didn't notice that now1 and now2 are unused :/ Damn whyyyyy

          If we assume that cheating did take place, what happens next? It looks like you can get away with cheating if you have the skills and take effort to obfuscate the source. Will Demi and others just get better at it? Do many orange/red members already do it??? Deterrence is hard if people with actual skills cheat.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        AC submissions are not only ones should be looking at.

        Consider submissions:

        They both WA9 and use such algorithm simulate first string, simulate second string, simulate first string again (the first submission contains original reference to now1 and now2). The second submission simulates second, first, second (probably because the first got WA9).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      i didn't want to say this just because i didn't want to attract attention but you guys made me say it ;D, from what i see from the coding style of both accounts the owner is the same person!

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why do I have TL with O(n*log n) solution on div2c? http://mirror.codeforces.com/contest/608/submission/14955285

»
9 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Div1C was a very elegant problem, I really liked it.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div1C http://mirror.codeforces.com/contest/608/submission/14965956 Who tell me what is the wrong? I try to get the 30th data,the last 10 letters of the first string and the second,using this method if(n==999999&&a[0]=='W'&&a[1]=='N'&&a[2]=='W'&&a[3]=='W'){ puts(a+n-10); puts(b+n-10); } but I failed,because I find the 20th data is same with the 30th I also have try to run other's program to compare with mine using random data,but never find the difference. Who can help me ?

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Saitama Sensei!