Tommyr7's blog

Codeforces Round #462
By Tommyr7, history, 7 years ago, In English

Hi, Codeforces! Happy Valentine's Day. And happy Lunar New Year!

I'm quite honored to invite you to Codeforces Round #462 which will take place at 15:05 MSK on 14 Feb and last for two hours.

The authors are quailty, skywalkert, visitWorld and me. This is our second round here.

The round couldn't have been realized without efforts of KAN and our testers: cyand1317, demon1999. Thanks for your help to the contest. Also, thank MikeMirzayanov for the fantastic Codeforces and Polygon platforms.

The contest will consist of five problems and it is rated for both division contestants.

The background of problems will be about Lunar New Year. (Yes... Not Valentine's Day...)

Hope to see you in the contest! Good luck and have fun, wish you a high rating!

We suggest that those who already have Valentine's Day plans should not participate... You can always upsolve a contest, but there is only one Valentine's Day ;)

The scoring distribution will be announced later.

See you in the contest!

UPD: The scoring distribution is:

div1: 500 — 750 — 1500 — 2250 — 2500

div2: 500 — 1000 — 1500 — 2000 — 2500

UPD2: Congratulations to the winners!

Division 1 :

  1. Um_nik (solved all problems!)
  2. Golovanov399
  3. geniucos
  4. fateice
  5. kriii

Division 2 :

  1. aabdelzaher
  2. WNG
  3. ZYF1023
  4. Kita_The_Dragon
  5. Kuroni

UPD3: The editorial is available now!

Thank you everyone!

Happy Valentine's Day and happy Lunar New Year!

See you next time!

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

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

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

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

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

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

Another Goodbye 2017

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

Thought of not participating at contests for a while but when i saw the nationality of the writers....

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

An interesting fact:

Feb/14/2018 is the 72th anniversary of the first computer ENIAC.

(So I'm going to spend the Valentine's Day with computers, codes and algorithms QAQ)

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

16 contests announced. I've never seen more on the future list, keep it like this codef

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

Good thing there is a contest on Valentine's day! Now I will be solving problems instead of watching porn :)

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

:D

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

I thought for a second to skip the contest and go out with my GF, but I realized that I don't have one (sad emojis ...)

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

I don't think your second warning is necessary -- we are on Codeforces, after all :-)

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

Hope there will not be combinatorics C like in last Tommyr7's last round

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

Finally! Something good on 14 feb. ;)

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

I hope this round will not like that. 1vldm8

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

Ahh,codeforces doing unpaid job for Bajrang dal :| (only indian can understand it)

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

I remember what happened in your last contest mate ;) I hope the mistakes are not repeated this time :P :P

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

Can you call it "Lunar New Year" instead of "Chinese New Year"? This festival is also meaningful for all East Asia countries (Vietnam, Nouth/South Korea, Japan, Taiwan, Hong Kong, ...), not just China. The background of the festival is based on the orbit of the moon (instead of the sun in the normal Julian calendar), then we call it "Lunar New Year". So if you change the phrase, you can support more programmers in Codeforces where there are so many programmers come from the East Asia countries. Thank you.

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

    But the blog poster knows the holiday as "Chinese New Year", and most people know what it is, so I don't see the point. You can call it "Lunar New Year" yourself if you want to.

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

    I'm really sorry about it and I have fixed it now. Thank you for pointing out!

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +91 Vote: I do not like it
    Not safe for political tryhards, especially during New Year
    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Taiwan and Hong Kong are not countries. Please correct it immediately.

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

    But it originates in china, at all. There is not any problems to call it Chinese New Year. You can see it clearly in the problem background.

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

'

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

Codeforc always gives new things in a new event. I want a girls friend from this contest for current event in this world :D :D :D :D

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

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

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

Again Tommyr7's Round. I like it!

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

That moment when the round organizer cares more about your romance life than competitive programming!!

This level is off the charts! LOL xD

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

