danilka.pro's blog

Codeforces Round #330
By danilka.pro, history, 9 years ago, translation, In English

Good time of day, Codeforces!

I am glad to announce that this Sunday, 8th November at 19:30 MSK, Codeforces Round #330 for both divisions will take place.

The problemset of the round has been prepared for you with pleasure by Alex fcspartakm Frolov and me, Dan Sagunov. We want to thank the coordinator of Codeforces Gleb GlebsHP Evstropov for his valuable help in problem preparation, Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon systems, Maria Delinur Belova for translating problem statements into English and Vladislav winger Isenbaev and Alex AlexFetisov Fetisov who have tested the round problemset.

Every participant will be given two hours to solve five problems. We have tried to make the round problemset variative and interesting and therefore we strongly recommend to read all the problem statements during the round. Scoring will be announced later as always.

We wish good luck and high rating to everyone!

UPD. We are sorry again for the mistake in Cdiv2/Adiv1 problem: jury's solution is working wrong in odd n case. We are hoping that other problems was (or will be such in upsolving) interesting and useful.

Anyway, let's congratulate the round winners:

First division winners:

  1. jcvb
  2. 2222
  3. KAN

second division winners:

  1. Tagrimar
  2. fsps60312
  3. uhateme

Editorial could be found here.

UPD. Problem Cdiv2/Adiv1 was fixed and now it has the statement and solution which jury meant it to be. Problem has been returned to the contest, so feel free to upsolve it.

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

Comments Comments (315)
| Write comment?
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

you used to be red :D

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

I like your problems... not too easy not too hard. thank you.

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

Finally we have Div 1 after A long time.

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

The comment is hidden because of too negative feedback, click here to view it

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

The links in my email seemed to be incorrect.I clicked Codeforces Round 330,but it went to http://codeforces.me/contests/587,588

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

"We wish good luck and high rating to everyone!". I may have believed that a week ago, but after explaining how the rating works it is clear high rating to everyone is impossible.

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

That is my time to be purple.Ok gays! if you want to have a good luck and increase your rating please thumb up me, and you will be lucky!

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

Last contest before regional Acm Icpc 2015.

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

Good luck and have fun!

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

how can i register for the todays contest round#330 (div.1)?

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

    hack a div 1 account :P

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

    Only Div 1 contestants can register for Div 1 contests.

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

    New contestants are only allowed to div. 2 contests. Once you have managed to gain a rating of >= 1900, you are allowed to to enter div. 1 contests.

    So simply join a few div. 2 contests. If your're an excellent programmer you'll be in div. 1 in no time.

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

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

hope this would be my last div2 contest :D

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

I can't take this contest because of school exam :( !

life is not fair !

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

    I can't take school exam because of codeforces contest :D

    Life is fair!

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

      I dream your life! ;D

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

      i cant do my homework for codeforces contest

      and ... fair unfair i dont now

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

Scoring will be announced later.....ammmm maybe after the contest :D

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

Where is scoring distribution??

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

today's contest also seem's like div1 contest..... how we solve ????

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

    Well , this time it's not so hard (at least as last round). :D. But i don't say it's easy too.

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

"Div 2 problems" ...

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

These kind of problemsets are a disaster! Such an easy A, then relatively much harder problems. Why did you wish us high rating? You knew that's a a lie.

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

why this hard contests ??? is there a revolution in the divisions ??? :_( please a div2 usual contest !!!

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

Div. 0 contest :)

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

What terrible problems... perfect round to make unrated.

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

    I think problem Div1A is really nice.

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

      I was confused by the statement, but it seemed like a nice problem. Take a look at Div2/B though — absolute nightmare.

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

Unrated round >.<

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

Why UNRATED contest because of one problem ??? This time I solved 2 problems and they did this.

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

    this is wrong! just do not count the C part! but why it has to be unrated?

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

      Simply not counting the problem wouldn't be fair to the people who spent a lot of time on it.

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

      are u fucking serious? well imagine someone spent a lot of time for C, solved it and then BAM 'time well spent'. yea great idea

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

After long time i was going to get under 1k rank and now it's unrated! :( Well now i am waiting next contest. :D

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

"Unfortunately, we are too tell" — the english is stronK in this one :)

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

    Think first, what would be your situation while getting such type of pressure! Can you think yourself in the place of authors?

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

      It's funny though isn't it? :). Btw these last 2 rounds reminded me why i stopped competing on codeforces long ago... Nothing has changed, hard to understand statements and problems not suitable for div2.

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

a unrated round after 1:30 hours. really?

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

    Think about the chances of finding out that your model solution is wrong. There's only one: a contestant raises a valid question.

    Of course, realising that it's not your solution that's wrong (as a contestant), but a model solution, requires actually writing something that passes pretests — and not moving on to the next problem. How many people would do that? In addition, it requires realising that what you submitted is totally wrong. That makes the chances even lower.

    It requires a lot of coincidences. 1:30 can even be quite early, I'd rather expect the error to be found in comments after the round.

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

      Why didn't authors stress their model solution against n·2n solution?

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

        Maybe they did, but the small test data weren't strong enough?

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

        What makes you think the smallest counter example is small enough for that algorithm to be feasible?

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

          Looks very reasonable that the minimal counter example has the length <= 20.

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

            I agree, but my point is that you can't hypothesize that they did not stress-test their solution when you have no idea what the counter example looks like.

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

        This is the right question. I modeled that the task is unsolvable with any greedy algorithm that I came up with using my minimax bruteforce solution as a etalon and a couple of hard test cases, but still was trying to find some "quirk", because didn't even consider a possibility of a wrong problem.

        Why didn't authors did it...

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

      You the contestant.

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

