Mahdi_Jfri's blog

By Mahdi_Jfri, 7 years ago, In English

Hi Codeforces!

I'd like to invite you to join Codeforces Round #446 which will be held on November 17 at 17:35 MSK.

And yes it is rated.

The contest is prepared by Omid Azadi (omidazadi), Mehrdad Saberi (Batman), Arshia Soltani (ckodser), Aryan Esmailpour (Aryan) and me (I honestly didn't do anything).

And also thanks to Mahdi Amiri (Amiri), AmirReza PoorAkhavan (Arpa) for helping us, Weihao Zhu (Tommyr7) for testing the round and Nikolay Kalinin (KAN) for round coordination and Mike Mirzayanov (MikeMirzayanov) for awesome platforms Codeforces and Polygon.

You will have 2 hours and 5 problems each division.

Contest theme will be about Seven Deadly Sins but the statements will be short and brief.

The scoring distribution will be posted soon and good luck and stuff.

Update 1 : The scoring for both divisions is 500 — 1000 — 1500 — 2000 — 2500.

Update 2 : The round is over. Hope everybody had fun and enjoyed it. And as you can see the round is rated so yay!

Top 5 Div1 participants :

1.jqdai0815 (The only one who solved all problems)

2.Radewoosh

3.dotorya

4.SkyDec

5.ksun48

Top 5 Div2 participants:

1.shoob

2.mosthenio

3.SLLN

4.fdoer

5.dl1997

The editorial is posted.

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

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

Do you mean the anime "Nanatsu no Taizai" or just the typical Seven Deadly Sins? I hope it's the anime one! :D

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

Mahdi_Jfri If you didn't do anything so why did you write the announcement?

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

    I wrote it so now I have done something!

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

      Oh, it seems Mahdi_Jfri have done a very important and great thing. I think so too.

      Due to CF Round #444, #445 was unrated, everyone is hoping that this contest will be rated. I hope so too. There’s a risk of getting 1000+ downvotes in this announcement if it is unrated, as far as see the last 2 contests. So I think less than half can have courage to write an announcement if they’re writer. So I think he is brave, and he make great contribution.

      But I hope this contest will be rated with 99.99999999...% = 100% probabilities.

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

        why are you always whining about downvotes. please get over it.

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

          No. But I think that mentioning about upvotes/downvotes is important to support how much contributed it is about writing today’s contest announcement.

          Btw it seems there are many other way to support his contribution. (Writing announcement is originally a type of contribution.)

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

Is it rated?

»
7 years ago, # |
  Vote: I like it +74 Vote: I do not like it

Hmm..

The "greed" problem will probably involve greedy technique as its solution.. or it might be a trap.. :|

Just a prediction lol~

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

    Haha :)

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

    "Wrath" will actually not be a problem, it's just the feeling that you have when the servers go down mid-contest.

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

I hope it won't look like this

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

We hope that this round will not become unrated magically.

UPD: Ok, ok... I hope...

»
7 years ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

It will be enjoyable contest. Because it has a tag best round ever. . .

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

Previous two round was unrated. Now what should be our expectation from this round????

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

    "Best round ever"

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

    sa1378 is my bro xd he won't betray us

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it -39 Vote: I do not like it

    We have a binary random variable X with Bernoulli distribution.
    P(X = 0) = 1 - p — probability of an unrated round
    P(X = 1) = p — probability that the round is rated

    What is the probability that X = 1, given that we saw X = 0 two times in a row?

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

      This sir is a glorious comment.

      You deserve my upvote.

      (Not that it matters because it has so many down votes any way)

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

