PrinceOfPersia's blog

By PrinceOfPersia, history, 9 years ago, In English

Hello Codeforces.

I'm honored to announce you, that Codeforces round #326 is gonna take place soon on Codeforces.

Writers are AmirMohammad Dehghan(PrinceOfPersia) and Ali Haghani(Haghani). There will be 6 problems in each division(4 problems are common) and you'll have 2 and a half hour to solve them. I hope you enjoy the problems.

I wanna thank Maxim Akhmedov(Zlobober) for his great helps in preparing this round, MikeMirzayanov for wonderful platforms of Codeforce and Polygon, Delinur for translating problem statements into Russian and MohammadReza Maleki(mruxim) and Ali Bahjati(LiTi) for their great advices (and LiTi again for some graphics).

This is my third round on Codeforces and not the last one, I hope.

This is the last round on Codeforces with Zlobober as coordinator. It was nice working with him. We had a lot of fun and interesting contests during his coordination. I just wanna say: Thank you Maxim for all your contribution to CodeForces community and good luck in the future. After I heard these news, my first guess for the next coordinator was I_love_Tanya_Romanova; But I don't know if CodeForces hires people from out of Russia or not.

The main character of this round is Duff, but you'll also have to help her friend, Malek!

I wish you all high ratings and lots of joy.

Scoring will be posted soon.

GL & HF!

Problems are sorted by the expected difficulty, but we strictly recommend you to read all the problems.

UPD: Scoring is: 750-1000-1500-2000-2500-3000 in Div.2 and 500-1000-1500-2000-2750-2750 in Div.1 .

UPD1: Editorial is published.

UPD2: System test is over. Congratulations to all winners.

Div.1 Winners are:

  1. qwer1561
  2. Endagorion
  3. jcvb
  4. subscriber
  5. wjh720

Div.2 Winners are:

  1. sleepy_mario
  2. BIT-silence
  3. Owaski
  4. Orenji.Sora
  5. JavaInTheSouth

Also congratulations to JoeyWheeler, the only one who solved problem Div.1 D.

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +123 Vote: I do not like it

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    Came from gym... tired... was really afraid to be late on this round...

    Gym makes my body better and Codeforces makes my brain better!

    Really hard week but I'm marchin on to become better & better...

    Vote up if you agree that SPORT and PROGRAMMING are really good compatible!!

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

      Now I believed it's Instagram not Codeforces... :/

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

        I've just wanted to share the best part of my life with you guys, to inspire new achievements...

        Is it bad desire or what?? :(((

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      If you DO NOT agree please DO NOT vote down, I'm loosing my contribution :((

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

        Lol. Guess you don't like the "bad boy" image :p

        thug life

        this is not instagram

        let's keep it that way

        please :)

»
9 years ago, # |
  Vote: I like it -84 Vote: I do not like it

THIRD

»
9 years ago, # |
Rev. 4   Vote: I like it -210 Vote: I do not like it

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

    what does it mean? Zlobober is still alive ;)

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

    Damn. I've been laughing at "R.I.P" for about an hour now, and I feel bad for it xD.
    Anyways thank you Zlobober! :D

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

Mother of math contest is coming :v will miss you Zlobober :(

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

Your first guess seems to be wrong :)

Looking forward to an interesting contest) And I'm also curious about next coordinator)

»
9 years ago, # |
  Vote: I like it -50 Vote: I do not like it

How can purple user prepare Div.1 round??

It seems a bit nonsense like grey user preparing Div.2 round...

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

I want to thank Maxim on fantastic work and good contests. I was prepared one round with this great guy and I hope we will meet again :)

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

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

GOOD JOB, Zlobober!!!!

»
9 years ago, # |
Rev. 2   Vote: I like it +46 Vote: I do not like it

very good character ;) hope she dislike math :|

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

codeforces bug ??

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

I'll be specialist this contest :(

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

And i had already got used to seeing Zlobber on each round publication. Oh Well!!!

Missed Gerald. Will also miss you Maxim. Even though some people(me included) might not comprehend the amount of work required to be coordinator, we can all agree that you did a great job.
Thank you once again

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

HackerRank HourRank1 and Codeforces round 326. Tomorrow is gonna be fun!

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

    Look at my day :

    • school, test from Algebra

    • HourRank 1 — my third competition as problemsetter :)

    • Codeforces round 326

    • Learing logic and prolog for test in Friday

    And yes, I missed today TCO SRM — sorry Errichto, my dear friend. School was sabotaging me :(

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -44 Vote: I do not like it

      Сменку не забудь))))

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

        It's the worst idea to write message in Russian, in English blog.

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

      Tough day. I forgive you then.

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

Who is this "Duff"? :/

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

Just iranian's know the meaning of duff ;)

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

Hi I really become glad when see that Iranian Coders prepare a round:) But i have a sugestion for you PrinceOfPersia, Please prepare persian version of problems for iranian coders. Ty hf with The Duff :) :P

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