I think up votes for this post raised so high cos the writer mentioned the line "We suggest that those who already have Valentine's Day plans should not participate... You can always upsolve a contest, but there is only one Valentine's Day ;)" :P ;LOL

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

Happy Lunar New Year and hope a good contest!

However,dear MikeMirzayanov, why I cannot open the problemset and history contests?

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

Obligatory comment: "Hope the problem statements are as short as the announcement"

0v0

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

lunar new year or.. Chinese new year....We need to stay with parents and extend family..The contest is very suitable for me to avoid doing some new year's work that day:)

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

lol coders having valentines :/

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

Codeforces is my actual girlfriend

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

This contest is my boyfriend so I hope it has a hard D problem

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

For chinese prople, maybe a New Year wish is better than a hign rating Butskhrikidze Happy_New_2024

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

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

Wow, that's fantastic, especially for the time of the contest.

Ahh, although for the Valentine's Day.

Gook luck, everyone. And best wishes for everyone in the New Year!

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

The contest coincides with Slovakia — Russia hockey match...

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

Fifteen words,fifteen words,fifteen words,fifteen words,fifteen words

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

You can easily find a girlfriend, but you can hardly find a cf contest early like this(a contest ends before my bed time).

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

A great contest for single dog(Just a joke) :P

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

Tommyr7 registered this contest... rank++...

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

maybe you can enjoy this round with your girlfriend:D

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

It is clashing with my dinner could you please shift-up contest more later ?)
UPD: Ok, I will eat KFC before contest, no problem )

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

14, 15 and 16th Feb 3 contests back to back.

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

Give me a good reason why I'm still at home on Valentine's day, because I want to attend Codeforces Round #462

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

Looking forward to screencasts of people participating in this contest. Preferably with their dates and a glass of wine.

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

Tommyr7, how to solve div2E?

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

    brute force

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

      Actually, there is a polynomial solution. Note that instead of generating the permutations we can just calculate the determinant of the matrix

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

Came here to make a comment on how I don't have a girlfriend and codeforces contest is one true love.

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

Maha Shivratri >= codeforces round > valentine's day :D

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

Next time, codeforces should do back to back 7 contests, starting from 8 to 14 Feb. So, we can stay motivated. :)

→ Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it -56 Vote: I do not like it

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

So, finally something for us(single people) :D

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

Happy Valentine's day, good coding for everyone at the contest Codeforces Round #462 :)

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

Two consecutive valentine day and also codeforces round on both days! :O (2017, 2018)

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

I'm grateful to CodeForces and the contest writers for giving me an opportunity to spend such an unforgettable Valentine's day with my beloved codes and algorithms.

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

Click friend standings and you will find who have no girl friend.

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

Woah, 5 contests in a single week! Awesome!!!

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

Valentines Present by Codeforces.

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

Four authors and all of them have different colours, interesting coincidence))

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it -34 Vote: I do not like it

...

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

btw, Valentine's day is every year :D

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

Pyaar ek dhokha hai, rating badha lo yehi mauka hai :P

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

Tommy?Tommy!

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

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

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

Are the problems shared between both the rounds? If yes, then Div 2 D would be easy than usual if its worth 750 for Div1 participants. Maybe XD

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it
TO EVERY PEOPLE IN CODEFORCES:

HAPPY VALENTINE'S DAY

HAPPY CHINESE NEW YEAR!

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

    yay! this is my year according to the chinese calendar, and if I'm not mistaken it is also tourist year since we are both born in 1994

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

WISH YOU ALL HAVE A GOOD TIME IN THE RATED CONTEST!

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

