mfv's blog

Experimental Educational Round: VolBIT Formulas Blitz
By mfv, history, 9 years ago, In English

Hello, Codeforces!

“Experimental Educational Round: VolBIT Formulas Blitz” will take place on February 18, 2016 at 18:00 MSK. This time the problemset is recommended for Div.2 participants.

The round will be unrated for all users and it will be held according to the standard ACM-ICPC rules. You will have 180 minutes (three hours) to solve 18 problems. There will be no open hacks phase after the round.

Our main target audience is beginners and Div. 2 members. All offered problems can be solved without conditional constructs and without loops. Only formulas are required. Assignments and functions can be used to reduce code duplication.

The topics of the problems are:

  • combinatorics
  • geometry
  • game theory
  • sequences
  • other

The round is created as a part of Vologda BIT event, also as part of this event “Contest programming from zero in Java” webinars were held devoted to the topics listed above. Recordings of the webinars are available on YouTube (in Russian).

The round was prepared by me, Fyodor Menshikov mfv, Igor Andrianov igand and Oleg Strekalovsky OSt. Special thanks to Maria Belova Delinur for bugfixing the English statements and of course to MikeMirzayanov for Codeforces platform and Polygon. Polygon made our checkers and tests for this contest better.

UPD: The editorial is complete.

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

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

18 problems in 3 hours !!!! this looks challenging (1 problem per 10 mins).. especially in these topics .. can't wait ;)

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

Сertainly, some common functions from standard math libraries can be used.

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

    Yes, particularly

    • sin, cos, tan, asin, acos, atan, PI
    • sqrt, pow, abs

    Also bitwise shifts can be a part of the formula. There will be no need to use long arithmetic such as BigInteger/BigDecimal in Java.

    Maximum required types are 64-bit integer and 64-bit floating point.

    Contestants are allowed to use conditions, loops, long arithmetic, etc, but we hope that these constructs will not help. :-)

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

Math ,, 1 problem per 10 mins ,, sorry i’m out

it is unrated

i’m in :v

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

As a beginner, I can't express how excited I'm for this round. This, for sure, is going to be a memorable experience. :)

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

No, registration required ?

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

    Registration will be open till the end of the contest.

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

It is good to see codeforces coming up with different types of contests. It really helps a lot.

→ Reply
»
9 years ago, # |
  Vote: I like it +58 Vote: I do not like it 
#include <cmath>
#include <google>
#include <wikipedia>
// ANY COMMENT?
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +89 Vote: I do not like it 
    #include <oeis.org>
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -29 Vote: I do not like it 
      #include <mathforces>

      //not Codeforces :)

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

      oeis.org may help in some problems but not required if you know combinatorics.

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

    We hope that Google and Wikipedia will not help. It is not easy to create good request when the problem statement is a legend, not in mathematical terms one.

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

    include

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

      it seems that Codeforces currently supports markdown. You may need to quote your include in a code block, or add a '\' in front of #, or it will regard your include as a title, and all we can see is just include.

      good example :

      solution A

      ```c++

      #include <stdio.h>

      ```

      solution B

      \#include <stdio.h>

      Choose either one will solve your problem.

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

The contest name should be : Fast as Ferrari !

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

I think this is a great idea, and I will certainly enjoy this contest. The only thing I regret is the absence of an open hacks phase after the round end, I think this could be a good oportunity to learn about reducing error, and how to write stable formulas when working with doubles.

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

What do they mean by "this contest is unrated"?

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

    Rating of the round participants will not change.

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

So ineresting!

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

Hope there will be short statements...

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

Will the problems be sorted from easiest to hardest?

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

    Somewhat. Different topics for different people have different difficulty, so it is impossible to sort a problemset from the easiest to the hardest.

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

Hope to have Some Nice, Short & Easy to Understandable Problem Statement .

Because A short & well understandable Problem Statement can make a sense of a Nice and Quick solutions .

It would be better if you set the Problems according to their Difficulty Order .

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

I want to mention about competition time. When the organizers set time 18:00 MSK, our local times shows 17:00 which is our end of the business day. I know there is no chance to set for every country, but I just want to tell you :( sad story.

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

Is there any way to get benefit from the Youtube's channel for non Russian speakers > ?

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

    Probably only if someone will volunteer to translate.

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

    If someone can make English subtitles for the videos, it could be of great help.

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

Currently I have my mid semester exams but I will take part in this contest ..

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

    Same here! 18,19 and 20, and all three codeforces round are one these dates. :D

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

Word "Education Round" without Edvard ... :)

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

    And word "Education" instead "Educational".

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

    I'll post the announcement of the Educational Round 8 soon :)

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

      great :) your awesome man...

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