I 'm waiting timer :)

»
9 years ago, # |
  Vote: I like it +51 Vote: I do not like it
  00:30 start time (local time)
+  0:10 expected delay
+  2:30 contest
+  0:30 system test
+  0:30 rating changes
= 04:10 sleep time
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I suspect that there are many hacks in today's contest good luck everyone!!!

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

wish a duff contest too. :D

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

Thank you !

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

Congrats! :D
You're now first in top contributors list.

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

    And also congrats for your gold medal of iranian national olympiad in informatics.

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

Dear dynamic score
I hate you

»
9 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Duffy...plz don't sit on ur duff

Duffy..Duffy..Duff :-p

»
9 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Have I opened CF or Instagram :/

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

Good_luck everyone!!!

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

Isn't it late enaugh to post scoring?

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

"Problems are sorted by the expected difficulty, but we strictly recommend you to read all the problems."

Famous statement. I smell a rat!!!

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

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

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

no delay until now!

thanks god! i wish it continues!

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

Did 6 problem rounds become standard ?

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

CF round 326 Good luck to everyone!!! 3*2=6 :)

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

Here comes the 10 minute delay :D

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

In problem C, if I have subsequences (1.2.3),should I connect 1 and 3 after erasing 2.

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

So satisfying!

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

That's why, when he saw her minister, Malek, free, she gave her a sequence consisting of n non-negative integers, a1, a2, ..., an and asked him to perform q queries for her on this sequence.

What is this gender-fluidity?

I'm going to make a round about amoebas and randomly change gender pronouns throughout the statements!

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

Seems like Div. 2 C is going to be one of the most hacked problems in Codeforces history...

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

    It also happened to me :[ I am sorry but is it possible for others to hack my solution after I locked it immediately ? In the case the answer is no, how could this happen that after 20 mins of locking the problem, 2 people just hacked it?

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

      Locking your solution doesn't protect it from hacking. It just gives you the ability to hack other people's codes.

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

        So how can I prevent it from getting hacked ?

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

          code the correct solution :p

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

            You mean if it gets hacked, it's because the code couldn't pass all the test cases ?

            Alright I got it !

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

              If it gets hacked, it contains some bugs. But if it contains bugs, it may pass systests.

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

              yup !!

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

          Write correct solution

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

          Submitting the right solution haha. If your solution has any failure people will always be able to hack it.

»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Div 2 Problem D requires PhD in mathematics.

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

I thought score was dynamic, but it was fixed!

However, its time to get the editorial right now as it is a contest of PrinceOfPersia !! :)

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

It seems to be a nice contest. Aparently I was to busy with problem F to try all problems but anyway :)

Btw, is there solution faster than for F?

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

Good problems .. ))

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

It was a nice competition, Had fun solving the Problems :).

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