Well, perhaps that explains why I found Div1A to be so hard...

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

An unproven greedy strategy can mess up your codeforces round :p

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

That's why I recommend the authors to discuss the solution with me before the contest starts! ;)

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

ZLOBOBER COME BACK PLZ!!!

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

    this is the second bad contest of new coordinator. (just two good rounds) :( UPD : sorry GlebsHP

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

    Please Zlobober

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

    Best of the best of the best : Zlobober

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

    Please be polite and patient. First contests are the hardest ones, mine first days were also very nervous, sometimes I've been really close to have an unrated round.

    What you do is the worst possible action. Haters' comments like yours only increase the pressure, and make harder for everybody to hold a normal round. Just imagine how stressed will be the next contest authors. So please show some respect to the platform and to GlebsHP and be patient.

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

      +1 to Zlobober. This failure is also our failure as well. We didn't notice that on the presolving stage of the contest, so whoever wants to speak bad about new coordinator feel free to equally share your rage between all of us. More of that, working with GlebsHP is very nice. We will try to be more thoughtful next time and do our best to avoid these mistakes. Shit happens :(

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

In Hong Kong, I am doing this contest in MID-NIGHT and at the morning I need to go to school. And I still participate because I want my rating increase. Now this round is unrated... Really?

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

What do you mean by this?

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

    "We wish good luck and high rating to everyone!" ha? Could have become top10 if rated. Why not be rated for a part of the contestants?

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

Aw.. I solved (Div 1) D, was hoping for a lot of points. But I understand that making the round unrated is the right thing to do.

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

And now this contest is unrated :(

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

Now that problem C is removed, did anyone find something wrong with the logic behind explanation of test case 2? It doesn't seem right to me somehow :(

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

I wish it was still rated. Those who solved Div 2 A and B quickly will lose out on good rating :(

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

    rating is not everything, nor should it be the only motivation to code. just got swayed by emotion after the announcement so yes the decision should be fair to everyone :)

    plus the round writers have worked hard for this and they must have felt bad too. anyway, waiting for the editorials :)

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

Seriously, round unrated!!!!, i can't believe it, after 1:30 hours in competition, this is a disaster[contest:330]!!!

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

    wtf! cf had a lot of cool contests in these years!! how many of them gon wrong? NONE!! lets forget this brown day and v8 4 more cool contests.. and by the way, your a NewBie, just thank cf and fuc*OFF :D

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

this is not fare! make it rated!

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

Does the model solution fail on this test by any chance?

5
1 2 3 4 5

Ah, so this is the countertest?

I was a bit confused since things change a lot as the game progresses. During the contest, the first thing I came up with was apparently the same as the model solution, but I also had this countertest and got stumped and gave up. I proceeded to pass pretests on D and C (with some trouble).

I guess I still haven't solved D in an official contest then... I still learned some stuff I guess :D. Lessons: deques and queues have a much larger memory overhead than vectors. return printf("1\n") works locally but not on CF. Sometimes things that seem too hard actually are XD

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

    What would the optimal solution for both players be? I'm not sure what they mean by "optimal" by both players.

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

      The solution here should be 1.

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

      Answer is presumably 1; the first player will remove 5 (or 1, whatever), then whatever the second player removes the first player will be able to get a result of 1 (e.g. if the second guy chooses 2, then the first guy would choose 1). Similar thing with the case I was trying to figure out how to deal with: 

      5
1 3 6 7 15

      The point being that both players have a ton of on-the-fly adjustments they can make.

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

    Thst is the hack!

    Congratulation !

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

    What is special about this case? I couldn't come up with any solution (not even remotely close), so I'm not really sure.

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

    Are you using a set by any chance?

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

    So if this is actually the counterexample then I guess the offical solution was saying "ok, we can let the first guy do all his turns first" (i.e. you want max(arr[n-1-turns+i]-arr[i]) where turns=ceil((n-2)/2) is the number of turns the first guy gets) or something similar.

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

    If it's in main(), you can use return printf("1\n"), 0;

    By convention, main() should return zero on success.

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

      Yeah I know that. I always do it with the 0 but today I forgot and it still worked locally -> learned to check that.

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

Were all the solutions of participants incorrect, too?

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

    Maybe solutions which passed pretests are false, but solutions which fails pretest are true? :D:D

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

a black day for codeforces ...... (mabye brown)

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

I assume we are free to discuss solutions if it is unrated.

How to find the count of integers which start with b[i] and are divisable by a[i] in some range [a[i],pow(10,k + 1) -1] ? Anyone can help here please??? :)

I assume we shouldn't brute force, there should be an elegant solution to this.

My idea for B is : count possible numbers for each of the n/k positions. then answer is the product of the (1 + count of possible numbers) for 1 <= n/k

A tip for the problem setter : It's better to say "If ... start 'WITH' instead of 'FROM'

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

    Find lower bound -> 'from' if divisible, from + (x — from % x) if not. Then find upper bound which is simply (to / x) * x. Now the number of divisors is (to — from) / x + 1

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