Seven Deadly Sins, I was looking forward to more Arpa and Mehrdad adventures :(

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

Is it unrated?

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

    we make this unrated!

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

      externalgoal, you are so suspicious. But please, don’t open your solution during the contest... You want downvotes... I know. But we’re wanting strongly, a rated contest. Please don’t open your solution during the contest... please...

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

    Just wrote a piece of code to answer this ultimate problem.

    text = readFromURL("http://codeforces.net/top-contributed/friends/false/page/77")
    
    if text.find("NoMoreThanANoob")
    then print "Unrated"
    else print "Rated"
    
»
7 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Unrate or riot!

»
7 years ago, # |
  Vote: I like it +50 Vote: I do not like it

I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.

Taking one for the Community.

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

Is late registration there? I am returning to codeforces after a while — is it there in all contests now?

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

hi I'm kinda a noob and was wondering what the difference between dev.1 and dev.2 is... would really apreciate it if someone answered... tnx

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

    Okay so div1(div stands for division) is for people with ratings in the range 1900-9999 and div2 is for us noobs below 1900 rating.

    Since you haven't played any CF rounds, you will be playing in div2 to get your rating first. Your default rating is 1500 I guess.

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

Is the CF great now ? :D

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

    After the situation of past CF contest it might be improved enough :)

»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Good to see "the statements will be short and brief" Waiting for the statements!

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

Arpa and Batman's contests are always amazing!!! i think this tradition return its value :).

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

I like the confidence in the problem-set of this contest

»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Yaaaay a Persian contest! I hope I can wake up for this lol

»
7 years ago, # |
  Vote: I like it +121 Vote: I do not like it

