romanasa's blog

Codeforces Round #329 (Div. 2)
By romanasa, 9 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #329 (Div. 2). It'll be held on Wednesday, November 4 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

Writers are Stanislav Naumov (josdas) and Roman Korobkov (romanasa). There will be 5 problems and you'll have 2 hours to solve them. I hope you enjoy the problems.

Great thanks to GlebsHP (Gleb Evstropov) for helping me preparing the contest, to Delinur (Maria Belova) for translating the statements into English, to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon.

The scoring distribution will be announced later.

Good luck and high rating!

UPD: The round will use the dynamic scoring with 250 points step.

UPD2: Editorial

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

Comments Comments (227)
| Write comment?
»
9 years ago, # |
  Vote: I like it -14 Vote: I do not like it

gl & hf!

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

    I'm so sorry, it seems like no one enjoys this problems...

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

      No one except div1 guys and div1 guys with div2 accounts :D

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

        There are even some Div1 contestants that can't solve these problems

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

hope to see short statement .... and good luck to every one :)

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

Is there any punishment for those who doesn't write this,"thanks to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon." in their contest blog???,, Just curious to know..!!!

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

    Look at the previous contest description. It is quite concise and yes, it doesn't include the phrase. So ask Morphy, I hope he is able to answer after that:)

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

Good Luck!

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

Does anyone want to guess how long will system testing take? What about rating changes? Hopefully they won't take very long.

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

is this contest was in gym before :D see tags
Tutorial of ыфф
Announcement of Либо баг, либо фича.
Announcement of Короб лучший
Discussion of Короб не голубой

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

    As I understand anyone can attach any phrase to blog if he creates mashup with this name. :)

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

Excited!!

My First Contest On CodeForces.

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

    Exited!!

    It should be excited instead.

    Sorry for being picky :)

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

    Welcome to codeforces :).Wish you best luck!!!

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

Why?

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

    And the last 5 link are linked to this page :-| And i can't read russian and is there any one to tell me what does they mean?

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

    It says "You are not allowed to view the contest" when I click on the links. Does anyone one know why?

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

    successful hack

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

First round from blue coder?)

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

Hello all, why are regular rounds not scheduled for the weekend if possible? It seems that by moving contests to the weekend, more people (especially students or employees of different time zones) could participate.

Thanks, and I hope everyone enjoys this round.

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

Hope see good translation :3

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

completing whole contest, hacked on A being like :'D

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

    ┬─┬ノ( º _ ºノ)

    We learn from our mistakes :)

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

Am I the only one who thinks its funny that fml stands for f*** my life :p

Sorry romanfml31.

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

    lol. Physics and Mathematics Lyceum. In russian language "fiziko- matematicheskiy litsey"

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

    Actually it means:

    ФизикоМатематический Лицей (Physics and Mathematis Lyceum) -> ФМЛ -> FML -> Well :D

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

Why dynamic scoring :'( why why

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

Problems will be sorted by expected difficulty or shuffled?

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

    Problems will be sorted by expected difficulty

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

shocked
it seems that "The score distribution will be announced later" better than early announcement with dynamic score :(
we can wait man :D

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

Best wishes to all participants !

By the way, Soccer fans will be happy cuz there will be European champions league after the contest:)

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

What about order of problems? Are they will be sorted from easy to hard by authors? Or random?

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

It's okay too be dynamic scoring, but I hope the round will not be the battle of speed.

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

short Blog = Long problem :| (I I learned from contest 328)

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

In fact, why is the scoring distribution "announced later" every time?

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

The site is quite slow now, my solution was being evaluated for something like 5 minutes and when I want to click on some link it loads longer than it usually takes. I hope this will not be the case during the contest, at least :)

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

For being good in dynamic scoring contests it is very good to solve first problem B or C but it is a big risk because if you don't solve it fast or wrong then the contest will go on very bad. You can choice to risk or not BUT I THINK DYNAMIC SCORING CONTESTS ARE NOT GOOD FOR TESTING CODING ABILITIES !!!!

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

    If you solve all five problems in any order and in any time I guarantee you will do good in the contest and get a big rating increase.

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

    If you solve all five problems in any order and in any time I guarantee you will do good in the test and get a big rating increase.

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

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