Another terribly contest! The idea of tasks ( first four tasks are great ), but guys:

  1. The tasks are pretty hard for div 2 round.

  2. The fourth task again some physics ?!

  3. Bug in the third task, I am really interested what it is. I can not understand that two purple, one orange and two red coders didn't find mistake in the problem.

  4. Why I can not hack solutions with smaller matrix size than it is needed in the first task( many users put matrix [100][100] instead of [100][200])?

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

    4th task is not physics, point on circle can be described in terms of coordinates of circle-centre and angle (and angle depends only on time)

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

    the same at 4

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

    >physics

    I don't think this word means what you think it means. A cycloid is a mathemathical curve; while I see a lot of analogies with physics, they didn't help at all and I solved it as a purely programming problem.

    You're given an implicit relation between something proportional to the answer, t (the answer is tV / R) and some parameter p which you can freely change: φ(t, p) = R(t + sin(p) - sin(p + t)) - L = 0. Find the minimum t.

    Binary-search. Since t - sin(p + t) is non-decreasing in t for any p, if φ(t0, p) ≥ 0 for some p, then the min. t is at most t0; otherwise, it's more than t0. For fixed t0, sin(p) - sin(p + t0) attains all values in the range , which makes the binary search condition easy to check.

    Where's the physics? Though I agree that it's too hard for div1 B.

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

      Problems involving rotational motion like these arise a lot more in physics than in pure mathematics or computer science, and I believe that is where the confusion may have stemmed from.

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

      Ok. I can agree with you. I didn't have full solution for the fourth task and you are right.

      The previous round had similar idea for the fourth task. I think physics task, which can be solved by math (geometry) and binary search. For me previous one was more interested.

      BTW:

      Did anyone has right solution for the C d2 (A d1) task ?

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

    allllekssssa Same happened with me.Someone had made an array of size[107][107]. So I gave n=100,m=100 and gave all the values as 1. Surprisingly, it gave Correct Answer which was 10000.I wrote that contestant's solution on my machine and gave the same input but a miracle happened. It gave 10000 here too. I failed to understand the sorcery:P. So as a last ditch, I put some 0's in between instead of all 1's. The correct answer was 9998 but his program showed 10000. Hacked it with this input and succeeded. But curious to know, what had happened the first time? Shouldn't the code Segfault?

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

      I thought the same. I am not big expert for C++, but I think that program use some extra memory and change size of array.

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

spent one hour on the C --> :C

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

When you realize that your rating will decrease, but then contest become unrated

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

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

I dont remember last time i was able to solve C (Since last 3 contest).

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

Please don't make this round unrated , for the first time i solved div1 D during contest

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

    please make this round unrated because div1D gave MLE on #59

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

Shouldn't contestants decide whether or not they want this round rated? If there was a poll I think many would still prefer for it to be rated. And if more than 80% (or different fraction) of people want it to be rated then it would be. However, now it's too late since probably many have stopped writing and left after announcement.

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

    NOPE, CAUSE ITS SURE GOING TO BE 50-50

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

      Well, at least then you would end up with a feeling that you made right decision by making it unrated contest.

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

This must be upsetting for coordinators and problem setter too.I think we should support them and have a little faith in them. :)

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

    Agreed, the number of posts saying "I hate you" is too much. Mistakes are bound to happen anywhere, and today's one incorrect model solution is small compared to the thousands of interesting problems that Codeforces has given us.

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

      I can only imagine how much effort it took him to write 8 problems and then only to see the contest to go in vain. Announcing it unrated must have hurt him more than anyone!! If not anything then he gave community 8 new problems to solve!! So less hate comments please

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

How to solve div2 B ?

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

    Wait.. :)

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

    for each a_i count how many numbers are divisible by a_i in the rang 0 to 10^k-1 . Then find how many of these numbers fall in the range of k-digit numbers starting with b_i . subtract it from previously counted numbers. The multiplications of these numbers for all i is the answer (mod 10^9+7) .

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

      Nice explanation. b_i = 0 was a exception.

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

        I didn't do any extra checking for b_i=0 . I passed the system test. What will be the exception, could you tell?

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

          It depends on method of finding numbers that fall in the range of k-digit numbers starting with b_i. In my method it will give WA for b_i = 0.

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

    Compute the number of possibilities for the i-th group of digits, then the final result is the product of all those possibilities.

    To compute the number of possibilities for the i-th group of digits, you can count the number of integers j so that 0 <= j*a_i < b_i*10^(k-1) and add the number of integers j so that (1+b_i)*10^(k-1) <= j*a_i < 10^k.

    I hope this is clear :)

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

so there I was... having solved B (hopefully) , thinking about how I may finally have a 1500+ rating or maybe even get a change of color and bla bla .... suddenly this notification -_-

I am never gonna get a good rating :'(

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

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

    when do you people have time to make this stuff?

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

I also wanted to point out that statement + input of Div1C is horrible. Seriously, WHY is the input given in rectangle? Combined with some vector explanation which I couldn't understand, I just stared at the problem statement for about 30 minutes.

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

How unlucky can a person be?if you want to find the answer,it's enough to know who is fsps60312.I didn't see anyone more unlucky than him/her.

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

what is the hack for div1 A?

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

I'm still confused by problem C. Is it asking 'given n points, remove k of them and make the smallest rectangle which encloses them'? Why are the magnets described as rectangles, then?

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