hack is stuck. Infinitely loading.. Is this happen occurs only for me?

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

    close, tab and reopen. bug in codeforces platform

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

      only if I knew this situation 1.5hr earlier, I can hack a lot because I started to hack 10 minutes after the contest begin :( Anyway, thanks a lot!

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

In DIV2 B for the first test case can 04 be a valid answer?

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

rating predictor is not working

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

The rating changes from the CF-Predictor Plugin are all 0's. Is this contest rated?

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

Why Div2A is harder than Div2B?

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

First problem was prettier than my girlfriend

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

Negative CF rating. its Valentine's Day cure for not having girlfriend

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

Div1B got me so much time to understand that answer for case p < k is just p, and I have to hardcode it. Damn it.

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

B seems to be standard: "Represent a number in negative base".

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

    Why does such problem exist? It easy to search on gg: https://www.geeksforgeeks.org/convert-number-negative-base-representation/

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

      The main part of the problem is not doing the base representation itself, but figuring out how base representation helps for this problem. For people like me who are not that smart, it takes time for us to figure out that the solution for B is just to represent p in base (-k). Although it may seem trivial for you, I think that the problem is interesting.

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

    for example, for me its not obvious

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

    I agree, but it seems a bit harder to figure out if you don't know that and try to expand the formula given in the statement instead.

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

What's tc 8 in div1 C?

Well, what I did was, taking points from (-21, -21) to (21, 21). Since you can't take all of them, I magnified the grid by 100*100, and took all lattice points there. And for each point, find in what circles it lies in.

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

    I didn't take into account this case:

    3

    -1 0 1

    1 0 1

    0 0 2

    the answer seems to be 5.

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

    my error was that it if there is no commmon area among the 3 circles than also it is possible that plane is divided in 8 regions

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

    I think it looks like

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

Happy Hackentine day!

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

Summary in Div2: Codeforces Round #462 (Div.2) a.k.a. Skip C-D and solve E...

(I know, counting all possible cases for E was still a pain, but to me and many others it is still easier than solving C/D).

Anyway, anyone knows about pretest 3 of C? ._.

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

    The subsequence does not have to be contiguous.

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

      What? So that meant I've got it wrong all along...

      Feeling like a dumb right now...

      Thanks for the support anyway...

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

      A non-decreasing subsequence is a sequence of indices p1, p2, ..., pk, such that p1 < p2 < ... < pk and ap1 ≤ ap2 ≤ ... ≤ apk. The length of the subsequence is k.

      Doesn't this imply sequence has to be contiguous?

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

        No. It's only contigous when p(i) = p(i-1) + 1 (with 1 < i <= k).

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

          Okay makes sense. Was solving in the contest thinking it had to be contiguous :(

          Thanks anyway

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

Guys, remember that -x * -x = +x²
Case for problema A:
3 3
-7 1 5
-7 1 5

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

The thing in A is not to use your mind -_- just simulate the process with O(N^3)

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

after months of participating in codeforces contests i ve come to the conclusion that the problems are generally trash with weak pretests and badly translated statements , written by sad weeaboos calling themselves programmers and problem setters so i will leave forever this site here is my passowrd : codeforcesistrash . bye

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

    I made sure you will not participate again, at least with this account :)

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

      by the way can you change the email thx bye again

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

        btw u werent supposed to change the password so that anyone can come visit my account i will send ticket to email noob

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

          You are like a girlfriend that you are breaking up with, and she like "I'm leaving and never will write you again" and then writes you like 9000 messages about how she hates you and how she won't ever write you again. Just leave, omg, nobody gives a shit.

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

I expect a lot of hacks at div1C, I wouldn't like to see more such tasks in future :

  1. Some participants had finished codes

  2. there is a lot of cases + geometry — more 5h ACM style

Other tasks were great to me.

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

in problem D Div 2 are polynomial always exist

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

    Yes, substitute x=-k into the polynomial and you will find that f(x)=q(x)*(-k+k)+p=p. Thus, the coefficients of f(x) are just the base (-k) representation of p, and the coefficients will always be smaller than k since it's base k.

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

Task C div1 / E div2 looks as easy version of one task from Timus.

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

i hated this contest : - unclear statements - a lot of math tasks - a lot of hacks ( which i don't like personally ) - uninteresting tasks

Thank you for trying and please don't do it again

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

Is this true?

For Div2D, notice that although decimal coefficients are allowed for q(x), in no solution will q(x) have a decimal coefficient (??)

Proof: Suppose some coefficient a_k is a decimal number. Then x*a_k will leave a decimal residue, to remove which you will need another decimal coeffcient for q(x). This cycle will never end.

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

    in g(x) all coefficients are integer.

    f(x) = (x + k)(g0x0 + ... + gmxm) + p

    So f0 = kg0 + p;f1 = kg1 + g0;...fm + 1 = gm

    Since fm + 1 must be integer, gm is integer to. And all gi integer.

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

I am surprised to see a lot of C++ submission for B. It seemed that people would rather implementing big number than writing this problem in a different language.

For C, what is the easiest (fastest to implement) method to find intersection of two circles? My idea is to divided the grid into k2 point, and for each point find the set of circles that this point is in (represented by a bitmask), and then the answer is the number of distinct bitmask. It seemed that setting k = 2000 is not enough (higher k will not run in time). So I thought about considering each circle center and points near the intersection of any two circles, and got stuck and the intersection thing.

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

My div2B has been hacked twice,because I regarded the parameter as 34 & 38.I really want to cry.

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

    In the last moment before submitting I changed 36 to 34. Locked the solution briefly after. The next moment I realized I'm f***ed. The right thing to do was to hack myself, but I lost that opportunity.

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

    I thought 1e18 had 18 digits -_-

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

What is the easiest solution for div1 C?

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

    Euler's formula.

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

      What's the value of V and E in Euler's formula if there is only one circle (or two circles not intersecting with each other)?

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

        You can think of a single circle as a vertex with an edge to itself, or 2 vertices with 2 edges between them. In any way, it has V = E.

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

          But if V = E, from R + V - E = 2 we have R = 2. This is correct when there is only 1 circle, but it's incorrect when there are 2 circles not intersecting with each other (R should be 3).

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

            Euler's formula works for connected graphs only.

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

            Euler's formula is V - E + F - C = 1, where V is number of vertices, E is number of edges, F is number of faces, C is number of connected components.

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

Very nice contest for DIV.2! All 5 problems are solvable, and many hacks on A, B. I was late to contest half an hour, but hopefully nobody was checking for hacks on B until that time.

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

Div2E: Can any one сonfirm that there is no such test in pretests?

3
0 0 1 
3 0 1 
6 0 1

Answer should be 4

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

Contest time was too dificult for me to participate, because it was 7:05 AM in my country, toooooo early ;-(, I was in REM 27 at that time. I think contests need to be scheduled in an hour more accesible to all the world.

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

Problem E Div2 / C Div1: Is there any tricky cases other than this one:

3
0 0 5
-3 0 4
0 -4 3

Answer should be 7

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

    For me every case is tricky :D

    For example all three circles have one different common point, or two circles are inside the third one.

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

I lost 1200 points in the last 20 minutes. Maybe i will never be able to participate Div.1. QAQ

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

    Don't lose heart, welcome to fight together to get a purple name :D

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

Anyone else thought the subsequences in div2 C had to be contiguous? I should really start reading statements more carefully...

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

In div2 B for k=39 answer can be 000888888888888888888 is it right?

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

Why cannot I understand Div.2 D(Div.1 B)......

It seems that there isn't any requirement on q(x), but if q(x) has infinite number of coefficients(in other words ), then it looks like there always exists a q(x) whatever f(x) is.

(I took f(x) = x for example and it didn't seem wrong)

So how to explain that? Or am I really wrong?

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

    Polynomial always have limited number of coefficients, that's the point. Polynomial with infinitive number of coeff. calls sequence.

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

      Oh, I see......
      It's likely that I'm misled by the paper of matthew99(in fact it's I that treat polynomial as sequence)
      Thanks a lot.

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

Why if we need 1 loop in problem B, '0' gets WA, and Accepted on pretests with '6'.

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

Div 1 C is the worst problem that can be proposed for a cf round, not only it can be found in various sources but also it only requires to just check some cases instead of the general case. D and E are good on the other side...

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it
    1. You can write a solution for general case, and I don't think that it is much harder.
    2. What is your problem with case analysis tasks?

    But I definitely agree that copying task from Timus is bad.

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

      When you need to analyse cases in a general problem it's good but when in a particular case I don't think it deserves to be C.

      Also, it isn't only on timus...

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

      This problem is prepared by me and I must apologize that this problem coincide with some problem elsewhere.

      I came up with this idea these days and found it hard to discuss all the cases even if n = 3. So I think it is interesting to leave it as a problem with some hacks, instead of a problem in general case (seems luckily that I haven't did so). However, none of us writers or tester realized that this problem is a special case for an original problem.

      When I saw you passed this problem in 3 mins, I knew things go wrong but can do nothing. But I am still so sorry for that.

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

        Actually you do not need to worry about it :) It is important only for 30-40 users, for all others that is not big deal ( it is true that is the 40 users with highest rating, but still it is not so big disaster ).

        Hope to see more your rounds !

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

          Well... thanks for your approval. But for me it is really an issue, which makes me feel upset instead of delighted for such an interesting(?) task. It seems that my hard works, especially generating some tricky cases by hand, for this problem are in vain.

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

            But... It's harmful for other participants. Because it's just after two very simple problems, a lot of people solved A and B in about twenty or thirty minutes.

            You see, div.1 D is super easy to code, and not difficult to think(just a few sigmas). But when I saw a lot of people passing C in 5 min(even 2), I spent one and half an hour thinking problem C. So I don't think it's good to make this round completely rated. Maybe unrated or semi-rated is a good choice?

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

              As you can see, all of us writers and tester didn't notice that. I must admit that it is also a part of ability to realize the original problem. Making this round unrated or semi-rated will be unfair to those who solved the problem by copy-pasting.

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

            At least you did good job with testcases ! More than 100 solutions got WA at final testing, also div 1 users got chance for hacking something during the contest.

            Still I do not like task :P But I do not think you done so bad job !

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

          Not only for reds, for example 6 people from my country solved it without even knowing the solution (the judge from the link above has public codes). I don't want to blame the author, it's just that codeforces needs testers from different regions.

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

            I wrote first that I do not like task, so I am completely agree with you !

            But I want to say I saw a lot of worse contests in last year than this one :)

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

What do you have on the following test for d1C?

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

Are there anybody who solved D without expanding the formula?

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

It's so funny when people who get high places are the ones who actually manage to quickly copy their sources off of other online judges to submit in this round. No hate.

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

The gift from TeacherQ has receivedQwQ

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

In div2 C, what does it means to reverse the subsegment? flip all 1 to 2 and 2 to 1 or std::reverse(l, r)?

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

I made a typo and still passed pretests for problem A div2

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

not a standard contest at all!!!

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

I have received teacherQ's new year gifts.

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

At contest

![ ]()

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

Codeforces community

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

I enjoyed this contest so much that now I suggest to introduce new contest type. The main goal is to find out, where you saw such problems and then use copy-paste technic to solve them.

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

    I know C today is bad, but come on, other problem is not that terrible.

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

      Ok, you are right, however it doesn't change the fact that even one bad problem can ruin the whole contest, and so the problem C did today.

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

      Div2. A and maybe B were terribble!

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

        if u can't solve a problem it doesn't mean that it's terrible or something ...

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

          and if u solved some problems doesn't mean that they're not terrible:)...

          you can just compare these problems with some other contests to understand my talking...

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

            I don't have any problem with div 2 A or B ... :)

            what was your problem with them which made you say there are terrible ?! ;)

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

              they're ridiculous problems, and both were just implementation problems and have nothing to think about

              getting point from this kind of problems in the contest's needs high precision and chance!

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

                I'm not agree with u,

                A good competitive programmer should be able to solve any kind of problems in contests ;)

                you can't find any comment from top coders like

                tourist or ... that saying some problem is terrible or something else ...

                work on your coding skills and don't complain with others :)

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

                  yes exercising is so important but i don't waste my time to solve A , B problems that have nothing to teach me...

                  any way these problems were terrible ;)

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

    So your solution from Timus is wrong or what? :)

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

    BTW, there already exist contests of that type. SnarkNews [season] Series, for example.

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