Delay as expected!!!

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

10 min delay

OK, I don't participate

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

It's loading really really slowly...

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

Delay again ????

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

.

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

Do you guys think its a good idea to participate in a contest when you're sad about something in your life?

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

    I think it is one of the best ways to relax and forget about problems(not CF, problems of life=)).

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

    The delay got me thinking...... maybe today I should pass it....but you guys have a point.

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

    Cf contests makes you forget all your problems and just think about the problem..

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

    No. You won't be focused as you expect.

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

    "Be Obsessed. Do something which you are passionate about. Do it because you love to do it. Everything else is secondary."

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

It looks like we should donate again.

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

what an unruly contest!!!:(

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

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

CONTEST IS BEGINNING LATE! 10 MINUTES DELAY :/

What's wrong?

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

AlreadY 15 minutes late. After system testing....................?

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

delayed why?

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

The longest delay everrrrrrr. :/

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

15 min delay. wow

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

You mean: "as usual Div. 1 participants can join with fake accounts"

Bec that always happens in every Div. 2 only contests

There are more than 750 new accounts participating this Contest!

Many contestants are honorable and participate as "out of competition"

But unfortunately some of them are not!

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

    How cares about that!!! It is their business. I am focus on my own performance.

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

delayed 10 mins delayed 5 mins

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

Unknown language round?

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

These Problems should be in Div.1.

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

Is it div 2 or div 1?? I am confuse.

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

what a HARD contest !!!

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

contest is hard or I very weak :|

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

Not complaining, but there's a reason why there is a separate category on CF here called Div 2.

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

A very steep difficulty curve indeed..

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

Bad contest :|

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

div 2 ????!!!!

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

OMG!!! C problem with 3000 pts

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

The new coordinator sucks. :)

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

What a hard contest! I couldnt solve even problem A completely! This is frustrating and I lost 150 points in resubmissions!! wtf

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

Respect to Problem C!

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

    How to solve B?

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

      put each line intersecting with line x1 and x2 in a vector pair then sort it and iterator from the begining to end and find the solution.

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

      If you try a brute force method of checking each pair you wont pass because its a O(n^2) algorithm.

      Instead of lines think of them as line segments from X1 to X2

      You have to find the y intercepts at X1 and X2.
      Create a pair vector of the form { line_number , X1_Y_intercept}
      Create another pair vector of the form { line_number , X2_Y_intercept}

      Sort them both based on X1_Y_intercept and X2_Y_intercept.

      Now
      if the ordering of the line_number is the same in both vectors then
      there is no intersection
      else
      there is an intersection

      UPDATE : Since I got lot of upvotes I thought I shall make it clearer by an image

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

      oh and make sure to use long long (unlike me) cuz input may overflow integers

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

        el3el2, and make sure to use doubles cuz input can be decimals too :D 

        Problem B. Anton and Lines
*****
x' is NOT guaranteed (and is NOT required) to be integer
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          That just means the points of intersection need not be integers. The input is all integers. They just wanted to discourage trying to go through the x-axis checking whether two lines cross at that vertical line.

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

Thank God that contest has finished

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

i enjoyed this div-1 contest....!!!!!

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

I think this contest is like a Div-1 contest.

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

    Not really Div 1 problems are hard but these problems are ugly !

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

I feel bad for the people who are taking part for the first time. They will probably think Div 2 people are expert programmers after seeing such problems :P

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

    Interesting how you are more concerned about the fact of whether DIV2 coders are expert or not. You are supposed to be worried about the expression it would have on them after a relatively not so simple contest. I think you are a narcissist, egotistical maniac.

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

Geometry contest ?

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

How to solve B?

I solved x = (b[j]/(k[i] — k[j])) — (b[i]/(k[i]-k[j])) and check if x > x1 && x < x2 and got TLE on test 16.

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

    Something like this (lines[1,...] — k, lines[2,...] — b): 

    temp1:=lines[1,i]-lines[1,j];