Upvote me, please. When I look at my contribution, my mood falls down.

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

    Do not be beggar! Do not look for easy ways!

    Just comment wisely and you will faint , when you see your contribution.

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

    Can't agree more, I wanted to say this but didn't dare to do it :( Negative contribution is like saying "Codeforces community will become better without you", and now I started to think if it's true.

    Can I have positive contribution like others too?

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

    Foolproof way to increase contribution:

    https://snag.gy/X3qRLQ.jpg

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

well , all people with good contribution don't wear capes , some just comment in that manner , and magic happens :) :)

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

Hope that there would be no issues like the last "rated" contest...

»
7 years ago, # |
  Vote: I like it +135 Vote: I do not like it

Seven deadly sins:

Gluttony
Lust
Wrath
Envy
Pride
Greed
Sloth
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It is delayed?

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

Deleted

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

    Why only Iranian guys? Other guys also cool. People though are divided by the nation but to show discrimination on the public site is stupid.

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

Yeah!!! I love this anime!

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

I hope this time it will be rated!

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

Again rated, again...

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

    Congratulations! So how did you handle it?

»
7 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Let's wish good luck codeforces servers)

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

Hope today is the day Codeforces Servers get out of gray

»
7 years ago, # |
  Vote: I like it +123 Vote: I do not like it

Five Deadly Sins for Codeforces

Sin 1
Sin 2
Sin 3
Sin 4
Sin 5
»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

my three TOP only one things I have known in this world.

1 the sun. 2 the earth. 3 the only way to change the color of our handles in codeforces.

I hope everyone here to pass this way positively in this contest! Good luck to Everyone!!!

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

    the only way to change the color of our handles in codeforces

    When will Christmas come?

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

Is it rated?

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

Fix your damn servers..

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

Why it is so slow...I submit a code 5 minutes ago…… and now I found I got a WA

»
7 years ago, # |
Rev. 8   Vote: I like it -32 Vote: I do not like it

Seems like it will be a 3rd consecutive unrated round.

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

    Yep, I have to wait 5-6 minutes for each submission.

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

Thanks god for short problem descriptions

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

problem Ds difficulty is inverse of Cs difficulty for the past 3 contests, i think. D is very difficult.

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

It is really really disappointing that the server issue is still there :/ I mean, how can one enjoy a contest in the current situation where almost every submission takes 5-6 minutes to give verdict, even hacks. It's frustrating :(

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

It doesn't look like problem div2C has much to do with "Pride".

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

    Have you notice the case when there is more than one 1 in the array? The idea is that the solver can be proud of themself when they come up the solution and forget to handle this.

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

      I do hate problems where not all the corner cases are part of the pretests because it's stupid to lose a whole problem for a particular case. But, in this particular problem, if you proved your solution, you'd easily see this case (now, again, I believe it should be included in the pretests), so it's pretty unlikely for one who proved it to fail on that case. So I'm not taking "their" side, but I just think that you haven't actually solved a problem until you proved it. These corner cases, though, should not cost any more than just an extra submission (after seeing you failed on pretests)

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Problem Div2 B TLEd because of slow I/O (cin/cout in c++), and worked well with faster I/O (scanf, printf). Doesn't make it interesting.

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

    Same here. I don't see why the need for 10^6 max value for n (instead of the usual 10^5).

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

Will this work for Div1B/Div2D ? Output the next element in sorted order for each number. like if array is [2,4,1,3] output [3,1,2,4]. Seems too easy(given the constraints N <= 22) but i cant find whats wrong with this.

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

    try 3 5 6 2

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

    I was nowhere close to the solution but I think maybe n < 22 is for checking whether the condition is true for your logic

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

    Wht's the role of a[i]?

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

    Actually it works perfectly. If you choose one subset that does not contain the biggest element from the first array, then there is a map between elements in the first array to a bigger element in the second array (the one it becomes). Otherwise there is a map for a smaller element, so sum will never coincide.

    I thinks the n up to 22, was a misleading clue to confuse contestants. I tried to come up with a 2^n dp but completely failed.

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

Very interesting D.

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

very good (trolling) name for problem Div1D. I really lazy to code all this cases...

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

How to solve Div 2 D/ Div 1 B and div 2 E/ div 1 C?

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

    Div1B
    If any repeated elements are present then no solution
    Else put b1 = a2 , b2 = a3 , b3 = a4 , ... bn = a1 (Assume a is sorted)

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

      Isn't 5, 3, 4, 1, 2 a counter-example?

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

        yes, array should be sorted first and after that shift.

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

        Maybe i misunderstood smth, what will be the output for 5, 3, 4, 1, 2?

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

      [3 1 1] has no solution??? I think [1 1 3] is solution for this input. Am I wrong??

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

        array elements should be distinct so the test case isn't valid!

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

      I understand your solution, but is there any formal proof why it always works???

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

        after sorting a let c[i] = b[i] — a[i] then c[1] , c[2] , c[3] , ... , c[n-1] > 0 while c[n — 1] < 0 and sum of C's is 0 so obviously no proper subset will have sum of c as zero.

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

    Div1C
    consider all edges with weights <= C , then any minimum spanning tree (forest) consisting of these edges will have the same set of connected components
    So have an offline solution where for each i from 1 to MAX , you first check if for all query edges with this weight if they can be added , if not then mask this query with "NO". Then forget these query edges and add actual tree edges with weight i.
    This works because of the reason mentioned at the beginning.

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

      "any minimum spanning tree (forest) consisting of these edges will have the same set of connected components"

      Can you please elaborate on that a bit more?

      TIA!

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

Does solution to D use this?

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

    Of course.

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

      My solution which I hope is correct (it passed the pretests and it really makes sense) doesn't involve that observation (even thought at some point I made it and hoped it'd help, I didn't find it of any use)

»
7 years ago, # |
Rev. 5   Vote: I like it +23 Vote: I do not like it

Heck test for Div2C:

3

6 10 15

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

    What will be the answer for this case? My code prints 5 for the former test case you posted. For this test case, it prints 4.

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

How to solve D? I was thinking in terms of bitmask and reversal of highest bitcount numbers.

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

    If the sequence is sorted, (I call it as a1 a2 a3 .. an), then the B seq is a2, a3,a4,a5..an,a1. Then just for every element in the A sequence, print the smallest element that is bigger than it.

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

yay! Finally Rated Round ! I need +1 rating gain for becoming specialist again , and finally I will be specialist once again. :)

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

 My attempt today in a nutshell. (Div2C/Div1A).