So interesting for me,but per questions only 10mins hahahahahaha I don't think I have enough time to read and code these problems!

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

Would you please help me by giving some good tutorial link about sequence and combinatorics??

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

Hope that it is going to be a good 10 mins per problem contest filled with just import things from using the Wikipedia, google and OEIS library ;)

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

10 minutes per question

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

Никто не заметил, то что контест начинается 18 февраля в 18:00, 18 задач и дается 180 минут?

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

mfv Is only Java allowed or any other languages allowed in normal round are also allowed because tutorial videos was focused on Java?

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

    Any language is allowed.

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

Bannedaccount is a bot who is slowing queue.

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

Too many time :) More than hour before the end, but already 11 people solved everything.

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

    It was designed for div2, not for red ones.

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

      Not blaming anyone, just joking/showing off :) Actually in my opinion it will be very cool to have similar contest with div1 difficulty.

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

Got L accepted 20s to the end of the round

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

Solutions of all problems if anyone is interested

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

I think that the difficulty was perfect was such a contest. Somebody above said that there was too much time — because 11 people solved everything in two hours. In my opinion it was fine and the contest shouldn't be harder.

Problem Q (Pyramids) was funny for me. I calculated formulas for the first two pyramids and then I used the answer from sample to calculate the coefficient for the third pyramid. I guess it was intended but still very unusual.

WA in test #22 in E (Rectangle with hexagonal cells). Here I will complain a bit. For me, the main problem was to understand the problem. For more than one hour I thought that one cell has the center in point (0, 0). It wasn't true and my solution gave WA on #22. Standings show that I wasn't the only one, Organizers, in my opinion you shouldn't put a misleading drawing in the statement. Drawings were awesome in e.g. problems P and Q. But here, you gave drawing to one of two cases — the one showed in the sample. Why wasn't it in the sample explanation section? I know that in problem P a drawing was related to the sample too, but the number of points n was the main part of the problem there. But here, in E, the drawing suggested that particular arrangement of cells. For sure I'm biased because I couldn't get AC for much time. Does anybody agree with me or was everything ok there?

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

    Problemsetter's solutions use function with parameter n (3,4,5). It can be a part of the formula.

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

    From the results it looks like that a lot of people googled formula for Q. In other case it's hard to explain why Q has more AC than O (last one is way simpler IMHO).

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

      I faced to problem of preciion. Initialized points, assuming "center" of arrow as (0, 0), multiplication by rotate matrix and transposition. Still don't know where's fail

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

        I don't think it's precision issue. Looks like you need to change (c — a) to just c everywhere.

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

          My holy pretty f**cking stupid bad!!:D

          40 minutes couldn't understand my failure!)

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

            By the way, word of advice: use std::complex for 2D geometry. Makes thing that much simpler.

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

              Thanks for advise. Never used it.

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

      I did google for formula in Q. At first I tried with (1/3) for all (out of assumption, assuming from the formula of cone). Then when the answers did not match, I had to google.

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

    Why a drawing should describe all possible cases? It depicts one test.

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

      No, it doesn't have to cover all cases.

      Reading about hexagonal cells is very hard. Usually problems are much easier to understand and thus they don't require drawings. But here, drawing was crucial and likely almost all contestants used it to understand how coordinates work. It was in the main statement, not in the sample explanation. It wasn't said that it's the sample arrangement. So why shouldn't I assume that coordinates are like in the provided drawing?

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

        It should have been in sample explanation. Sorry.

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

          Still, only 1 issue in 18 problems. It was damn well prepared contest! Thanks.

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

    I looked at diagram and vaguely read the problem statement. Helped me avoid confusion for this problem.

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

    Wait... how come there is no cell centered in (0, 0)? There is a hole on the grid? It makes no sense to me.

    I am one of the people who can't get past test 22 and I'm pretty sure my solution is overflow-free.

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

      Apparently you could shift the whole "hexagon plane" a bit, so the centers are in cells like (1;0), (3;0) ... You should be oriented in which case you are by the input data, since it's apparently centers of cells only.

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

        I always feel cheated when I find out that a cruical part of the problem was hidden in the input format rather than the statement itself.

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

      There is no hole but it's possible that centers are in (1, 0), (0, 1), (2, 1), ( - 1, 0), etc. (instead of (0, 0), (1, 1), (2, 0), ...).

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

        Ok, thank you, now I get it, but I still don't see how could I have imagined that, at least from the English statement =p

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

    Totally agreeing on problem E with you. Took me 8 wrong submits and an hour to get it accepted, and I wouldn't have understood my mistake if I hadn't read your other comment. Not very nice to put misleading pictures especially when the statement wasn't clear enough, in my opinion.

    Most of the other problems were nicely done though.

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

    So according to you, there may be two arrangements for the hexagon? How can I get that from problem statement? I also got WA on 22 and not still understanding where the problem is . And if there are two arrangements which one should I produce output for?

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

      I believe input data is supposed to be centers of cells only, but I'm not sure since the statement is confusing. I got AC assuming that, though, after 8 unsuccessful submits.

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

        "input data is supposed to be centers of cells only" This can't be true. Otherwise, how will you construct the cells for input "0 0 2 1"? It could be true though, if we had additional restriction like "It is guaranteed that difference y2 - y1 is divisible by 2"

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

          "0 0 2 1" isn't valid. It was guaranteed that the given four numbers represent "the coordinates of the centers of two cells.". Yes, it implied that y2 - y1 is divisible by 2.

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

            Oh , now I get it. It's written in the input statement. I had given too much emphasis on the drawing and did not read other statements very well.

            Well, I agree that the statement could have been written a little better. But in the end, I think its my fault I didn't read the statement thoroughly. This should act as a reminder

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

          Well they just didn't have such input. After my previous comment I actually found it written in the input section — "...the coordinates of the centers of two cells."

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

            Now I can see it too. Thanks!

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

    Agree with you on E. Test case #22: 1 0 5 6 Expected result is 18.

    "Orthogonal coordinates system is set up so that ..." It seems there are 2 ways to set up such system: one with (0,0), another one with (0,1). (0,1)-way gives the answer 18, (0,0)-way gives the answer 17.

    Please correct me if I am wrong.

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

      My solution failed on that test too .

      centers could be shifted so it is not necessary that (0,0) is a center .

      (x1,y1) should be a center so you have to shift centers to achieve that.

      if(x1%2 != y1%2 ) x1++,x2++ ;

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