temp2:=lines[2,j]-lines[2,i];
if temp1<>0 
  then temp3:=temp2/temp1 
  else temp3:=0;
if (temp3<x2)and(temp3>x1)
  then ....

    And TLE too...

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

    This is my idea

    I have two vectors where I save the interception with x1 and x2 for each line. The tricky part is that I am saving in the vector a pair<double, pair<double, int>> where the first element is the y_intercept value and the second value is a vector with the other y_intercept and the index of this line in the input.

    Then, I sort both arrays and for each element from the sorted array, I check if it is the same element. If at position i, there is not the same index line then, we have an interception between 2 lines. If the order in both arrays is the same, there is no interception between any two lines.

    I hope this solution passes the systest.

    PS: PASSED SYSTEST, LOL!!!!!

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

    This Image should explain it :)

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

    try it with long long int :D

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

Lets hope Arsenal wins today. Its already a bad day after such a hard contest.

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

15 minutes delay + dynamic scoring + extremely difficult problems -> a disaster!

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

Even O(n^2) solution passed B . I lost a few points trying to hack, not cool at all :)

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

    how O(n^2) pass?

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

      it is an old trick. they just check the first 6000 elements... if YES print yes else it prints no (because these tests are made by system).

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

        LOOOL, WHAT.

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

          99% the answer is no when the answer is no in 6000 elements.

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

        so they may TLE in system test?

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

        It's easy to make hacks for those solutions, though.

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

          I made a case where the input consisted of 1e5 parallel lines, but the solution passed in about 850s . However, someone else hacked it using increasing slopes lines.

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

            Mmh I was talking about the "N^2" solutions that only consider first K points for some K.

            By the way, take a look at the loop conditions in the submission you tried to hack, specifically the inner loop in solve(): 14073024. It doesn't actually run for N^2 operations on the case you tried.

            Looks like the author's two mistakes (doing N^2, but with incorrect implementation) cancelled each other out on your specific test case. :|

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

    no it got TLE

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

    No, solutions that have O(n^2) time complexity didn't pass system test, and it failed also when checking just the first 6000 elements .

    If you saw such a solution please link to the submission .

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

hahahahahahahahahahahahahahahahah

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

How to solve Problem-D?

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

    Just some thoughts. You can observe that you need to divide Y by at most O(log(MAX_VALUE)) numbers greater than 1. So now I think you can use HLD to quickly answer queries "Which is the next number in this chain which is greater than 1?". However, I didn't implement that. And a friend of mine told me we can solve it using LCA-like approach (with powers of 2) with union-find but I don't really understand that :D

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

Participated in div1 in a div2-only contest.

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

I had never spent this much time on Div 2 B Nice problem :)

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

What a hard contest:

problem A: harder than usual, took me >10 minutes to solve it.

Peoblem B: Passed pretest with ~0.6 seconds. I'm not sure if python can pass 1 second time limit with full 100K input.

Problem C: Are you kidding? I have no idea how to solve it.

Problem D: I know it's HLD but I never and can't implement it.