Well, many thanks to the problem setter xD (No, really, this is the best pretest set I've ever seen — hacking comes in so many levels :) )

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

Then the feeling when the TL 2000 ms and the participant code runs 1996 ms(

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

Will this work for Div1B/Div2D? Output the next element in sorted order for each number. Like if array is 2 4 1 3 print 3 1 2 4

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

    That's my solution and it passed pretests.

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it +37 Vote: I do not like it

    Yes, and it's easy to prove. Let's consider for convenience the permuted arrays a and b:

    a1<a2<..<a(N-1)<aN
    ^   ^     ^      v
    a2<a3<..<aN    >a1
    

    If we take any subset that doesn't contain the last element, the sum on the lower side will definitely be bigger. So, we'd only have a problem with those that contain the last element. We need to balance a difference of aN — a1 with a subset of the values a[i + 1] — a[i] for 1 <= i < N. The nice part is that all those are positive and only if we choose them all will we be able to balance the differences (otherwise the total balance from the second part is still too small)

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

      I understood the proof when subset doesn't contain the last element. I didn't get how you proved the sums will be different when the subset contains the last element. Can you explain it again in more detail ?

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

        Let 1<=i1<i2< ..<iK<N be the positions you choose so that you get equal sums, when adding position N to these. You must have:

        a[i1] + a[i2] + .. + a[iK] + a[N] = a[i1 + 1] + a[i2 + 1] + .. +a[iK + 1] + a[1]

        By moving terms from a side to the other, you get:

        (a[i1 + 1] — a[i1]) + (a[i2 + 1] — a[i2]) +... + (a[iK + 1] — a[iK]) = a[N] — a[1].

        Now, on the right part you have a positive constant. On the left part you can choose for each position j with 1 <= j < N whether j is part of the chosen subset, and in the same time, whether you add a[j + 1] — a[j] to the sum on the left side or not. All the possible values of the form (a[j + 1] — a[j]) are positive. So choosing any of them increases the sum. Now, if you choose them all, you get (a[2] — a[1]) + (a[3] — a[2]) + ... + (a[N] — a[N — 1]) = a[N] — a[1], which would be alright, just that you can't choose all the indices. So you need to give up some of them. But since all of them are positive, giving up any of them will lead to a lower value on the left side, which means that unless you choose all the positions you can't get equal sums, which is exactly what you need

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

    If you don't mind Sarvagya, Can I ask you something?

    You have not given any contest from quite sometime and after each contest ends, you ask "how to solve problem X?" Do you give contests with a fake ID? Because it seems so. If yes, why?

    Please don't ignore. Thanks.

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

      Why would I comment with this account if I am participating with a fake one?

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

        Why would you comment "how to solve problem X?" just after any contest ends if you haven't participated or haven't seen the problems?

        And seeing problems without participating during contests make doesn't makes sense.

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

          Huh, I do this all the time — I just do not have enough time to do any Codeforces Round until recently so I just read the problems and ponder(?) about them in my free time. Also I want to improve my thinking speed for ACM (I rarely code — my code sucks) so it really helps. I also have friends who read problems and seek for solutions without participating to gather as many ideas as possible (lol idk how it works but oh well).

          Not trying to 'solve' the case or anything, just pointing out it is not that abnormal at least for me.

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

How to solve div2 D/E ?

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

How to solve div1.E ? I am not good at this kind of problems, but anyway, nice contest and nice problems.:)

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

    I see it can be solved by generating function.

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

      Author's solution is completely different unfortunately we didn't predict that it can be solved by generating function :(

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

Can anybody explain me why my first div2 B submission got tle on test 9 having the complexity O(n) and using cin — cout, but after that i used scanf — printf and my second submission got accept. Why?

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

    cin/cout is by default synced with scanf/printf, which caused the I/O process in C++ submissions to be pretty slow on large input if we don't switch of the sync. Personally, I'll insert ios_base::sync_with_stdio(false); on any source code files I create to switch off the default sync.

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

    cin/cout is slow.

    If you want to use cin/cout, include these three lines at beginning of your main() function.

    ios_base::sync_with_stdio (false) ; 
    cin.tie(0) ; 
    cout.tie(0) ;
    
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Cin/Cout is slower than scanf/printf. Keep it a rule of the thumb when n >=1e6 the IO becomes the bottleneck. Use scanf/printf or instead http://codeforces.net/blog/entry/10297

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

    thanks for advices and explanations

»
7 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Thanks for nice problems! Is there any neat way of solving Div1D? I tried some long and ugly dp which took 1hr to code but don't even pass samples

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

    My solution (it's different from author's) uses dp on tree and I can't say it's ugly. I will post a link to my submission after the system testing ends.

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

    Here is my solution: 32407269.

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

I wrote this program for Div.2 B but still got Time limit reached in pretest 9: could someone please tell me whyyyyyyyyyy?

include<bits/stdc++.h>

using namespace std; int main() { int n,s=0; cin>>n; int arr[n]; for(int i=0;i<n;i++) { cin>>arr[i]; } reverse(arr,arr+n); bool arr2[n]; for(int i=n-1;i>=0;i--) arr2[i]=true; int count=0; int last=0; for(int i=0;i<n;i++) { if(arr2[i]==true) count++; if(arr[i]!=0) { if(last<=i+arr[i]) { for(int j=last;j<=i+arr[i];j++) arr2[j]=false; last=i+arr[i]; } } } cout<<count<<endl;

return 0;

}

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

    sorry for that....

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

    cin/cout is slow.

    If you want to use cin/cout, include these three lines at beginning of your main() function.

    ios_base::sync_with_stdio (false) ; 
    cin.tie(0) ; 
    cout.tie(0) ;
    
»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Great thanks for the short statements, this just made my day :D i hope all setters do the same

Also for the interesting tasks, enjoyed doing them...

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

Why break the consistency, let's make this round unrated! :D

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

How to solve div2 C?

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

    Let's suppose array contains count number of 1's.

    • If count ≠ 0, then every non-one element has to change into one. So, ans = n - count.
    • If array doesn't contain any 1, then compute in the following way.
      You have to find the minimum length of subarray, whose gcd is 1, let's say, it is p. First you have to create one 1 using (p - 1) operations on that subarray. Then, change other non-one elements into 1 also using (n - 1) operations. So, ans = n + p - 2.
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone Explain How To Solve Problem B Div2.

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

    You need to answer whether the i'th person will die in O(1).
    He will die if there is some other person to the right j > i which can reach the i'th person.

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

Just take input 10^6 element using cin>> cause TLE in problem B. -_-

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

    I think this is a good thing to teach people how to use their's language from time to time =)

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

What's the motivation behind the constructive algo for Div2D/1B? Like, how did you arrive at the thought of trying exactly that algorithm?

»
7 years ago, # |
Rev. 5   Vote: I like it +75 Vote: I do not like it

Is it normal to lock after getting hacked?!!!! KAN MikeMirzayanov

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

Problem Div 2-D is overestimated !! it should be categorized as B. Also the constraints is so tricky (22 numbers?!!), that tends my way of thinking towards something like backtracking and bit-masking. But it so easy just sort the numbers and replace each one with the next element after sorting.

Whatever I didn't take care that the numbers will be distinct and I have known that after the contest.

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

    Actually if n > 22 then we can't check if the participant answer is correct or not.

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

      Well, i believe they can be slightly (~40) more if you would write meet-in-the-middle knapsack in checker (however this only increases possibity of incorrect checker and doesn't really change anything).

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

      Noob jafar

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

      Actually there is a way — you could specify a way to generate testing subsets and provide a number — for example first X subsets in lexicographic order. You could also provide some additional number of subsets given explicitly — to verify some random subsets on larger sequences.

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

Long check :(

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

can someone plz tell me how to solve div 2 D and why that works

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

hey , congrats to moejy , he is the second on codeforces now :D ,again,

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

Thanks a lot for this sweet contest! Really glad it went well, unlike 2 previous ones.

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

Tests to div1 C might have been better. Accepted submission: http://codeforces.net/contest/891/submission/32408123

Fails almost example test (replace vertices in first edge):

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

    And here is my accepted solution.

    Which fails the following test:

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

Hi guys! Unfortunately, Codeforces API is down, that is the reason why CF-Predictor doesn't work.

You could find last saved snapshot here: div1 div2.

UPD Official rating has been updated, but API still down.

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

Great problems with short statements, I really enjoyed it, thanks!

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

can someone plz tell me how to solve div 2 D and why that works

»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

My solutions were skipped because somehow someone copied my solution for Div1-A.
http://codeforces.net/contest/891/submission/32389480
http://codeforces.net/contest/892/submission/32400911

I have no idea how this happened. And no, I didn't use Ideone. KAN, please fix this!

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

    I see there is a flaw in codeforces to disqualify someone: when you lock a problem, it is possible to view roommate's code, then send it to other :)

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

      Damn, you're smart, brilliant observation :) I wouldn't come up with it by myself.

      Is there an easy (no matter if allowed by rules or not) way to get that code without retyping it? Anything easier than text recognition programs.

      I already thought that I got hacked since I didn't use Pastebin/Ideone either. And now it is like 50/50 :)

      P.S. I don't remember how it works — can one read codes by all contestants after locking (without being able to hack them), or only codes in his room? None of the coders in my room have problem C locked, so in case you can only read codes in your room — for me the reason should be different.

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

        You can only read codes in your room.

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

        Is there an easy (no matter if allowed by rules or not) way to get that code without retyping it? Anything easier than text recognition programs.

        I think that Flash applet gets the code from the server in a text representation and then renders it in a non-copyable widget. Will try looking into this.

        can one read codes by all contestants after locking (without being able to hack them), or only codes in his room?

        IIRC you can read the code only in your room. At least with the current interface.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 3   Vote: I like it +40 Vote: I do not like it

      Hmm, looks like you can also disqualify yourself if you are doing poorly in contest and don't want to lose rating: just submit your code again with fake account.

      Is this how it works? :)

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

        Cheating should result in account removal, to prevent this.

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

          That might work only if you can be sure when someone has cheated. As you can see, 2 red coders that most likely haven't thought of cheating were caught by the system. Even if any of them used ideone (which they didn't), do you think that because of a mistake (not of a desire to cheat), they should have their accounts removed?

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

          I've always thought that an interesting method to try to deter cheating would be to consider the cheater as earning a score of 0 (or maybe -INF) in the contest (and consider all of his/her submissions as incorrect). This way, cheaters would still lose rating, which I think may do a better job preventing cheating.

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

      but wouldn't they have to solve the problem to lock it?

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

    My solutions were skipped too because somehow the SAME guy (Helli.code) copied my solution for Div1-C. LoppA/32401950, hellicode/32405243. (Link for his submission is broken right now).

    I don't use Ideone too, I coded and tested the program in my computer and only submitted to codeforces. I also have no idea how this happened.

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

    Well, we will look into this and think what to do. Btw, these submissions are completely identical, so I doubt someone retyped it.

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

    This time we will roll back ignores for first submissions in a group of identical. After it we will recalculate ratings. But from this moment we will notify if someone submissions look like your and in case of repeated notifications we reserve the right to apply penalties.

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

      I feel that if someone did deliberately retype their submissions in order to sabotage them, those malicious guys would probably just do it to the same group of people again to damage their rating, especially upon reading this comment so Codeforces should probably be more careful of that.

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

        Getting into the same room, then retyping without a single mistake, indentation etc.? Seems unlikely.

        For me it seems more likely that passwords were leaked or there is another flaw in this website.

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

    I get the same trouble here

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

    the same trouble http://codeforces.net/blog/entry/55843?#comment-395662

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

Something is not right. User I_love_Tanya_Romanova does not appear in standings, even though he participated in the round and hacked my A submission.

Edit: Ok, looks like he was disqualified, but shouldn't all his hacks be removed too? They should be removed from final tests if they were added. KAN could you please comment on this?

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

    Maybe all submissions in the round were opened for viewing? I can't believe red users cheated.

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

    I got disqualified since my code for div1C matches with code for div2E by user best.code. I don't know exact way how it leaked yet :)

    Do you think the part about hacks is really that important? As I recall, out of my hacks three were like

    3
    6 10 15
    

    And one was something like

    8
    15 6 6 6 6 6 2 1
    

    I don't think they aren't covered by model tests and other hacks :)

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

      "I don't know exact way how it leaked yet :)"

      Perhaps you should ask EdwardSnowden.

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

      There's one way to do that:

      1. Pass pretests on one account in Div1
      2. Lock the solution
      3. Look at other people's solutions
      4. Submit a random red's solution on your account in Div2

      Or have a friend in Div1 to do steps 1-3 for you.

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

        It was mentioned that no one else in his room locked C.

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

          In that case Codeforces should just start using HTTPS

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

      best.code copied my div1B I don't know exact way how it leaked yet too

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

Thanks for the short statements:) But there were several mistakes in russian version

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

