Codeforces Round #618

5 years ago, # |

← Rev. 2 →

for div 2 D, I tried this approach: if n is even and slope of opposite sides are equal, then yes else no, can someone say what's wrong with this approach. this is my submission https://mirror.codeforces.com/contest/1300/submission/70677064

→ Reply

5 years ago, # ^ |

+26

should be equal and parallel

→ Reply

Tschech

5 years ago, # ^ |

Oh wow I did that and got wrong answer. Guess I must have a bug in my code. And I thought the solution is really wrong because I could not convince myself that this must work.

→ Reply

brurrito

5 years ago, # ^ |

Same for me, I assume this is due to a numerical precision issue. Anyway instead of calculating lengths of each edges I could've compared the x & y components on each vector

→ Reply

Tschech

5 years ago, # ^ |

Oh yes, it was an overflow, should just use long long all the time. Guess I do not deserve to get rating

→ Reply

spookywooky

5 years ago, # ^ |

What is "equal" here?

→ Reply

5 years ago, # ^ |

equal means the lengths are equal

→ Reply

spookywooky

5 years ago, # ^ |

← Rev. 2 →

Okay, thanks.

But, is it not that if two opposite sites are not same len, then some other two sides cannot be parallel?

PS: Perhaps I better wait for editorial, thanks anyway.

→ Reply

5 years ago, # ^ |

take a regular octagon and shift any its side by epsilon.

→ Reply

5 years ago, # ^ |

← Rev. 13 →

I didn't get this, on shifting a side by some distance, won't some other pair of opposite sides become non-parallel

→ Reply

5 years ago, # ^ |

shift while not changing other sides' directions

→ Reply

5 years ago, # ^ |

got my mistake! really good question. Thanks for helping!

→ Reply

5 years ago, # ^ |

that's exactly why I wasn't checking for the lengths to be equal

→ Reply

dranikpg

5 years ago, # |

Why are almost all tasks based on math?

→ Reply

shashack

5 years ago, # |

Why Div2 D the second case answer is no? It seems to me that there are always A, B in P such that for all (x, y) in T (A, B) = (x, y). Could you give me (x, y) that the vector couldn't be made by the set of points in P.

→ Reply

midnoon

5 years ago, # ^ |

+16

Visualization for second case is in the description

→ Reply

SPyofgame

5 years ago, # |

-17

Thanks problem setters for the problems <3

→ Reply

danirainy

5 years ago, # |

+21

intersting problems. I did not prove anything and just guessed the solutions for div1 b and div1 c. They both worked haha

→ Reply

algomaniax2.0

5 years ago, # |

What is/are the hacking cases(s) for Div1B/Div2D

→ Reply

yashgarg2107

5 years ago, # |

+29

How to solve Div1C

→ Reply

SHZhang

5 years ago, # ^ |

← Rev. 3 →

+26

Build a lower convex hull with points being (i, s[i]) where s[i] is the sum of the first i values, in addition to the point (0, 0). Each edge in the convex hull represents an operation on the interval [x1 + 1, x2] where x1 and x2 are the x-coordinates of the endpoints of the edge.

My submission: https://mirror.codeforces.com/contest/1299/submission/70681667

→ Reply

tRuNgSeO

5 years ago, # ^ |

+19

Convex Hull (though I did not manage to submit at the end).

You have to minimize the first element by choosing a segment $$$[1, i]$$$. Any operation on the segment $$$[l,r]$$$ which $$$1\le l\le r\le i$$$ or $$$i\le l\le r$$$ is unnecessary. Besides, if operating segment [l, r] which satisfies $$$l\le i\le r$$$ before [1, i] can cause the first element to be lower than operating [1, i] solely, then with some mathematics, you can prove that operating [1,r] is more optimal.

Therefore, you should find $$$i$$$ such that $$$S_i / i$$$ is minimum where array $$$S$$$ is prefix sum array. Then you fill all element from $$$1\rightarrow i$$$ with $$$S_i/i$$$. Trim the subarray $$$1\rightarrow i$$$ and repeat. The solution is optimal.

Since $$$n\le 10^{5}$$$, we can use Convex Hull trick to squeeze the solution into acceptable complexity $$$O(nlogn)$$$.

→ Reply

AmineTrabelsi

5 years ago, # |

→ Reply

Thallium54

5 years ago, # ^ |

-8

So true

→ Reply

HanaYukii

5 years ago, # |

← Rev. 2 →

The Div1B figure mislead me for over 1 hour.

Reading quiz orz.

→ Reply

reeWorld

5 years ago, # |

Thanks for the contest! Problems are very interesting)

