Codeforces Round #618

5 лет назад, # |

← 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

→ Ответить

5 лет назад, # ^ |

+26

should be equal and parallel

→ Ответить

Tschech

5 лет назад, # ^ |

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.

→ Ответить

brurrito

5 лет назад, # ^ |

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

→ Ответить

Tschech

5 лет назад, # ^ |

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

→ Ответить

spookywooky

5 лет назад, # ^ |

What is "equal" here?

→ Ответить

5 лет назад, # ^ |

equal means the lengths are equal

→ Ответить

spookywooky

5 лет назад, # ^ |

← 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.

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

← 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

→ Ответить

5 лет назад, # ^ |

shift while not changing other sides' directions

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

dranikpg

5 лет назад, # |

Why are almost all tasks based on math?

→ Ответить

shashack

5 лет назад, # |

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.

→ Ответить

midnoon

5 лет назад, # ^ |

+16

Visualization for second case is in the description

→ Ответить

SPyofgame

5 лет назад, # |

-17

Thanks problem setters for the problems <3

→ Ответить

danirainy

5 лет назад, # |

+21

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

→ Ответить

algomaniax2.0

5 лет назад, # |

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

→ Ответить

yashgarg2107

5 лет назад, # |

+29

How to solve Div1C

→ Ответить

SHZhang

5 лет назад, # ^ |

← 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

→ Ответить

tRuNgSeO

5 лет назад, # ^ |

+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)$$$.

→ Ответить

AmineTrabelsi

5 лет назад, # |

→ Ответить

Thallium54

5 лет назад, # ^ |

-8

So true

→ Ответить

HanaYukii

5 лет назад, # |

← Rev. 2 →

The Div1B figure mislead me for over 1 hour.

Reading quiz orz.

→ Ответить

reeWorld

5 лет назад, # |

Thanks for the contest! Problems are very interesting)

→ Ответить

utsav_deep

5 лет назад, # |

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

→ Ответить

mango_lassi

5 лет назад, # |

+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.

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

ohweonfire

5 лет назад, # ^ |

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)$$$ .

→ Ответить

tfg

5 лет назад, # ^ |

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

→ Ответить

ohweonfire

5 лет назад, # ^ |

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.

→ Ответить

ame

5 лет назад, # |

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

→ Ответить

michao

5 лет назад, # ^ |

-6

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

→ Ответить

tfg

5 лет назад, # |

+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.

→ Ответить

Lewin

5 лет назад, # |

+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.

→ Ответить

nvmdava

5 лет назад, # ^ |

+22

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

→ Ответить

aswwwanth

5 лет назад, # |

+76

Geometry Geometry Everywhere

→ Ответить

snorkel

5 лет назад, # ^ |

-16

Geometry is good bro.

→ Ответить

snorkel

5 лет назад, # |

-7

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

→ Ответить

NeiH

5 лет назад, # |

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

→ Ответить

madlogic

5 лет назад, # ^ |

Congrats!

→ Ответить

5 лет назад, # |

-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:(

→ Ответить

Mohammad_Yasser

5 лет назад, # ^ |

← 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;

→ Ответить

5 лет назад, # ^ |

It works! Thank you very much!

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

→ Ответить

Mohammad_Yasser

5 лет назад, # ^ |

+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.

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

5 лет назад, # ^ |

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

→ Ответить

Mohammad_Yasser

5 лет назад, # ^ |

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

→ Ответить