Can you please explain in a detailed way what modeled solution was and why it's wrong? Because I was really sure about my solution for Div1A.

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

    Can you describe your solution?

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

      I guess everybody printed the minimum value of a[i + N / 2] — a[i] in sorted order :))I'm not sure at all about this solution but I hate the fact that in the latest contests div1A is much harder than some other problem or div1B is very strange and mathemtics problem. D was pretty ok, C also(even though that the task description was very ambiguous

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

        Consider the follow case:

        5
1 2 3 4 5

        Printing out a[i + N / 2] - a[i] will get wrong as the answer should be 1 instead of 2.

        The first step is to ban 5, and if the second ban is 2 (or 3), just ban 1 (or 4). And it is easy to see that banning 1 or 4 in the second ban will get the result of 1 as well. (reverse the banning if the first ban is 1)

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

        I got with a greedy/bruteForce solution, after you sort the set, in the optimal game the first player will move just in corner sides. So he with (n — 1)/2 turns needs to maximize some distance from the preffix set and from its suffix, the remainder distance after to maximize will be the answer.

        code: linkYour text to link here... Does any one have a counter example of this??

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

          Same as the case mentioned above(?)

          Input this case to your solution gives 2 while the answer should be 1:

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

            What about this one http://pastebin.com/fmV6DTvw ? I didn't manage to submit during the round because it disappeared after some time.

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

              In the case:

              5
1 7 100 130 131

              your program gives 31 while the answer should be 6? I wrote this solution in time complexity of O(n!) and this should be correct.

              The possible first bans will give the following results: (so the first guy should ban 100)

              1: 31 (as the second guy should ban 130)

              7: 31 (as the second guy should ban 130)

              100: 6 (as the second guy should ban 130)

              130: 31 (as the second guy should ban 7)

              131: 30 (as the second guy should ban 7)

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

How to solve problem D?

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

    If the wheel moves n meters then the pin moves n meters around the circle. Reduce this movement to an angle alfa between 0 and 180 degrees. this is how much the pin moves from start to finish. You want to maximize the distance in the x-axis made by this angle. This turns out to be 2*(alfa/2)*r. So the answer is tentatively n-2*(alfa/2)*r divided by speed. But notice that this implies we moved less than n meters, so alfa is actually smaller than before. Just plug in the new values and do the same process. If you do this enough times you will be really close the the real answer.

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

      Nevermind, that won't work. It times out on test 3. I found a new method with binary six that gets me all the way to test 8, but then it becomes unable to reach sufficient precision.

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

    Didn't have the time to pass send to the pretests but this works at least for test 1 : I used the equation of a cycloid. x(t)=r*(v*t/r — sin(v*t/r)) Then I use ternary search on d between 0 and r*pi with the start at x=d and the finish at s=d+(f-s).

    To compute the function to minimize (tfi-tsi), I have a solver that uses binary search.

    UPD : sorry, WA 4, not precise enough apprently, maybe its just a wrong implementation I don't know.

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

:/

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

Give me back my up vote :/

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

    come and get it! (بیا بگیرش)!

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

      wait... I'll come for you tonight ;)

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

just a bad contest...

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

    why do you write comments in your stupid language when every one here are from different nationalities!!!

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

      do not be rude.

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

      This comment has been deleted cause of technical reasons :/

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

      You are stupid more.
      You can be more polite.

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

      he is stupid for doing that but you cant say any thing you want to this language

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

    Unfortunately, we are too tell, that there was a mistake in a model solution for problem C. We will remove the problem from the round and the round will be UNRATED. We sincerely apologize for this happening.

    UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED UNRATED

    do you see UNRATED?

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