Does anybody know what was Div2 D pretest 4? Spent half an hour debugging with no success... =(

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

    To pass 4th pretest, you have to use long long. I wrote #define int long long and passed it.

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

      Bloody hell. I guess this will be the last time I tried to use long long only where I thought I needed it...

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

        Got TL in the hardest problem last time because used long long instead of casting to long long only on multiplication. Didn't get place on the top.

        So, think twice

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

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

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

2 times I battle with TLE resulting from scanf vs cin :(. Cin: not even once.

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

im so eager to know what the test11 is in D2 C, spent almost 2h solving this problem and FAILED!!

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

Oh my god.what a fast editorial and system testing.

»
9 years ago, # |
Rev. 3   Vote: I like it -11 Vote: I do not like it

This my AC submission for D2-C: 13635586, with 218 ms. This is my previous submission for the same problem: 13634487, that got TLE.

However, the only difference of the two submissions is the array length. The former has 1M, while the latter has 2M.

Can someone explain this phenomenon? My previous submission should have been AC with around 500-600 ms :(

Edit: nvm, I used cin/cout in the previous submission... :(

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

    only difference is array length? You change cin to scanf buddy. Scanf is faster!

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

    Its not actually because of cin/cout. If your array was 1M length, that means there is no cell of memory in 1M+19, as it has to be. It was a popular hack though!

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

      He uses array 1000100 — length, plz don't comment if you even don't see the code. ><

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

I think somebody submitted a wrong code for C or D (div1) and now he/she is going to get accepted and the writer is adding some test now. :D Is it right?

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

How to do div 2C problem?

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

Div 2 C got TLE only becuase I used cin cout....logic is correct. This shouldn't happen..shouldn't it? The time should be given such that it will get AC irrespective of input method :(

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

    The problem is that in that case, inefficient algorithms with scanf would also pass. Sorry, but you just have to use scanf for large input problems =/ (I had some submissions fail because of that today too...) OR use ios_base::sync_with_stdio(false);cin.tie(false);cout.tie(false);

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

    so... Make the time limit so that Java's Scanner(System.in) would pass? This would allow for much less optimized algorithms in C to get passed.

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

very easy and noble the pretest, I hate this competition's system

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

    Pretests are good. They permit the whole "hack" system to exist.

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

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

»
9 years ago, # |
Rev. 2   Vote: I like it +29 Vote: I do not like it

Good problems, but the jump in difficulty between div1 ABC and DEF was way too big.

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

My old laptop's battery run out of charge in the last twenty minutes and then I try to edit my code on my mobile phone but finally got a Compile Error...

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

Eh, my sqrt-decomposition on Div2-E gave TLE :( I was too lazy to code HLD and I didn't want to copy my previous implementation since I don't like copying old codes. Somebody who got AC with sqrt-decomposition?

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

    There's no need for HLD, you only need the same structure as for LCA (except this time storing also the 10 smallest people on the path 2k vertices up from v, not just the 2k-th parent of v). Then, it's just LCA+mergesort.

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

      Ah, I am such an overkiller :D Thanks for the explanation, it seems much easier now! :)

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

        Generally, this tends to be a full replacement for HLD as long as there aren't any updates.

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

          Thanks for sharing that, I will know it in future! And congrats for becoming red again! :)

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

        Speaking of overkill, I used persistent segment trees to solve this problem.

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

      What is HLD. Will not work Heavy Path Decomposition?

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

        Heavy-Light Decomposition. The same thing, a slightly different name.

        It will work, but as I mentioned above, it's a total overkill.

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

I think it's better to swap problem E,div1 and D,div1 and the score of D,div1 being 3000.I mean that the arrangement of the question be like this: A,div2 B,div2 A,div1 B,div1 C,div1 E,div1 F,Div1 and D,div1

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

this contest learns me this:

all prime divisors of N are not between 2 and sqrt(n) ! just its for testing is it prime or not!

thanks PrinceOfPersia XD !

*sorry it was t not w!

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

    actually you are wrong, and this is one of the reasons so much people got hacked.

    For example, consider number 33. It's square + ceil is 6. But the prime divisors are 3 and 11.

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

50th place! Rating +4, here I come!

UPD: Damn, I never get it right with this new formula.

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

The contest can get unforgettable if the rating update very soon.

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

Why this submission gave TLE? (Problem C, Div 2) http://codeforces.me/contest/588/submission/13648330

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

    cin >> a;

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

    due to cin Code needs I/O optimization. Change cin to scanf

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 4   Vote: I like it -30 Vote: I do not like it

      I hate when I see this type of comments. Scanf is not faster than cin, not even close on newer versions but cin is synced with scanf as a default since 4.6(?) which means it uses scanf behind the scene. You can use ios::sync_with_stdio(false; în your main function and see the difference.

      Do that before any reading and don't use both scanf and can.

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

        I hate such comments like yourth, because SCANF is faster and it is FACT! Example of codes which are simular but not pass with cin and ios::sync!

        Code with cin and without cin As you see, it is faster MORE then TWO TIMES!

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

    It's enough to write

    ios_base::sync_with_stdio(false);cin.tie(false);cout.tie(false);

    at the first of your code and now I think you can get AC with cin/cout.

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

    cin >> a; was giving TLE. I got AC now :/.

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

Why TLE in test 38??? please, i need help http://codeforces.me/contest/588/submission/13643971

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

Does it take much time for the contest to be published on your profile? I mean, for the rating change and all that

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

    It usually takes 1 — 2 hours. Bingo! It's there.

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

      It's the first time I take park in a contest. I had to leave a 30 minuntes from the beginning, so I just solved 1 problem. My rating lowered in 62 points. It's kind of funny

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

        Yes it's weird. I think rating on Codeforces depends on previous contests also. That's why even when my ranking was better than other people but still i have a lower rating than them!

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

This is my submission for Div2B : # 13646742 The logic is the same as given in editorial but for some reason it's giving different answers on my IDE (correct) and CF judge (wrong).

the link: http://codeforces.me/contest/588/submission/13646742

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

    pow function is messing up with your answer Tip:Never use pow function

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

I solved A and B in Div-2 and passed system test ... Why skipped ??!!!!

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

    Cheating.

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

    You may have Multi ID or Your code may be matched with someone's . That's why thus happens what I am thinking . Same problem happens to me .

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

      May be matched with someone's, but I never cheating :/

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

Really nice div1E, solved after the contest.

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

Could someone give me a tip about how I can remove the "Memory limit exceeded" from my code for div.2 E? http://codeforces.me/contest/588/submission/13652236 I tried to make a LCA of sets...

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

Its strange changing cin (alongwith ios::sync_with_stdio(false);) to scanf worked. Was getting TLE with cin

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

Screencast of me failing rounds.

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

Looks like someone got a bit too angry :P

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

Can anyone offer a brief explanation about problem E please? I really don't know what is the basis of a vector and why the answer is 2 ^ (b.size()) ...