I miss when pretests' sole purpose was to decrease the load on the servers during the contest. Now it's just some additional hidden samples.

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

Why is CF-Predictor not working?

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

My friends (and I) with Div2E/Div1C...

Hope that the editorial for this problem will be something genius...

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

    genius

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

      Did anybody manage to pass this using Monte Carlo sampling and DFS?

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

        Probably not. Some of the testcases have an extremely small part, with an area less than 1e-6.

        upd: It's testcase 113, here is the plot --> http://www.wolframalpha.com/input/?i=plot+(x%2B4)%5E2%2B(y%2B2)%5E2%3D81,(x-8)%5E2%2B(y-4)%5E2%3D81,(x%2B10)%5E2%2B(y-10)%5E2%3D100

        http://www.wolframalpha.com/input/?i=plot+(((x%2B4)%5E2%2B(y%2B2)%5E2%3D81,(x-8)%5E2%2B(y-4)%5E2%3D81,(x%2B10)%5E2%2B(y-10)%5E2%3D100),(-0.69%3Cx%3C-0.68,6.36%3Cy%3C6.37))

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

      I'm still not getting it. I know the theorem, but how to set it up with a plot full of circles? (and to top it all off, many curves between two points may be formed)

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

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

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

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

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

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

What is the solution for Div2C?

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

    i solved using dynamic programming.

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

      Could you please explain your solution?

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

        My approach for Div2C:
        It is easy to identify that, all the possible non-decreasing subsequences will be one of the following type:
        1. Starting with 1 and ending with 1
        2. Starting with 1 and ending with 2
        3. Starting with 2 and ending with 2.

        Now for each pair (i, j), we want to find the length of each type of non-decreasing subsequence and we can keep the length of the largest.

        We have two arrays, dp[i][j][k] storing size of largest non-decreasing subsequence of each type [k], in subarray [i...j] and reverse_dp[i][j][k] for reversed [i...j].
        k = 0 stores maximum subsequence of type 1, k = 1 stores maximum subsequence of type 2 and k = 2 stores maximum subsequence of type 3. 

        if(arr[j] == 1){  
    dp[i][j][0] = dp[i][j-1][0] + 1;  
    dp[i][j][1] = dp[i][j-1][1];  
    dp[i][j][2] = dp[i][j-1][2];  
}  
else{  
    dp[i][j][0] = dp[i][j-1][0];  
    dp[i][j][1] = max(dp[i][j-1][0], dp[i][j-1][1]) + 1;  
    dp[i][j][2] = dp[i][j-1][2] + 1;  
}

        Similarly we can store data for reverse subarrays.

        Now, we want to find answer when we are reversing subarray [l...r]. We break this array in three parts [0...l - 1], reverse of [l...r], [r + 1...n - 1].

        We can form each type of subsequence by given data.
        Type two subsequence can be formeb by..

        [Type 1] + [Type 1] + [Type 2]

        [Type 1] + [Type 2] + [Type 3]

        [Type 1] + [Type 3] + [Type 3]

        [Type 2] + [Type 3] + [Type 3]

        We can calculate size of these subsequences by using dp and the reverse_dp.
        This is the link to my solution.

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

          [Type1] + [Type2] + [Type2],
          I don't think this would be there. All the possible options can be —
          [Type1] + [Type1] + [Type1]
          [Type1] + [Type1] + [Type2]
          [Type1] + [Type2] + [Type3]
          [Type1] + [Type3] + [Type3]
          [Type2] + [Type3] + [Type3]
          [Type3] + [Type3] + [Type3]

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

            Oh, yes. You are right. Thanks for the correction.

            → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
          int mx = max(dp[0][n-1][0], max(dp[0][n-1][1], dp[0][n-1][2]));
       for(int i = 0; i < n; i++){
           for(int j = i; j < n; j++){
               int a0, a1, a2;
                if(i == 0) a0 = a1 = a2 = 0;
                else a0 = dp[0][i-1][0], a1 = dp[0][i-1][1], a2 = dp[0][i-1][2];

                int b0 = rdp[j][i][0], b1 = rdp[j][i][1], b2 = rdp[j][i][2];


                int c0, c1, c2;
                if(j == n-1) c0 = c1 = c2 = 0;
                else c0 = dp[j+1][n-1][0], c1 = dp[j+1][n-1][1], c2 = dp[j+1][n-1][2];
                int d0 = a0 + b0 + c0;
                int d1 = a0 + b0 + c1;
                d1 = max(d1, a0 + b1 + c2);
                d1 = max(d1, a0+b2+c2);
                d1 = max(d1, a1+b2+c2);
                int d2 = a2 + b2 + c2;
                mx = max(mx, max(d0, max(d1, d2)));
    }
}

          @sak3t can you please elaborate this part little more?

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

            In the last for loop, we are taking subarray A[i...j], and we are finding length of largest subsequence of each type in A[0...l - 1], reverse of A[l...r] and A[r + 1...n - 1]
            a0, a1, a2 store length of largest [Type 1] subsequence, [Type 2] subsequence and [Type 3] subsequence respectively for A[0...l - 1].
            Similarly, b0, b1 and b2 store length of each kind of subsequence in reverse of A[l...r].
            Similarly for A[r + 1...n - 1], in c0, c1, c2

            Now we want to calculate maximum length of each type of subsequence in d0, d1, d2 in A[0...l - 1] +  reverse(A[l...r]) + A[r + 1...n - 1].
            We can create [Type 1] and [Type 2] subsequence easily. Look at the explanation above for how to calculate d1, and then we take the maximum of these three length.

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