How to solve problem Div1 D (REQ)? There are 168 primes up to 1e3.
There are 78498 primes up to 1e6.
For 168 primes we can build Segmet Tree. But what do for others?

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

    I have N * sqrt (N) * some constant around 7(maximum number of primes in the decomposition of a number smaller than 10 ^ 6)

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

      does it run in time limit?

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

        According to his submission history, his solution ran in 2979 ms (barely below the 3s limit). I implemented the same thing (but with more overhead since I used prewritten code) and received TLE on pretest 9 (test 30, after some optimizations).

        There was an announcement in the beginning of the contest about the time limit being changed (presumably increased) to 3 seconds, but I'm still unsure about whether this solution was intended to pass. I think the time limit should either have been stricter (to avoid these solutions) or more tolerant (to make optimization of constant factors unnecessary).

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

          I just spent 30mins optimizing my solution and it finally passed. I had to change my factorization from O(sqrtU) to O(number - of - primes - below - sqrtU) which is just ridiculous. My guess is that constant optimizations like these weren't intended, and the time limit is just still too strict.

          UPD: Maybe we were supposed to factorize numbers in O(logU) using smallest prime table, like TimonKnigge suggested. That seems more reasonable.

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

            I actually precomputed the first prime factor and the next divisor of each number in times and O(U), respectively, but nonetheless received TLE on test 30.

            I won't try to optimize this solution since I now know that a better one exists, but I guess optimizing my implementation of Mo's algorithm would make it pass, too.

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

              My theory was that the segment tree solution (which I referred to as "my solution", I wasn't specific enough, my bad) in pair with first prime factor optimization is the intended solution and shouldn't ever TLE.

              Using prime factor optimization on Mo's (like you did) proves nothing since the dominant complexity is still . On the other hand, using it on the segment tree solution removes the square root factor completely.

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

                Oh, I see that now, sorry.

                I only commented about precomputing the next divisor (as opposed to repeatedly computing it every time), though, because it would have slightly improved the complexity from to , where p(x) ≤ 7 is the number of prime factors in x — and this seemed to be important for geniucos's Mo-based solution to pass. Of course, the specific amount of time spent during precomputation doesn't really matter, since the bottleneck lies elsewhere.

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

        my solution didn't pass system test with such complexity

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

          I had 2979 ms out of 3000=))))Try to optimize small stuff

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

      Good =)
      What did you do?

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

    Mine is MO's algorithm + modular inverse + the fact that:

    phi(x) = x * P(1 — 1/div) -> where div is each unique divisor and P() is product.

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

    Note that phi(range)=prod(range)*{(p-1)/p for all p such that p divides at least one number in the range}. This is like DQUERY on spoj, since we want to know if a prime occurs 0, or >0 times. Use a BIT with multiplication. If sort the queries offline, and sweep over the left endpoint l, and for each prime multiply a[i]*(p-1)/p where i is the first occurrence of p>=l, we can solve the problem in

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

    Note: where pi are the prime divisors of n. I stored the ai in a segment tree so I could query their product quickly.

    Next, notice that each number up to 1e6 has much less than primefactors, which is about 20. So, for each ai, store its prime divisors, and for each prime divisor, store the next number to the left that also has this prime divisor. Then, for each number ai that has a prime divisor p such that ai is the first number with prime factor p, multiply segmenttree[i] with (p - 1) * p - 1.

    Then sort all queries by left end points in increasing order, and simply query the segment tree for the answer, and whenever the left end point leaves some position i, for each prime factor p of ai, find the next occurrence of p, say position j > i, and multiply segmenttree[j] with (p - 1) * p - 1.

    Complexity: calculating the smallest prime divisor of all numbers upto 1e6 is for U the upperbound on the ai, then factoring each number and maintaining the next occurence of each prime is , sorting all queries is O(Q) (for each position you can just store all queries with a left end point on that position), and lastly, updating the segment tree for each left end point is , resulting in the beautiful complexity:

    Accepted submission: 14153688

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

    my persistent segtree gave MLE on #59 and MO's algo gave TLE on #30 , idk what should i do

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

.

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

I am curious about the solution of Div2.C = = .I think lots of time , but still didn't come up with a good key.

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

"there was a mistake in a model solution for problem C."

Was the problem solvable and only the judge's solution was wrong or was there a mistake in the problem statement making it unsolvable?

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

    no one knows..

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

      I saw some people had solved it before it was removed from the Standings, so they might know whether the problem statement was ok or not.

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

why this greedy wont work for problem c? simply sorting the points...remove the corner points,by finding the minimum value of a[i+rem]-a[i] for i=0..n-1-rem, where rem=n-n/2-n%2+1

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

>mfw WA on pretest 4 on div1C

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

I couldn't submit anything last 20 minutes. It said page was blocked. You should have just let us keep writing the contest, if you want to make it unrated after the contest that's fine, but not being able to submit code makes me sad.

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

That moment when you spend one hour on D, succeed the test after finding out a stupid mistake, and it is 30 seconds too late to submit.

At least I did my first ternary search :)

UPD : happy to see a failure ont test 4 anyways

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

Lesson learnt: NEVER EVER use inbuilt pow function in codeforces. It behaves weirdly.

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

    Can you show us why?

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

      Sure:

      Accepted: http://codeforces.me/contest/595/submission/14150524

      Pretests Fail: http://codeforces.me/contest/595/submission/14150122

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

        Huh. I've never seen that before, my submission got through fine using pow. Then again, I do have four WAs on Div. 2 B.

        I'll be using a custom function from now on. C++ is weird. Thanks!

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

          obviously. Pow is for float numbers. If you use it for integral values they got casted to float type and you get precision errors.

          P.S. It has nothing weird with codeforces, go on and see the docs on C / C++.

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

          I think its because of precision issues with floating point numbers. pow is a floating point function so such issues happen. Eg: pow(21, 14) gives me 3243919932521508680

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

            use pow(21.0,14) always that you want calculate in C++ a^b write pow(a.0,b)

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

              Emm, seems to not work correctly on my computer, 

                  long long int a = pow(21.0, 14);
    cout << a;

              Still the same answer

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

          Use powl() instead and see if the problem still persists ?

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

    The same happened to me. But you were smarter and confident about your algorithm and figured out the problem.

    I thought "Maybe the second pretest is not the given example and my algorithm is wrong". Two lessons learned in my case.

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

Like this if you gave up on the round because problem A seemed too hard.

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

    Like this if you're too dumb to realize A is too hard and got pretests passed with ten-lines solution.

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

    Just skipped it and solve other problems

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

Will this round announcement get fewer upvotes than the last round? (Last round has 120 upvotes currently)

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

