PrinceOfPersia's blog

Codeforces Round #299
By PrinceOfPersia, 10 years ago, In English

Hi.

Codeforces round #299 is gonna take place soon(exact time) and I'm the writer. I'm lucky to be the first Iranian author in Codeforces, in your and our new year (2015 and 1394).

Now, I wanna thank: myself(PrinceOfPersia) for writing the problems(:P), MikeMirzayanov for great Codeforces and Polygon platform, Zlobober and Damon and sobhan.miryoosefi for helping me prepare this round, Haghani and SoroushE for testing this round, Delinur for translating problem statements into Russian and big thanks to my great buddy, HosseinYousefi for problem legends and the pictures.

Also, I wanna thank MinakoKojima for teaching me how to use polygon and testlib and so much other things about it (about a year ago).

This is my first official contest(after all those contests in Gym :D). I hope you enjoy it.

The main character of all problems is Tavas, well-known by eating CoffeeMix without water! Trust me, when he does that it smells awful.

Also, you'll meet his friends.

I hope you enjoy the problems. I wish you all high ratings, many Accepted solutions and Successful hacking attempts. And Hacked instead of Failed System Test.

Scoring will be posted later.

GL & HF ;)

UPD: Scoring will be standard for both divisions (500-1000-1500-2000-2500).

UPD2: Contest is over. We're waiting for system testing. Editorial is published.

UPD3: System test is done. Congratulations to all winners.

Div.1 winners:

  1. jcvb
  2. rng_58
  3. vepifanov
  4. mmaxio
  5. flydutchman

And Div.2 winners are:

  1. l1n4r
  2. 0e352a
  3. vintage_Vlad_Makeev
  4. wilcot
  5. boray

Good job everyone, see you ;)

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

Comments Comments (184)
| Write comment?
»
10 years ago, # |
← Rev. 4   Vote: I like it +22 Vote: I do not like it

looking forward to this contest thanks :) congrats for being the first Iranian author in CF in our new year wish u and everybody else luck :)

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

    tavas has eaten the ratings instead of karafs??

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

Congratulations with your first official contest:) Looking at your contests at gym — now I am expecting interesting tasks, and I'll try to attend this round.

P.S. And I guess you'll also become a leader of contribution rankings soon, congratulations in advance:)

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

    wow, he made it! congratulations :))

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

    There will be another boost up after the editorials are out assuming he writes them.

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

Congratulations Man !! Hoping to see problems like the ones in gym :D.

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

I like contests with graphics :D I think it would be amazing one isA

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

Congratulations with your first official contest :)

I hope to see Problems a bit easier than yours in GYM :P and please do not use dynamic Scoring system :D

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

And also you should wish us Hacked before locking code ;)

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

Long time no see ... It is great to see you progress during this year ~ I am looking forward to your problems tomorrow night ~

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

This is my first contest as a Div.1 participant. Hope my rating will not decrease)) Thanks for Div.1+Div.2 contest!

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

Round #282 was my last Iranian author CodeForces round I have participated in and the problems was interesting.. I hope this one to be better :) Good Luck.

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

Hoping for rating increase.

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

Congratulations,I hope the problems will be easy enough for me to be able to increase my rating a little bit :P vali dadash farsi ham tarjome mikardi soalaro Awwwli mishod :)

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

Good luck to everyone !!! Hope that I'll participate in Div 1 Round next contest :)

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

You said you were going to write a contest and thank yourself and you did. haha thats awesome (y) http://codeforces.me/blog/entry/16996#comment-217994

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

Is Tavas your character ?

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

Firstly, when I see green color in this blog, I decided that it is some green coder, who made part of problems for the contest:D

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

    Do you think green coder can't "make part of problems for the contest"?

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

Loved that "Hacked instead of Failed System Test"!

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

be careful with tricky cases xd, ...Does somebody know why our contest time has changed in one hour later?

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

    It happened the same to me. I think it's just because the different Daylight Saving Time in Russia as in other places.

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

Congrats! :D

You're now first in top contributors list.

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

our new year also. it's 1st day of 1422 here in Bangladesh today!!

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

If you carefully read mails about rounds, you can find "The round writer is Codeforces problem coordinator PrinceOfPersia".

It is just copy-paste mistake. Zlobober, sorry me. You are not fired :)