For all those failing 22nd test in E: You can't just calculate (x2 — x1) * (y2 — y1). It will overflow even if you work with signed 64-bit ints (as possible value is 2 * 10^9 * 2 * 10^9 = 4 * 10^18 > 2^63).

Disregard everything above, I was wrong.

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

    test 22 is not integer overflow. 2^63 > 8 * 10^18.

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

    It's not true that 4·1018 > 263. I think that the reason for WA was to assume that (0, 0) is center of some cell. It wasn't true. So, misunderstanding the statement.

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

    Actually 263 is about 9 * 1018 so I believe you're wrong.

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

The first problem could be rephrased just to: "Output 25".

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

    cap

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

    No, because people like me had fun with coding fast exponentiation.

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

One ER after another. Wowie!!!!

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

Can anyone help me in Problem B? I tried this code https://ideone.com/lgG2Tf I don't get it why my code is approximating the values?

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

    For big doubles, ouputting them via cout can lead to results like 1.23456e20. Try to do cout << setprecision(7) << fixed << answer;

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

Hi! I think most of the problems were obvious! Maybe it doesn't help me to improve much, but actually it was a good collection of implementation! Thank you for the contest but I think it could be a lot better. :)

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

    I don't mean to sound offensive but you solved 8/18, and the competition was anyway targeted at "beginners and Div. 2 members", so I think the problems' difficulty was fine, for their format at least.

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

First hour really tried to solve problems without loops and conditions. But N...

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

I strongly doubt if the problem E is right or its data. See the test data 22 , it is obvious that the answer is 17 which is shown as 18;

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

    The grid doesn't always look like the one in a drawing. Read the comments above.

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

great contest, i hope to see lots of this kind :)

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

Hi guys, you can now register for tomorrow's contest. This week is just beautiful. Contest after contest. :)

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

my solution for problem E failed on this test 1 0 5 6 .

jury's answer is 18 , my answer is 17 .

submission : 16183842 .

I can't count the 18 cells , does solution of judge gives wrong :\ ?

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

    Read Errichto's and others' comments above. The grid doesn't always look as the one in the picture.

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

      sorry , I didn't read the above comments .

      even during contest I didn't read the problem statement of this problem :v .

      I think I learned from this contest that I should read problem statement carefully next time :D

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