Actully 4th task is not about physics. A model of moving can be described like this: let start point be ( - b, 0), start be (0, 0). Start angle of point of circle is a (that's the angle between line centre-point, and line Ox). One can see, that if we want to get finish in time tres, than we should take such a, that

 - b + v * tres + cos(a - v * t / r) ≥ f - s, 

where b = r * cos(a). It can be done through some mathematical analys: inequality is equivalent to

v * tres + r * (cos(a) * (cos(tv / r) - 1) - sin(a) * sin(tv / r)) ≥ f - s

Using derivative, we can get, that

after this we simply use binary search on $t$. By problem condition, a should be in range [0, 2π], but I haven't proved it. Anyway, this solution passed pretests, so it's not far from truth.

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

    Yeah, I know that you can derive it yourself. But derive it yourself by pen and pencil you will need at least 10-15 minutes(of course if you know derivative,how to compute arc length and cosines). The person who will Google "trajectory of point on wheel of bicycle) it will lead him to cycloid(wiki) where all your formulas are written.\n Since it is 80% of problem I think it is unfair.

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

      We even don't need to use a derivative for finding max(a * cos(φ) + b * sin(φ)). One can see, that

      so there is an $\alpha$, for which

      so, $\sqrt{a^{2} + b^{2}}$ is maximum (and, obviously, it can be reached)

      and something wrong with tex on CF, I don't know why my message wasn't parsed normally

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

        You mistyped the last bracket: "b^{2}{" instead of "b^{2}}".

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

    Could someone please check why the above solution gives WA for Div-2D. I have done the same thing mentioned in this comment but I'm getting WA on test case 8. Link to my submission.

    Thank you

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

Thank God.. It's unrated :)

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

No worry for rating and Failed System test.

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

Hey guys , the wrong model solution caused a single round to be unrated, didn't cause the world war III to start!!!

I believe GlebsHP did his best to prepare the round, but he is after all a human, and no human is free from mistakes.

furthermore, this is not the first round which is made unrated because of wrong model solution in codeforces, it happened before with former coordinators, even in topcoder same situation happened before, please don't mix between what happened today and GlebsHP being a new coordinator.

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

    "even in topcoder." So you're saying that topcoder is recognized as a better platform than Codeforces.

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

    I agree with you! GlebsHP has my support (if it is important to someone :D). I only worry about really bad estimation for level of tasks.

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

    when you are going to set a contest you have to check it 2 or 3 times at least to dont have this kind of mistakes if you cant or wont dont do this at all this isnt ww3 but its not that simple

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

Div2 B using c++ pow -> WA Changed pow to own power function -> AC

DDDDD:

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

    The pow func in C++ sometimes cause trouble because it assumes numbers as floats and the return value gets wrong sometimes while working with ints in code

    Same thing happened to me previously and left me in confusion :]

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

      It's so annoying -.-

      Worst of all, this isn't the first time this happens to me. I never learn :D

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

http://codeforces.me/contest/595/submission/14159310 Why does this give me compilation error?

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

    It compiles perfectly in my computer with g++

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

      How is it possible? M_PI came from sky or what? :P

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

        I don't know, I only copied the code and compiled without errors or warnings. It seems that some compilers are including M_PI while other aren't. I've never used it...

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

        Visual Studio 2013 knows M_PI if u were included cmath

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

    I saw some cases where M_PI is not defined, it could be a reason

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

Yes, I too feel so he should be back!!

Making Div2 ocassionally hard is a good practice indeed !! Adding maths problem reduces my fear from maths problems though I binary searched my answer :P !

But when I see this regularly I loose interest !

That is why ZLOBOBER was good... But respecting the coordinator there might be some reasons as to why rounds these days are becoming hard!

But I think my rank only depends on how fast I code Problem B . If I cannot I get a bad rank! Only a few people solve C making the ranks totally based on speed and in my opinion it should be balanced on Speed and Problem Solving!

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

    and more problem solving. in this contest specifically every one solved b and no one solved c(actually d) and for me(my net was going crazy) it was bad lost.

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

Is Div.1 A solvable for the given constraints?

Edit:

I was only able to think of greedy solution for even values of n:

A will always remove a position situated on the boundary of the remaining array.

Now, whenever B moves, he can select the middle element from the remaining array, to ensure that he can select consecutive elements.

So, answer is min{x[i+n/2]-x[i]}.

will this give correct answer for n=even?

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

    Yes. Let P(x,n)=min{x[i+n/2]-x[i]}. It is easy to show that P is not greater than answer — if the warrior doesn't care what archer does and delete all a[j] for j < i or j > i+n/2, the result will not greater than x[i+n/2]-x[i].

    Let's prove P is not smaller than answer. After the warrior take turn, the archer can make P not smaller than it was before warrior's turn, by deleting the median of x.

    For example: if x is 1 2 3 4 5 6, initial P will be min(4-1,5-2,6-3). If warrior delete 1, archer will delete 4, and x will be 2 3 5 6, P will be min(5-2,6-3), which is not smaller than initial P. If warrior delete 4, archer will delete 3, and x will be 1 2 5 6, P will be min(5-1,6-2).

    Archer can prevent P from being smaller, and P for n=2 is answer, so initial P is (not smaller than) answer.

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

      thanks for your explanation :)

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

      Any ideas about why the statement "It is easy to show that P is not greater than answer" doesn't hold for n=odd?

      I don't see how you implied this statement from n=even.

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

I make mistakes(in fact, I just did, for all the two hours), why shouldn't you? :)

If there's a probability for wrong model solutions of 0.01% for every round, the probability for it to ever happen in all the 330 rounds is 1-(1-0.0001)^330 ~= 3.25%

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

    I have an experience in preparing a contest, and 0.01% seems to be too small const) It's closer to 1 - 5%, as for me.

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