Problem E: Time to learn C++! ugh getting compilation error. :p

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

    Seems problem D can be solved by DSU and LCA.

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

    not sure if python solution for B will pass for given time limit. yeah, time to learn C++ seriously.

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

    Even using HLD problem D is very tricky. I thought pre-computing the multiplication of the edges and use HLD but... Xi <= 10^18 :(

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

      The Yi<=10^18,too.Maybe you can limit the multiplication of the edges in 10^18:p

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

      This could be avoided by carefully checking for overflows. Take a look at my solution: http://codeforces.net/contest/593/submission/14073334 (lines 256-258, or ctrl+f "__builtin_smulll_overflow"). I think you could also replace the check ab ≥ 2 × 1018 with something like .

      But yeah, avoiding these kind of overflows is definitely not fun and I think it would have been better to put limits of the form x ≤ 109 instead of x ≤ 1018.

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

        :o I didn't know about that function! Thanks :D

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

    Can anyone explain DSU-LCA approach for problem D?

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

      I never thought this solution in contest-time but I'll try to explain:

      If node a and node b has edge weight = 1 you can merge node a and node b since multiplying or dividing by 1 has no effect.

      Otherwise because edge weight is an integer so number of multiplication or division will not exceed ceil(log(10^18)) = 60 operation. I guess this can be done without LCA(?), just save the parent and depth of a node(?)

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

        You must have LCA. How else could you tell how far should you traverse up the tree?

        Edit: My bad — you don't need an LCA.

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

      First observation is that if you keep dividing y, you'll quickly get 0. (Of course, if you divide by a number bigger than 1)

      This is the basic idea

      // a path from a to b. Initial value is y.
lca = getLca(a, b)

while (y > 0 && depth[a] > depth[lca])
    // an edge e connects a and a's parent
    if e.weight > 1
         y /= e.weight
         a = parent[a]
    else
         a = parent[a] // ***
// do the same thing with b

      This is too slow because of *** part. It's too slow when we have a lot of edges whose value is 1. Basically, we want to skip all edges whose weight are 1.

      For that we can use DSU.

      Initializing... (This must be done before processing query)


      for each node u
    for each child v of u
        if e(u,v).weight == 1
              g[v] = find(u)

      Every time you update the cost, we can do the same.


      // update an edge e = (u, v). u is a parent of v.
// new cost = c

if c == 1
    g[v] = find(u)
      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone please explain why this output is wrong for C:

(0+(t-1)*(10+0*(t-2)))
(10+(t-1)*((0-10)+10*(t-2)))

I consistently got WA in pretest 1 and I think pretest 1 must be the sample.

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

    10 + 0 * (t - 2) is invalid, it should be 10 + (0 * (t - 2)). Look at the examples under the testcases.

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

      You are right.

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

        I'm always right!

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

          You aren't right always, correct is only: (10  +  (0  *  (t  -  2))) (without spaces of course)

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

    Okay, let me see

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

TodaY most of the hacker are <=300. (Hacked B).

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

18 solutions for problem C, seriously?

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

this my first div1 contest

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

How to solve problem D?

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

    Notice that we will pass not more than ~64 edges with something greater than 1 written on them. Therefore, the only thing we need to do fast while travelling on a tree is to pass sequences of edges with 1 written on them (because they don't change your yi anyhow). This can be done by DSU — merge two adjacent vertexes (u, v) if you get request "write 1 on (u, v) edge, and simply update number on edge if the number  ≠ 1. Also you need to update the topmost vertex for this set in DSU. Now we answer on every request by checking if there are more than 64 numbers on path  ≠ 1 or by finding all these numbers and consequently applying all the divisions to yi.

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

.

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

    I'm dying :D

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


    LOL me too. I was hoping I could hack someone like me. xD
    You should have been in my room.

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

    отличные претесты. Можно было что угодно запихать

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

    hahahahahh .... are you serious :D ?

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

It is sad, but I have to downvote :(

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

Don't even care about the system testing. :D

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

Kudos for problem C! I spent the whole first hour writing my solution, and I'm still a bit worried about the full system tests, but I really liked it. I'm really fond of problems where you have to construct an object that satisfies certain properties, no bullshit 'find the shortest path with a twist' problems, but something you actually have to think about.

EDIT: yay, passed the systests! It also seems my solution finds much shorter answers than the jury solution :)

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

    I tried to use polynomial interpolation on the axes independently, what did you do? I dont understand the part of your code where you are taking modulo 50

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

      I exploited this function: W|A plot. It's zero for all x ≤ c and for x > c it satisfies f(x) = 2(x - c). In other words, this function only becomes relevant after position c. Let's denote this function by fc(x). If you pick for your function g(t) = a0 + a1 * f0(t) + a2 * f1(t) + a3 * f2(t) + ..., then this function will satisfy g(0) = a0, g(1) = a0 + 2 * a1, g(2) = a0 + 4 * a1 + 2 * a2, g(3) = a0 + 6 * a1 + 4 * a2 + 2 * a1. If you pick your coefficients ai appropriately, you can reach any even value you want (or equivalently, exclusively odd values if you pick a_0 odd). Since the cirles have at least radius 2, this is sufficient jump into any circle.

      I also thought about polynomial interpolation but the fact that you couldn't do division was a bit unfortunate.

      EDIT: As a bit of background, the idea for this came from the beautiful identities:

      max(a, b) = (a + b + |a - b|) / 2
      min(a, b) = (a + b - |a - b|) / 2

      (verify this yourself! hint: consider $a \geq b$ and separately)

      It would be great if you could use these functions directly so you could make the step function max(0, min(1, x - c)), but unfortunately we cannot divide by 2, so this step function would make jumps of size 4. So I dropped the minimum, ending up with f as described above. Then you have to mess around with your coefficients, and poof you have a working solution!

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

        Nice solution :D I'll try to implement this

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

Sorry community, I must accept that this round was too hard for div. 2. I will try to better evaluate the difficulty in the future.

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

    I have 1 suggestion for C: Why do you need to have so many brackets? I don't think it is that hard to write judge that works without those extra brackets, but it makes life of contestants much easier.

    The problem is already quite hard, and you're making it much harder for contestants that could come up with some complicated functions but failed to insert brackets correctly.

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

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

Ok, you should definitely lower Div2 problem difficulty... Problems A and B were excellent. Problem C... i don't even know what to say about problem C. It's difficult to even understand what is asked. Problem D should at least move to most difficult and problem E is for Div1 ...

This is my humble opinion, but i think others will agree.

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

D was standard HLD. Just the overflows had to be taken care of. But how to approach E?

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

    I think it doesn't need HLD.

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

      May be there are simpler approaches, but what came first to my mind was HLD.

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

      Can you please explain how to solve it without HLD?

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

      How did you approach D? and what is the intended solution of E?

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

        E: (I'm using zero-based index, which is different from problem statement)

        This can be solved by dynamic programming with matrix multiplication.

        In a nutshell, make a vector V that keeps the number of ways to get to each cell and make a square matrix C such that C*V is the information about 1 second later. And basically keep doing (C^n)*V with some changes on C.

        Here is a more detailed solution.

        Let f(i, j) = i * M + j. (This maps location (i, j) to an integer, and it's bijective.)

        First make a column vector V such that f(i,j)th element has the number of ways to get to (i, j) at some point. Initially, V is filled with zero except f(0,0)th element is 1.(Because we have 1 way to be at (0, 0))

        And make a square matrix C whose size is (N*M) x (N*M).

        Fill 1 in matrix C such that C*V is going to be a column vector such that f(i,j)th element has the number of ways to get to (i,j) 1 second later. More specifically, for each (i, j), we need to fill C[f(i,j)][f(i',j')] = 1 if you can move from (i',j') from (i,j).

        Now to get the information of n seconds later, we just need to calculate (C^n)v. (C^n) can be calculated very fast by using Exponentiation by squaring.

        Cats can be handled by changing the elements in C. When a cat shows up at (i, j), every element of f(i,j)th row of C is going to be 0.

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

      Can you explain how to solve it without HLD?

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

    Solution without HLD.First observation is that you need to make at most 60 / with numbers >1 to make it 0. I note 1 edges>1 and 0 edges=1.So I want all 1's on path from a to b,if there are more than 60,the answer surely is 0.

    So starting from a,b I go to lca and should have a function that gives the first ancestor of x that has 1 to have no more than 60 steps on each query.

    The brute force is using disjoint sets.The problem is the updates on edges,but update is of form x[pi] to ci with ci<x[pi].So from a 1 it can be 0 but not reverse,this helps a lot.

    Try firstly to do this problem 1D on an array,then it will be similar(just that position x+1 is father(x)).

    Complexity O(q*log(max_y)).

    If the updates were random,I can do a query in O(60*log^2),does anyone have a better complexity?

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

System testing please?

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

lol i wish this contest as unrated

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

Too hard for me... Only able to solve the first problem.

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

Maybe stupid question, but how solve A? :)

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

    Try all of the combinations of two letters and check what length of the text we'll have if we take only words with these letters :-)

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

    Count the maximum number of words that can be formed with every pair of letters

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

I_love_Hoang_Yen didn't solve C :'D and I am expected to?

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

What is wrong with this approach for B?

Take xi = x1+EPSILON and xf=x2-EPSILON for EPSILON = 1e-7. Find the indices of the lines with the highest value at xi and xf. If these indices are the same, print NO. Else print YES.

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

    Draw two intersecting lines and then draw another one well above them.

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

seems I miss great contest!

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

Editorial?

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

2 solved problems + 2 hacks = 67 place. NICE.

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

Can codeforces show recent comments at the top instead of bottom of the page. We need to scroll down to find recent comments.

Also it would be best to too negative comment all together as it doesn't serve much purpose on this forum.

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

Are there any a, b, c such as [[a/b]/c] != [a/(b*c)]?

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

    No. Let be the remainder of after division by , so we have and such that . Then . Now let be the remainder of after division by , so we have and such that . Note that , since . Then , and since , . So .

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

      After that announcement I decided that HLD was bad idea)

      P. S. To be honest I didn't even try to implement it.

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

The thing I liked the most is "Yes" and "No" were case insensitive. :D

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

Could have had such a good rating ...

Problem B...Failed System Test...changed int to long long int...Got Accepted :'(

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

    I feel the same way with such stupid mistake. On D i have MAX=1e18+1 instead of MAX=1e18 and that made my program fail system tests.

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

I miss PrinceOfPersia 's contests :D

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

I wonder how many solutions of problem E fails at this test case:

5 4 10000

1 1 1 i*10000 + 100

There is no restriction in the statement that forbids using this test case, right?

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

    I don't see what is special about this case?

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

    You are right. It seems either the test cases are extremely weak, or the constraints and restrictions are misleading. Here's a more extreme version of the worst test case:

    5 4 10000

    (Followed by 10000 lines, i = line number)

    1 1 1 i * 200000

    I can pass this in 3 seconds but my implementation is heavily optimized. I'm certain most solutions will fail in this case. I got accepted in 156 ms and that's a joke, considering I can generate test cases quite easily where it takes > 3 seconds.

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

problem D A Big Trouble I use quick_mul to judge the num is exceed 1E18 or not,and this solution has no accuracy error!But someone may use log function to solve the problem,but we know the double only has 15~16 bits of accuracy,but the problem can have 18 bits,so this solution has no accuracy error! When I submit my solution,I get WA.Just a big data,the answer requires 0,but I output 1.But I think whether my answer is wrong.Because if standard procedure use log,I think may the data is wrong because of accuracy! So does everyone know standard procedure uses which method?

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

This contest was very difficult, but I must admit I overthink problems like B :( always seeing "geometry" problems like demons ...

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

    If I remember it right, this blog should have gotten nearly 70-80 down votes after the contest ! I think you're not alone with the vision

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

First round from blue coder, they said

Easy contest gunna be, they said :P

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

    Actually the lower rated the coder, the harder the contest. They are just trying too hard.

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

Some bug in my code for Problem B Anton and Lines, please, thanks you

my submissions WA on test 24

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

It's so difficult that those whose scores are around 1700 can only solve the first two problems,and the third problem is so difficult that I don't think it's a successful problem.So sad.

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

Finally Experted!

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

Necroposting may be discouraged by the community, but I trust they'll forgive me for making the very necessary comment that problem C is the most absolutely horrendously disgusting dumpsterfire of a problem in the history of computing, and that the fact alone that there exists a human smart enough to see a solution, yet not smart enough to see the ungodly number of reasons it should have been rejected as a problem idea before being typed is proof enough we do not live in a simulation.

Also the "Incorrect functions" section has a typesetting error in example 3. But I do not recommend anyone dare to fix it, because I am not cruel enough to show such a statement to even my worst enemy, let alone someone trying to be helpful.

That is all--carry on.

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

    it would be funny if they actually corrected the sample

    → Reply