Can anybody tell me what's wrong with my solution of PROBLEM A

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

    You set initial values for fans and ans too big. Long long in C++ can only hold up to (approx.) +-9e18.

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

      That won't be an issue.

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

        Yeah, the declaration of array size is wrong. But still, the wrong initialization values for those variables I think would lead to Wrong Answer, though.

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

          You're right, there may be integer overflow. But in this case, the code passed.

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

            I see, the constants are implicitly converted to the max/min value of long long.

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

Well...I have to say that it's a round full of FST....

I didn't realized that there was a round here until when the round had run for 30 min..

Then I tried but failed on A,then solved B immediately...

It's not difficult to know how to solve C,but I coded for almost an hour...

Before system test, I was #200+ but became #50 after system test..TAT

I have to say that it's an excellent round.

Finally, Happy Lunar New Year to all the Chinese players!

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

Div.2 D: Anyone here used Bezout polynomial remainder theorem?

P/s: In the last 45 minutes, although I knew we have to build f(-k) = p, but I couldn't implement it :'(

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

gimme privilege to write editorial for Div1C/Div2E: http://codeforces.net/group/qo1icaI3vI/blog/entry/1205?#comment-367474

you can also copy the code and paste exactly from gym with coach mode (sorry div2 poor you)

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

I have to say, this wasn't a nice cf round. It's understandable that pretests in Educational rounds are weak, because those problems are a little bit easier and the main purpose of that kind of rounds is the hacking phase. But making such weak pretests in a normal cf round? Why? I love this kind of contests, but this one is the exception...

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

in question A;

INPUT 3 3 -3 -2 -1 -2 0 1

Output: -2

Answer: 4

why not answer is 6 ? it is the maximum

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

    Tommy hides -3 so the answer is -2 * -2 if Tommy hides another number , Banban will get -2 * -3 which is larger than 4

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

Love such rounds with a lot of hacks :-) the best present for Valentine's day. :roffle!

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