The problems are quite interesting and the difficulty is fine. What a pity it is unrated. BTW, can anyone show me how to solve Div2 C/Div1 A? Even the algorithm for the wrong model is fine. I never know how to solve game theory problem

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

    For warrior, I was removing first or last element (from remaining set), for archer second or second last element — depending on gap sizes at front & back. But I couldn't solve ties when front & back gaps were equal (it would require to iterate through all existing elements, to resolve ties), was getting WA on 6th pretest.

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

    If n is even, min(a[i+n/2]-a[i] for i to 0~n/2-1) is the answer.

    If n is odd, min(max(min(a[i+(n+1)/2]-a[j],a[j]-a[i]) for j to i+1~i+(n+1)/2) for i to 0~(n-3)/2) is the answer.

    It can be proven by mathematical induction.

    EDIT: Sorry, my odd solution was wrong too.

    Code

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

      How did you arrive at the result for n=odd? Did you try out for small cases like n=5,7,9 etc. and notice a pattern?

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

        I tried to apply same mathematical induction to odd-case, but it was wrong :(

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

          What is the counter test?

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

            5

            1 2 12 22 23

            if warrior deletes 12, answer will be 1.

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

why did these past contests was ********

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

    these past contests WAS?? WAS!!!!!!!!!!!!!

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

      i typed half of this comment 10 minutes after the other half :)

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

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

BTW this one looks very similar to today's A: 377C - Captains Mode

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

positive point of unrated contests!

you don't have to wait for rating changes! :D

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

though Div 2 C got removed, could greedy be one of the approaches to it? like first sort the positions and then player 1 would try to delete positions from the end while player 2 would start from the middle?

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

What was the greedy approach for DIV2 C even if it was incorrect? I was not even able to get an answer for the second pretest? Please help !!

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

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

When will the editorial be published?

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

PLEASE HELP!!!

This is my code for DIV2 B https://ideone.com/eZXkMx

I am simply getting WA in test 2 where as it gives the right answer!!! And CF shows it gives WA! Why???

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

    Casting double value of power to integer and expecting correct conversion? What about values as 999.999999, wouldn't it evaluate to int value 999?

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

      But why it gives correct result in Codeblocks and ideone?

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

        Because it's a different compiler, different cpu or different OS? Never cast floating values to integers, if you must — add 0.5 before casting. But in this case — you can just multiply by 10 until you get that power.

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

        i had the same problem but in codeblocks gives wrong answer for me o_O

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

    Yup, I had the same problem. Write your own function:

    int exp (int b, int p) {
   if (p == 0) {
      return 1;
   } else if (p % 2 == 1) {
      return b * exp(b * b, p >> 1);
   } else { // if (p % 2 == 0)
      return exp(b * b, p >> 1);
   }
}
    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

danilka.pro please elaborate on what the issue with Div2C have been.

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

I think it is no need to set too many queries in one test case in div2 Problem D. :P Because of this, I got TLE with my code using cin/cout. Anyway, it is lucky that this round unrated... haha

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

Div1 D looks too easy for that slot, Div1 B was too hard for that slot.

And Div1 A was impossible for the slot, apparently :P What was the statement about?

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

    Binary search is too hard for Div1 B?

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

      Judging by your 18 submissions to 549H — Degenerate Matrix, I'd say binary search is quite complicated :D

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

When solutions for problems will be published ? And when rating will be updated ?

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

    This round is unrated, rating won't be updated

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

    May be your Rating would be updated after the next CF round (if you participate!) ;) However, FYI, today's round is unrated.

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

Hey guys, The codeforces says my code is failing on pretest. I check same pretest on my machine it passes. This is second time it is happening with me. Please help me why is this happening.

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

    Don't use the pow function, it behaves incorrectly on codeforces.

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

Please less math problems next time. Math problems are cool, but not when they're the majority of the problems. Coding is more about algorithms than math.

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