→ Reply

utsav_deep

5 years ago, # |

What are corner cases of div 2E? And why was this approach giving wrong answer: Traverse from right to left and calculate smallest average possible by including a[i] and in the process, also maintain the span of the current avg starting from current index to some index in right. If a[i] is smaller than current average, then set current avg to a[i] and span of current avg to 1. Finally print the answer with final values like this:

                DecimalFormat df = new DecimalFormat("0.00000000000000");
                double dmx=avg[0];
                for(i=0;i<n;i++){
                    dmx=Math.max(dmx,avg[i]);
                    out.println(df.format(dmx));
                }

My actual solution: https://mirror.codeforces.com/contest/1300/submission/70679283

→ Reply

mango_lassi

5 years ago, # |

+23

How to check if a graph has a nontrivial cycle with xor zero? I only know how to do it with gaussian elimination, but that's too slow.

→ Reply

5 years ago, # ^ |

actually the Gaussian elimination works because if there are more than 5 basis cycles, their costs are linear dependent.

→ Reply

ohweonfire

5 years ago, # ^ |

Actually, there's only less than 400 different vector spaces in $$$Z_2^5$$$，so after some preprocessing, you can do gaussian elimination in $$$O(1)$$$ , and do dp where state is current vector space. It works in $$$O(400n)$$$ .

→ Reply

tfg

5 years ago, # ^ |

Coded that with an additional log and got rekt by TL :(

→ Reply

ohweonfire

5 years ago, # ^ |

Oh, I misread your question. As for checking, just consider an arbitrary spanning tree, and consider all cycles consisting of exactly one edge that is not in the tree. Every nontrivial cycle can be constructed by 'xor'ing the cycles of the above type. So checking if a graph has a nontrivial cycle is equivalent to checking linear independence of all cycles of the above type. This can be done by union-find.

→ Reply

ame

5 years ago, # |

this solution SortWithArray is getting timelimit but the same implementation with the vector got AC sortWithVector , how could this happen ?

→ Reply

michao

5 years ago, # ^ |

-6

you have declared array which has size 100001 and it should be min. 200001 because it has to store 2*n elements.

→ Reply

tfg

5 years ago, # |

+27

Worst feeling ever: code general polygon similarity just to get WA due to overflow then guess the solution after 4 WA because it's div1B and people solved it fast af.

→ Reply

Lewin

5 years ago, # |

+31

I wrote an easier version of div1c a couple of years ago here. The bounds for that allowed for n^2. Luckily, there was a description of how to do O(n) in the discussion.

→ Reply

nvmdava

5 years ago, # ^ |

+22

Damn, my bad, downvote this comment if you want to.

→ Reply

aswwwanth

5 years ago, # |

+76

Geometry Geometry Everywhere

→ Reply

snorkel

5 years ago, # ^ |

-16

Geometry is good bro.

→ Reply

snorkel

5 years ago, # |

-7

When the ratings will be available? I hope to become newbie :(

→ Reply

NeiH

5 years ago, # |

Thanks for your contest :3 such an amazing performance, I will become purple <3

→ Reply

madlogic

5 years ago, # ^ |

Congrats!

→ Reply

5 years ago, # |

-6

How to solve the precision problem of the Div2.E(Div3.C)1299C - Water Balance

When I used float to save my answer, I got WA 70681208

When I turn to double, I got TLE 70681660

So sad:(

→ Reply

Mohammad_Yasser

5 years ago, # ^ |

← Rev. 2 →

+17

The problem said that you shouldn't read input as doubles. You can read it as integers and then convert them to doubles. E.g:

double a[N];

int x;
cin >> x;
a[i] = x;

→ Reply

5 years ago, # ^ |

It works! Thank you very much!

But one more question, what's the difference between them? I can't quite get it.

→ Reply

Mohammad_Yasser

5 years ago, # ^ |

+25

Imagine that you don't have built-in functions to read input except one function that reads a single character, which is getchar() in C++. Try to implement a function that reads double using getchar(), and implement another function that reads int.

You'll observe that the first one involves more operations that the second one, and also will be performing double operations instead of int operations, hence will be slower.

→ Reply

5 years ago, # ^ |

Yes, that's right. I never thought it in such a way. It's a totally bad coding habit.

→ Reply

5 years ago, # ^ |

Oops, It still doesn't work when n comes to 1e6. TLE again. :(

I have changed my approach to save number, now it will output immediately instead of saving it in the array.

Here is my code: 70690087

→ Reply

Mohammad_Yasser

5 years ago, # ^ |

I don't understand. It seems your solution is $$$O(n^2)$$$?

→ Reply