It was a great and interesting contest, except I falled into an unexcepted gotcha.

I'm a MS C# user.

I kept getting Wrong answer on test 1 on problem B. 16148846

I was totally confused and I put it aside. I passed it by rewriting my solution using Math.Pow.

After the contest, I checked the record, and I was surprised to find that the dot became comma!

OMG! I made a little change and I pass this one now. 16183742

The culture differences sometimes can drive people mad (well, and sad).

@MikeMirzayanov is there any way to fix this problem? Thanks a lot. (It's OK if C# users had to be careful for the following contests.)

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

I have submit problem E but in test 22 it turns out with WA. but when i saw test 22, i realized that my output number is correct and the correct output is 17 not 18

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

    Refer to the tons of comments about it above, especially Errichto's — the grid doesn't always look as the one in the picture.

    (I wonder how many times I'll have to respond with such comment today)

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

Are you going to write editorial?

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

    Yes. Probably in two parts. It is in the process.

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

      Thank you, I will really appreciate it. I am very keen on learning math.

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

Isn't it the most pythonic round ever hold? :)

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

The problem D — Hexagons! has the exactly same concept as SPOJ problem BEENUMS.

http://www.spoj.com/problems/BEENUMS/

It can directly be done by hit-n-trial(Approach 1). I have 2 interesting geometrical proofs/derivation for the end result.

2nd Approach —

3rd Approach -

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

    4th approach: find formula on OEIS.

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

      Or simply notice that the outer-layer of a hive of size N has 6 sides of length N, with 6 corner cells being in two sides and therefore you get 6*(N-1) for the outer layer in total. Then 6*1+6*2+6*3... is simply 6*(1+2+3...) = 6*(N*(N+1))/2 for a full hive (also add 1 for center cell).

      No need for anything complicated really.

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

        Sometimes, the journey teaches more than the end :) ! More so in an educational round :D ! That was the purpose of sharing the approaches. I myself had done it by pattern finding at the first place. And one more thing — in the SPOJ problem, the diagram is not given in the question — which becomes really painful to draw from the second layer onwards (12 hexagons, 18, etc).

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

I don't know what is wrong with my submission for problem B? It works absolutely fine on Ideone, but shows me WA here on test case 1 itself, with some "bizarre" output. I have absolutely no idea what is going on? Solution : http://codeforces.net/contest/630/submission/16187819

Any help will be much appreciated.

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

    What about casting to double in printf and using f instead of Lf?

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

      I tried to resubmit by doing this. The solution passed test case 1. But I still am not able to get as to why did I get such a strange output using Long Double?

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

Why does this fail?

http://codeforces.net/contest/630/submission/16189060

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

    Because you used vector of size 2 pushing two additional elements, which makes it vector of size 4 ;-)

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

How can i solve the problem "Q"? Please explain it. Thanks in advance.

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

In problem E, Test case 22: 1 0 5 6

Why is the answer 18?

According to the figure the count is coming out to be 17.

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

How to solve problem P ?

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

    The goal is to calculate the area of red polygon below (the left drawing below), and multiply it by n. So, finding coordinates of four red points will be enough.

    One point is in the middle of the circle. We can assume its coordinates are (0, 0). One point on the circle can be (0, r) and the neighbouring one must be rotated by angle .

    But how to find the last point, the one lying on the intersection of two diagonals? Maybe it can be done easier but I found diagonals and then computed the intersection of two lines. To find diagonals we must get coordinates of green points from the second drawing below. It can be done by rotating vector (0, r) by something like and . My submission: 16168847.

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

      I thought of that solution, but I thought there must be a simpler solution than making coordinates and finding intersection point of two segments, and it seems there's actually simpler solutions as some solutions are only cin then cout like this one 16190755

      thanks anyway

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

        Ok, I can prove it. It's not complicated to show that the red triangle below has angles α, 2α, π - 3α where . And side opposite to angle π - 3α has length r. We should use these values to calculate the area of triangle, and multiply it by 2n to get the answer.

        Let's consider any triangle with sides a, b, c and angles α, β, γ respectively (α opposite to a, β opposite to b, γ opposite to c). There are two very well known formulas:

        With them we can get:

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

      Another (harder) way is to compute area of the white sector-like things and then subtract from the area of the circle.

      → Reply