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

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

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. EvenImage

Division 2:

  1. Hansuzu

  2. ajjack999888

  3. platypus179

  4. Petru

  5. Mihaell

Editorial of round: /blog/entry/22256

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

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

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

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

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

P.S Hoping for some funny jokes.

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

hardest contest, hardest life.

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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:

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

like One Punch Man very much!!!

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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 :)

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

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

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

Code until you go bald :P

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

Hope to celebrate the Christmas by becoming specialist :)

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

Accepted from one submit. (c) One Submit Man

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

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

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

OneCodingMan

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

tourist vs EvenImage
that would be interesting.

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

who looks like ONE PUNCH MAN in codeforces ??

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

this contest will be amazing ☺ !

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

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

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

So addictive site ^_^

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

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

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

GL & HF !

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

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

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

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

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

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

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

deleted (i had a mistake about times)

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

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

ANIME is the WORST ONE I HAVE SEEN

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

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

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

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

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

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

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

i think we will hope for the many math problems!

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

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

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

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

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

In all rooms...

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

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

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

 Seems to be a bug in codeforces

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

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

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

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

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

B seemed much harder than C...

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

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

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

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

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

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

»
11 лет назад, скрыть # |
← 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 :)

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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...

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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 :/

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

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

when will the system test start?

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

I solved B Div2 with prefix sums

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

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

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

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

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

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

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

Thanks every one...

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

 I wanna be the best hero!

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

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

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

Rating changes please.

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

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

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +254 Проголосовать: не нравится
»
11 лет назад, скрыть # |
← 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?

  • »
    »
    11 лет назад, скрыть # ^ |
    ← 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).

  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 .

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

matthew99 first. LOL:))

»
11 лет назад, скрыть # |
 
Проголосовать: нравится -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?

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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.

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

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

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

Ratings updated.

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

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

  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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?

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

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

    • »
      »
      »
      11 лет назад, скрыть # ^ |
      ← 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.

      • »
        »
        »
        »
        11 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          11 лет назад, скрыть # ^ |
          ← 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.

        • »
          »
          »
          »
          »
          11 лет назад, скрыть # ^ |
          ← 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.

      • »
        »
        »
        »
        11 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +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).

    • »
      »
      »
      11 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +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!

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

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

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

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

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

Div1C http://codeforces.me/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 ?

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

Saitama Sensei!