Fullmetal Alchemist ^_^

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

10 minutes before the end until the contest, I pasded problem B by using priority_queue. T_T

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

    I used segment tree in case of I can't pass problem B...because at that time I was sleepy and I couldn't come up with a good way to solve it(I even submit a wrong answer solution using dsu trick in segments...)

    Now I think everyone will take me as a fool because I write a segment tree in a div.2 B problem...

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

      In Round#419 Div2 ,I used Segment tree for B,too.I thought for 1 hour and submited for 5 times,pretest passed.Unluckily,I fst in the end(TLE)...

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

        orz xlj

        I think we should always come up with a suitable solution for one problem,instead of just writing data structures or some other things without deeper thinking.But sometimes these "force" methods can save us in some condition...

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 2   Vote: I like it -6 Vote: I do not like it

          .

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

            I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.

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

              I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.

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

                I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.

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

                  Hey Don't always think like this

                  You are not weak as you got good rank sometimes,but bad rank warns us more about our methods of thinking,coding and so on.It's just a coincidence that you got good rank but the contests are unrated.Instead of just complaining for the bad rank,you should believe in yourself and review the mistakes you made in some bad-ranked contests,then you will learn more and be easier to get good rank next time.

                  UPD:OK maybe you all don't like to encourage others or he was just joking = =

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

can someone please find why i am getting TLE in test case 9 in questuion 2. my code. and when i remove macro rfl it gets accepted! please explain.

include<bits/stdc++.h>

using namespace std;

define fl(i,a,b) for(int i=a;i<b;i++)

define rfl(i,a,b) for(int i=b;i>=a;i--)

define int long long

main() { int n,count=0; cin>>n; int arr[n]; fl(i,0,n) cin>>arr[i];int sum=0; if(n==1) { cout<<1; return 0; } rfl(i,1,n-1) { if(arr[i]>sum) sum=arr[i]; if(sum>0)count++; sum--;

        if(sum<0)
        sum=0;
    }
    cout<<n-count;

}

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

Sweet revenge by ovis96 xD

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

Can someone help me with Div2D/Div1B?

Maybe I have misunderstood the problem, but judge says: "wrong answer there are 2 sets with equal sum".

Input:

1 3 4 5 2

My solution:

3 4 5 2 1

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

    pick second and last element of each array, 3 + 2 = 4 + 1

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

      Thanks! I was thinking that it should be some interval like [1, k].