I'm sad that there are no pretests for mails and I can't fix mail and resubmit it again.

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

    Yeah, I noticed. (I almost never read the e-mails, it's quite strange that I now did and noticed it.)

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

    I never read the mail, but when I saw you said that I read :D
    I think if you hadn't mention that a lot of users wouldn't see :D

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

I'll be on a flight from the U.S. west coast to the east coast during this round...

Sounds like time for Codeforces at 39,000 feet (if the flight I'm on has wifi) :)

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

    MISSION ACCOMPLISHED

    ...though my score doesn't really tell the same success story... :P

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

My Second Contest as a Candidate Master... This time I'll never go down to Expert

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

Congrats to my country — Iran — for having Top contributor(PrinceOfPersia) and Bottom contributor(Fear_Is_An_Illusion)!

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

PrinceOfPersia has registered for this contest !!!?

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

"Hacked instead of Failed System Test".. -> An awesome contest on the cards.. Also just 1 more to go now for 300 contests.. Thank you CF.. :)

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

I hope I will increase ratings in this contest !

And

I hope I will increase contributions in this comment !

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

I would participate in this contest and then watch the Real Madrid match. but Just Chelsea :D

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

    It is a perfect time for programmers who are also real madrid fans!

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

      Yeah it is a perfect time for watching Real Madrid's defeat...

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

If I predict your doing give me +1 else give me -1
"You will give me -1"
It is a paradox. Isn't it ???

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

    I wasn't going to rate your comment, so your prediction failed, so I gave you -1.

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

      It is paradox because : 1 you don't rate my comment — 2 you give me -1 how can you do that ???

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

        We're programmers. If statements are only executed once.

        action = "none"
prediction = "-1"
if action == prediction:
  vote(+1)
else:
  vote(-1)

        I'm sure we all know what this does :)

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

          so :
          if( "none" != -1 ){
          cout << "YOU DO 2 THINGS none && -1 how ?????";
          }

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

          Yes very nice, except lets refrain from using Python :D. 

          #include <bits/stdc++.h>
// I love bits/stdc++.h
#define int long long
// I love define int long long
using namespace std;main() // I love messy code
{while (true){int vote=0;int prediction;cin >> prediction;if(prediction==1)vote++;else vote--;}}
          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          vote == action .
          it is necessary

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

Early score distribution, lol. Nice!!!

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

Why most of the contests recently are being delayed?!

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

Wow ! Top contributor ! :D niiice ! :D Congratulations :D

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

This feeling when you found a mistake in your pretest AC-code, recode it, submit it again, and then realize that it wasn't mistake. Oh no( I was 125 and now I'm 825(

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

    Imagine locking your solution DIV 2 A and hacking others with testcase 0 and later realizing even you missed that testcase..

    Made two big blunders in this contest. Really need to learn to keep my cool during contest.

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

How to solve C?

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

    Isn't it just a fenwick tree? My solution got WA on pretest 3 but I think that the idea is correct. I sort them in increasing order of S and then of R. Then I loop from n to 1 and find the answer. Counter-examples?

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

    Convex hull.

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

Solution for problem C Div.2 ?

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

Lock Problem -> thinks about a test case that your code doesn't consider :(

For Div2 A, what about leading zeros?? please don't judge me on those :(

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

Thanks for the round, though there was a huge gap between B and C ( Div2 ). 2233 people solved B but only 196 ( of them ) got C !

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

about C task:

2
2 4
3 4

my solution: convex hull with two extra points: ( - 105, max(y) + 1) and (max(x) + 1,  - 105)

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

If you're thinking you're having a bad day.. I'm going to fail in B because I wrote this to calculate power

for(int i=1;i<n;i++)
  power[i] = (power[i - 1] * 26LL) % mod;
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    And what's wrong with it?

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

      i < n and n is the string length in the input :(

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

        Ah, got it, It will fail, when m=0

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

          This is just precalculation and then I output power[cnt] where cnt is the number of ? characters.

          and seriously I don't know why I did this

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

    I did more stupid mistake in B: I wrote
    int count = m == 0 ? 0 : (y[0] - 1);
    instead of
    int count = m == 0 ? n : (y[0] - 1); :( :( :(

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

First time i've solved E:), I just could not make myself stop to submit E after 1 hour and 40 minutes.

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

Contest is now ended. I hope you enjoyed problem legends and little graphics for each problem :)

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

My Problem A got hacked,before locking and failed system test!!

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

I hacked MamZi's B in the last 10 seconds and achieved a positive score :D

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

systest has stoppped :/

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

Irrespective of the system testing results , this was by far my favouraite Contest among the recent codeforces contests . Hats off to problem setter .

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

Any tricky case for Div1 B. Many people seem to have failed case 8 in pretests.

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

    forgetting to use MOD 1000000007, i think

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

    Found my error . By mistake used the wrong library method for modular expo.

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

It was pretty fun to hack div.2 A, I made fife successful hacks. And it was more safe not to write any numbers by hand — just copy-paste from wikipedia.

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

    Copy-paste what from wiki?

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

      Copy-paste written numbers from the given link, and then somehow use them in the program code (10707394).

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

        Oh, sorry. I didn't understand that you were speaking about Div2 A

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

Salam iran zamin ? ! How old are you ?! O_O !?

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

Hello)) There is a question about task C (2 div): Tavas and Karafs. Why in this answer on first test 2 1 4 1 5 3 = 4 ? 3 3 10 7 10 2 6 4 8

In this the sequence : 2 3 4 5 6 7 8... and I must have t = 7 that take 2 and 5. Or something not that?

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

My only mistake in C: I used doubles instead of integers. Even with an error margin, not exact comparisons, it still gave WA. When I replaced them by integers, AC. Stupid doubles.

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

    You are dealing with cross products with points distant from each other of 1e-8 and you expect it to work ( ͡° ͜ʖ ͡°)? Moreover you possibly wanted to check if some point lies on some line and do it with some allowed precision error ( ͡° ͜ʖ ͡°)?

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

      I thought it was 1e-4. (Not like the error caused by taking the difference of two close numbers couldn't be too small anyway, but this is the first time double comparisons have failed me so miserably.) Stupid doubles.

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

What's the idea of problem E-Div2/C-Div1 ?

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

Hey,

The limits for DIV2 B are (1 ≤ n ≤ 10^9). While if you look at this http://codeforces.me/contest/535/submission/10713882, the code fails on an input which is out of bound. WHY ?

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

I think there are weak tests in Div 1 A. At the end of the contest I found long overflow in my solution (I used binary search and the sum of arithmetic progression could be too large). I quickly added additional check and got AC but lost about 150 pts. However, my first solution passed all tests too...

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

    Maybe because when R is too large, then you fail 

    boolean canByLargest = last <= t;

    and can ignore overflow

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

    Overflow? Where?

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

Can somebody explain in detail how to solve DIV-2 C as I am unable to understand the editorial.There's a lemma.Is that a standard lemma. if Yes can anyone give me the link to that lemma .If no can someone prove that it will be the optimal way to arrive at maximum r because I am unable to think how to approach solution if say t is such that more than m is the answer.

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

    just a binary search for the required answer

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

loved the contest :) and the descriptions of the problems :)

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

Wrong answer at 51 for problem A div-1. with message-
wrong output format Expected integer, but "1e+006" found , actual answer is 1000000

why are you matching answers as strings? match values!!
10714667

and got runtime error in problem B because of writing "n" instead of "s.length()"
BAD DAY.

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

I got a Runtime Error on test 55 on problem B (div 1), a case where m=0 and my code crashed trying to read a line that didn't exist.

Looking at the input specification again, shouldn't you be able to expect an empty line in that case?

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

    Same here... Problem statement indeed states that The next line contains m space separated integers... , but there were no next line at all. Re-test wanted!

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

      Yeah I think that would be fair. Looked through some submissions and saw that at least 8 failed because of that reason.

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

        I'm not very familiar with Codeforces rules and regulations. What can we do in this situation? Do we need just send private message to MikeMirzayanov ?

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

        I'm one of them. Run my code against empty line test, lost 200 positions and my red color because of that :/

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

I am impressed by the number of people who wrote out all 100 answers to div2 A and the 1022 answers to div2 B

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

LOL. I understood C as "for which pair (xi, yi) do there exist A, B > 0 that Axi + Byi is not less than other Ax + By" instead of A / x + B / y :D passed more than 40 tests

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

    You didn't take the case in which you have more people of the same type.I think you could take AC :))

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

      I changed that couple of minutes ago and I get WA on #43. Testcase is:

      3
2 6
3 3
6 2
      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    loool , i made the same mistake , modify it to division and you get Accepted

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

writing twelwe instead of twelve and getting WA in problem a.div2. is it a dictation test or a contest?

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

I had a hard time trying to understand prob statement of C div 2. Maybe I need to sleep more, lol!

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

I didn't solve any problem... Guys! let's make it unrated! what u think?

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

very good contest!!

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

First time failed all problems in CF contest :( feels so terrible :(

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

    Me too :( Solved only B but failed even it because of wrong array size.

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

    Only 10 minutes before the end of the round, I was very close to ending up the same as you. At least I knew how it'd end.

    (For the record, I've had that experience.)

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

    Anw, now that I have time to carefully think about my failure yesterday, I think I learnt something:

    • How I spent my contest time: Trying A for ~ 10 mins, gave up. Quickly solved B in ~ 10 mins, go back to A. Tried A for almost an hour. Gave up after coding lots of (wrong) code. Quickly solved C in ~ 10 mins. Go back to A & tried it for the rest of contest.
    • So the lesson is, no matter how many participants solved a problem, should probably give up if you already spent too much time and still cannot proceed.
    • Should carefully test / read through code again, even if you're in hurry to do something else (I was so frustrated with A that I did not spend any time double checking both my B and C. So B failed because of negative mod, C failed because of precision (used 1e-7 intead of 1e-9) plus a corner case that I thought I handled)
    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anybody help me please?,

I can't see my mistake, i'm getting TLE in pretest 37 my algorithm is O(n) z algorithm

this is my code code

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

    You have a mistake in your z_function implementation. On the first iteration (which is unnecessary, as z[0] is undefined) the string will be compared to itself, z[0] — set to n, and r — set to n — 1. Then you have (r < i) in your if statement (instead of i < r), which will never be true. So, for each i you will iterate through the whole suffix (well, in case of a string like aaa...a), and it basically works in O(n^n).

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

      that was because of my incomplete template, anyway thanks!

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

Using picture is good and positive point

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

    Where are the ratings,man?

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

    i found saddas , best friend (not girlfriend)of tavas who love karafs a lot

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

Can somebody explain me DIV 2 C for this test Case 1

2 1 1

1 5 3

Why is the answer 4 and not 3 A=2 and B=1 so Sequence 2 + (i-1)*1 == i+1 so for l=1 we have Seqence =2,3 ,4 ,5,6

now we have 5 tries original — 2 3 4 5 6 1st try 1 2 3 5 6 2nd try 0 1 2 4 6 3rd try 0 0 1 3 6 4th try 0 0 0 2 5 5th try 0 0 0 1 4

so we get S[3]=0; so answer =3 and not 4 Can somebody exmplan me wher i am wrong

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

    2 3 4 5
    2 2 3 4
    2 1 2 3
    2 0 1 2
    1 0 0 1
    0 0 0 0

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    0: 2 3 4 5 6
1: 2 2 3 4 6
2: 1 2 2 3 6
3: 1 1 1 2 6
4: 0 0 1 1 6
5: 0 0 0 0 6
    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      does we have a constraint on distinct reduction of Distinct Karafses, You are reducing 1 1 to 0 0, which are Same not Distinct?? please correct me if am wrong

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

        distinct indexes, not distinct height

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

          okay so if u have distinct height selection do u have ideas how can we achieve the same

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

congrast to all new candidate masters!

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

Very nice problem! I love it! Thanks for problem.

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

Antihash in 67th test for D is awesome.

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

I really enjoyed the problem set after a while being away from lovely Codeforces rounds. Thank you PrinceOfPersia for putting such an effort preparing the round and so quick editorial.

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

So, finally...

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

    Thanks to the great performance of doing A and B :D.

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

Today's Last position holding contestant of div1 got back to his previous position!

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

Achievement unlocked :)

Moreover — with more than 1,5 min margin :D.

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

    You know, when I saw this, it was like oh, I have no idea how this solution can be proved, but this is definitely right one, becuase Swistakk submitted it already:)

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

      Or another reason behind probable simplicity of solution could be that this was A ;). Talking about a proof — easy greedy works :).

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

Rather weak tests for B(e. g. 10723410 fails on 

4 2
aab
1 2

)

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

So... Whens your next round?

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

LOL i didnt expect to win after i spent so much unnecessary time on problems B and C. Nice problems BTW

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

finally increase in ratings. #HappyMe :-)

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

Damn!!! I should have known before that the rating decreases even if you make no attempts!!! What was that? :(( I thought a "fail at test #1" is an exception :(

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

damn ... i missed this round :(

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

Can someone explain me why line mid=lef+rig>>1; works correct in the solution 10719921?

I think the correct usage in binary search is mid=(lef+rig)>>1;

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

    ">>" has less priority than "+"

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

      Ohh.. My world has changed that moment! I thought bit operations are the most prior

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

Sorry for the bad idea

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

My code got accepted in problem D but fails in this case

8 2

ababa

1 3

expected 26

found 0

http://codeforces.me/contest/535/submission/10724364

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

where is the tutorial?

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

    How about reading the "UPD2" from the announcement or looking at "Recent actions"?

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

Thanks for problem C. For me it's harder than D and E :)

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

    And for majority of people it was easier than A :D

    UPD: Ugh, sorry, that post is about #299 not #305, I don't know how I have found myself here x_0

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

In Problem D div 2 what should be the answer if the test case is : n = 10 , m = 2 p = "ibic" m --> 1 3 as I found 2 AC solutions one of them get answer 0 10922320 and the other gets 456976 10746306

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

    The answer is 0. My AC solution gives 0.

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

Thx for this contest, and I became candidate master.0.0~

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

problem c was too easy :D

→ Reply