Is that so hard, to always include maxtests in pretests? I have passed pretests with my where k is max number of distinct prime factors, but it turned out that it got TLE on systests, because constant factor was too big. After some optimizations it passed, but this is one of main goals of pretests to prevent TLEs of solutions with should pass (OK, I agree that this was a bit higher complexity than intended one, however argument still stands).

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

    I wonder why downvoting Swistakk is so trendy. I totally agree with him on this, my solution got TLE on systest 30, while after contest I changed barely anything and fit in half of time limit. I simply decided not to optimize everything, as they say, who doesn't risk doesn't drink champagne (or, in polish it's like "who doesn't risk doesn't eat"). In this problem there is a plenty room for improving time performance and I really don't understand decision of not giving at least one maxtest in the pretests.

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

Is it possible to solve div1A/div2C in this way: Binary search the answer, and check how many points need to be banned by the archer.

I submitted it in the contest but got a WA on pretest. However, it seems that this solution goes well for those countertest given so far.

Here is my code.

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

    I thought the answer of

    6
0 1 2 5 6 7

    is 5

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

      Yes, you are right.

      Maybe there are different solutions to even and odd n.

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

        I can see why your solution serves as a lower bound for odd n, but am having a hard time seeing that it is also an upper bound. Do you have a proof for upper bound?

        P.S. I couldn't find a countertest.

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

Could anyone post Div1A problemset here please?

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

I solved the div2 D in pretest,but FST on test12 and get a Time Limit Exceed. I tried binary search and Newton iteration but not it didn't work. Could anybody help me? This is my code

#include <bits/stdc++.h>
using namespace std;
int n,s,t,r,v;
const double pi=acos(-1.0);
double C;
double g(double L)
{
    double s=0.5*L,t;
    while(1)
    {
        t=s-(s+2*r*sin(s/(2*r))-L)/(1+cos(s/(2*r)));
        if(fabs(s-t)<1e-6)return t;
        s=t;
    }
}
double f(double len)
{
    double ll=floor(len/C)*C;
    return (ll+g(len-ll))/v;
}
int main()
{
    int i,j,k;
    scanf("%d%d%d",&n,&r,&v);
    C=2*pi*r;
    while(n--)
    {
        scanf("%d%d",&s,&t);
        printf("%.15lf\n",f(t-s));
    }
    return 0;
}
→ Reply
»
9 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Its feels kind of sad to me how this post got downvoted from >250 votes to 80 at the moment. Upvotes don't matter much in my opinion, but its downright disheartening to see people ignoring the kind of effort round writers put in preparing rounds. CF doesn't pay that really good and if someone has chosen to prepare a round is because he wants to contribute to the community.

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

my idea for problem B()--- lets take sample test #1--

n = 6, k = 2; what i will do is-

count all 2 digit numbers divisible by 38 ---

how?

lets take a look--

the last 2 digit number will be 99 or pwr(10,k)-1 and the last one digit number will be 9 or pwr(10,k-1)-1, so now what i will do?

i will divide (pwr(10,k)-1)/38 lets take result as x and i will divide (pwr(10,k-1)-1)/38 lets take result as x1 so (x-x1) will give me number of 2 digit numbers divisible by 38

but wait there is another condition i shud take care of that number shudn't start with b[i] or 7 so lets do it--- now there will be pwr(10,k-1) numbers starting with 7 but if i iterate through each and every number i wud TLE so what i'll do is i will take first number -- b[i]*pwr(10,k-1) and i will take last number ((b[i]+1)*pwr(10,k-1))-1 divide both by 38 and lets take result as x2 & x3 respectively, so numbers starting with 7 and divisible by 38 will be (x3-x2) ,substracting this result from (x-x1) will give me the desired result , now i will do same thing for all a[i]'s and b[i]'s and i will keep on taking product of each i's and finally output

point me if i am wrong anywhere

P.S. x,x1,x2,x3 are integer variables and u need to consider the 0 case too

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

    You dont have to subtract the k-1 digit numbers, because they count as numbers that start with 0. Also take note that "0000000" is also a valid number and is divisible by everything.

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

Leave the mistake, Where is the Editorial?

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

My idea for Div1 A: (WA 6 during the contest)

Examine two cases:

  1. n is even. Suppose both players have played their optimal game. Suppose that in the k-th move A picked xik and B then picked xik + 1. Group these moves into pairs (xik, xik + 1). Let lk = xik + 1 - xik. Note that in each step A can deny one of the pairs with his move. This means that B cannot get an interval larger than min lk with such a pair distribution. He is able to get it, too: when A denies a pair, B denies the second element of the same pair. Thus one pair will remain in the end of the game. Hence an optimal strategy for B is to distribute the xi-s into pairs before the start in such a way that min lk is maximal possible. It is not hard to prove that the distribution is optimal (if xi-s are sorted).

  2. n is odd. A similar argument works for A. Only now A makes the first move. Thus, A should deny one element and then devise a distribution into pairs (xik, xik + 1) such that max lk is minimal possible. Because after the first move, B denies an interval by his move. Similarly to the even case, A picks the second element of the pair after the move of B. Thus one interval remains. It is not hard to prove that after A makes the first move, the optimal distribution is (x2i - 1, x2i) (if xi-s are sorted and the one picked by A is excluded). Hence we should find the best element for A to pick in the first move. It is also easy to prove that this element should be one of the x2i - 1 (with an odd index). For this, we can calculate two prefix maximum arrays, say maxl[] and maxr[]. The array maxl[2i] stores the maximum length of the interval among the first 2i elements, if x1, x2, ..., x2i are distributed to the pairs as described. Similarly for maxr[2i], only it stores the maximum of the right side. The answer to the problem then is min(max(maxl[2i - 1], maxr[2i + 1])).

Can this be correct? Code here.

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

    The idea is interesting, but this is also incorrect: in the odd case, sticking to pairs may not be the best strategy of A: to mix pairs but exclude the worst one may yield smaller answer.

    Counterexample is this:

    7
1 2 3 4 50 125 140

    Answer is 3, not 15. (A has 3 turns, and he excludes 50, 125, 140)

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

I submitted a code for div1A and got WA on pretest 6. I am wondering if this solution is actually correct. I think the answer is the maximum of the minimum distance between the rest points after deleting exactly floor((m-2)/2) points.

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

      Oooops......So it seems not to work when n is even? lol

      How about when n is odd? imho it must work when n = 3, and is likely to work when n = 5.

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

        I have a bruteforce solution, and it seems that your solution gives correct answers for small odd n. (I tried it with n <= 9, and it passed more than 100 cases on my computer.)

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

          100 cases? So few? In TCO final 2015 that just finished, Petr's 550 solution passed his 1000 randomly generated cases. He had to generate 9000 more tests, and the code only failed on "1 or 2 of them"

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

            I'm not saying it's correct because of that. After all I only checked the case when n <= 9, which is way smaller than the actual problem :)

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

Why I become third?

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

    Desactivate "show unofficial".

    Someone became second in unofficial mode.

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

brothers this was a good contests

→ Reply