Hey guys,

Please can anybody tell me the correct answer for input of problem A Div1:

200

2 1 1 2 1 2 2 2 2 2 1 2 2 1 1 2 2 1 1 1 2 1 1 2 2 2 2 2 1 1 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 2 1 1 1 2 1 1 1 2 2 2 1 1 1 1 2 2 2 1 2 2 2 1 2 2 2 1 2 1 2 1 2 1 1 1 1 2 2 2 1 1 2 1 2 1 2 1 2 2 1 1 1 2 2 2 2 1 2 2 2 1 1 1 1 2 1 1 1 2 2 1 2 1 2 2 2 1 2 1 2 1 2 1 2 2 2 1 2 2 2 1 1 1 1 2 1 2 1 1 1 2 1 2 2 2 1 2 1 1 1 1 1 1 2 1 1 2 2 2 1 2 1 1 1 1 2 2 1 2 1 2 1 2 1 2 1 2 2 1 1 1 1 2 2 1 1 2 2 1 2 2 1 2 2 2

thank you!

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

    The answer is 116.

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

      I did not notice it is non-continuous subsequence :(

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

How to solve Div.1 A in O(n)?

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

    You can do a dp using current element, value of last, and the current state (non decresing, non incresing and non decresing again) [n][2][3]. This part that we'll reverse is the part that we consider non incresing

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

codeforces problem is like you can do both hack and AC..

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

can someone please help me with my code for DIv2C : https://ideone.com/Nd1oiy

It's an O(N^2) solution but it gives me TLE on test 11!

Edit : please don't mind. I am thinking totally wrong.

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

    Its not O(N^2). You call rev() function into two for loops and every time you call a for loop in rev(). That means 3-nested loops. So its O(N^3)

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

    Your solution is not O(n2), it goes to O(n3) as for each pair (i, j) you are swapping times. So each pair will be O(n2) and for this you are going at max on average n/4 times, hence O(n3). Correct me if I am wrong.

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

      oh sorry! Please don't mind.

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

For Div. 2 D, I could reach the conclusion that p must be in the form of a0 - a1 * k + a2 * k2 - a3 * k3..... + ( - 1)n * an * kn
How do I move ahead from this conclusion? Is there a theorem or property that I am missing? Please guide. Thanks.

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

    Now you are trying to represent p as a base (-k) integer.

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

      Seems like I need to go back and revise basics of number theory. I had no clue that a number can be written in (-k) base. >_<. Thanks anyway.

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

The reason why I don't need a valentine. :P

Codeforces is already my <3

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

Failed 1C due to the floating point precision error...

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

Can someone explain why my solution for Div2A failed on testcase 10 35279033

My solution is :

1-Sorting both arrays ascendant

2-check if the last element in Big Banban's array is positive

then i will check for the element tommy[n-2] if its negative answer will be

cout << '-' << (ll) (abs(x[n - 2]) * (ll) z[m - 1]);

if it positive answer will be

cout << (ll) (x[n - 2] * (ll) z[m - 1]);

and same as if Big Banban is negative

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

    In testcase 10 Tommy has 50 negative numbers and Banban has 50 positive numbers.

    so Banbans strat is to pick numbers with lowest absolute value, because product is guaranteered to be negative

    but you pick the num with largest abs from Banban's numbers

    p.s. by the way, this problem is relatively complex until you make a key observation: the input set is so small that you can just brute force all the combinations

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

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

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

Thanks to your fantastic tasks, I could finally go into a new year with a new rating and a new color.

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

Hack for Div2 A ?

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

Can someone please explain solution of Div2 C clearly and in an easy way? Appreciate your help!

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

Happy New Year！ Chúc Mừng Năm Mới！

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

for problem A i find a hack but it is not in test case: the hack is: 3 3 -1 0 0 1 1 1

my code output is -1e8 but ans is 0: http://codeforces.net/contest/934/submission/35661651

→ Reply