Блог пользователя nvmdava

Автор nvmdava, 7 лет назад, перевод, По-русски

Всем привет.

Приглашаем вас на предстоящий Codeforces Round #618, который начнётся в 09.02.2020 17:05 (Московское время).

В обоих дивизионах будет 5 задач. Вам будет дано 2 часа. В раунде будет интерактивная задача. Узнайте о таких задачах в блоге.

Задачи готовили rotavirus, rotavirus, rotavirus, rotavirus, antontrygubO_o и nvmdava. Благодарим MetB, stefdasca, cfalas, gamegame, hugopm, Redux, dorijanlendvaj, imbr92, Noob-ita-coder, 300iq, Rahul, AryaKnight, 244mhq, manish.17, Um_nik, mblazev, pseudocoder10, aryanc403, box за тестирование и бесценные фидбеки. Благодарим MikeMirzayanov за то, что сделал раунд возможным, и antontrygubO_o за координацию раунда.

Надеемся, вам понравятся задачи. Удачи и высокого вам рейтинга.

Разбалловка Div2: 500 750 1250 1750 2000 Div1: 500 1000 1250 1750 2250

Контест закончен, поздравляем победителей.

Div1:
1. EvenImage
2. TLE
3. Radewoosh
4. zhouyuyang
5. Benq

Div2:
1. ntftxdy
2. qsmcgogo
3. ZhouShang0817
4. sarthakmanna
5. nantfaker

Разбор

  • Проголосовать: нравится
  • +288
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +95 Проголосовать: не нравится

What about rotavirus

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

5 problem! may be going to be hard problems :(

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

Sorry for my bad memory, but I remembered that rotavirus and rotavirus were the same person

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +136 Проголосовать: не нравится

Round prepared by Eva? I'm ready to 998244853 modulo

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +19 Проголосовать: не нравится

Missed Newbie testers again.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

Happy to see Educational Round 82 between Round 618 and 619 !!! Back to Back Feb12 and Feb13.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +578 Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +128 Проголосовать: не нравится

There will be an interactive problem in the round.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +34 Проголосовать: не нравится

First round of codeforces 1.0!

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится

Thanks a lot for hosting the contest on a Sunday! Let's make it a regular thing, it ensures a lot of people are able to give the contest.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +94 Проголосовать: не нравится

    I like the varying times of Codeforces rounds, this way everyone gets some chances to participate. If you do it on Sundays only (or mostly Sundays), it means that a lot of people get the chance every time and other people never get the chance.

    Also, a lot of people do OpenCup rounds on Sundays.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Good luck 4 all :D

»
7 лет назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

Rounds consist of 5 problems are of high quality mostly.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

The round to become MASTER or expert not totally sure :D

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -47 Проголосовать: не нравится

300iq makes a round.

Interactive problem:

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

What's the score for each problem.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

the rounds that the number mod3 is zero, are my lucky rounds!

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

how fast the score distribution is!

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +31 Проголосовать: не нравится

A + B + C + D... Dinner.

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

2E/1C http://www.usaco.org/index.php?page=viewproblem2&cpid=419

Second solution is basically it.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

How to solve Div.1 C(Div.2 E) in time limit?

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    notice that it makes no sense to do updates with overlapping ranges. keep a stack with ranges of best updates (keep the sum and the amount of elements) add elements of the array 1 by 1 from first to last, while it is convenient to merge the last segment to the one before it, do so (if the average of both is less than the average of the one before the last)

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

How to solve C?

So many people did that, I couldn't even think of an approach. :(

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Div2. C ??

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

whats the approach to div 2 C ?? :(

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +4 Проголосовать: не нравится

    Let f(f(...f(a1,a2),a3...)=X.
    Following points are to be noted:-
    1. x=0,y=0 then f(x,y)=0
    2. x=0,y=1, then f(x,y)=0
    3. x=1,y=0 then f(x,y)=1
    4. x=1,y=1 then f(x,y)=0.
    Let us consider the jth bit of all a's , then jth bit of x = f(f(...f(a1[j],a2[j]),a3[j]..)).
    In order to get jth bit of x as set bit, we should arrange the elements in such a way that jth bit of a1 is 1 and jth bit of rest of the elements is 0.(WHY? Since f(f(...f(1,0),0,0...))=1).Thus our target is to have the jth bit of a's as follows, a1's=1,a2's=0,a3'=0........an's=0
    Thus in order to get the largest x, we will iterate from MSB(31st bit) and try to find which number have its jth bit as set and rest all have jth bit as 0.
    If we are not able to find then any arrangement will give 0 as answer. My solution 70646858

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve Problem C :<

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

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://codeforces.me/contest/1300/submission/70677064

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Why are almost all tasks based on math?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится -17 Проголосовать: не нравится

Thanks problem setters for the problems <3

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +29 Проголосовать: не нравится

How to solve Div1C

  • »
    »
    7 лет назад, скрыть # ^ |
    ← 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://codeforces.me/contest/1299/submission/70681667

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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)$$$.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

1cc-1.jpg

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

The Div1B figure mislead me for over 1 hour.

Reading quiz orz.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Thanks for the contest! Problems are very interesting)

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.me/contest/1300/submission/70679283

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +76 Проголосовать: не нравится

Geometry Geometry Everywhere

»
7 лет назад, скрыть # |
 
Проголосовать: нравится -7 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится -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:(

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +167 Проголосовать: не нравится

 EvenImage you surely hacked Rating predictor.

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

Can anyone tell me what went wrong with my approach for D? It failed on test 71.

I checked if polygon is symmetric. To do that, I found out the coordinates of centroid and shifted origin to centroid (hence redefined all the vertices accordingly). since our centroid is at origin, for polynomial to be symmetric, if polygon has vertex(a,b) then it must also have vertex (-a,-b).

What is wrong with this?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Can 1D be solved without the condition「there isn't any simple cycle (i. e. a cycle which doesn't pass through any vertex more than once) of length greater than 3 which passes through the vertex 1」?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I am not able to understand problem div.2 D. It would be great if anyone could explain to me...

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +55 Проголосовать: не нравится

My contest rank and overall rank now converge:)

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why does leaving cerr prints in your code give idleness limit exceeded and take so long to TLE? I waited 5 minutes just to fail in pretest 10 :/

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +66 Проголосовать: не нравится

Why does CF-predictor show that Δrating of EvenImage is +687?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Div.2-C was good problem.Nice Contest!!

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

div2 problem E could be solved in Monotonic stack. If one's averge is greater than the previous one, we can merge them. The problem can be solved in O(n). Besides, I want to say that is the the data of problem E is really unstrong. My friend accept the problem in O(n^2). If there are 1e6 number, and first 999999 numbers are 1000000, while the last number is 1, he won't get accept while get TLE.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

>tfw you finish writing C and then your PC crashes

It does crash from time to time but I really hoped it wouldn't happen during a contest...

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Eventually the user whose maximum rating >= 3600 became two. :)

»
7 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

I have solved Div2D/Div1B during practice now using such an overkill solution. It may strengthen the understanding of Geometry, or it may be just useless. The approach seems correct for the most part, except case handling in one specific case that seems too hack-ish to be true. I have to admit, I was shooting for something slightly different where my solution would fail if it did exactly what I wanted it to do. With some accidental bug it gets accepted. I am not sure if the approach is correct but can someone either prove this correct or give a counterexample or some explanation about it?

Here is my approach:

  • For odd-sided polygons the answer is just no.
  • For even-sided polygons, I search through the consecutive lengths for periods of length $$$\boldsymbol{1 ≤ x ≤ \frac{n}{2}}\textbf{.}$$$

$$$\textbf{( i.e.,}$$$ a number $$$\boldsymbol{1 ≤ x ≤ \frac{n}{2}}$$$ such that for all $$$\boldsymbol{0 ≤ i ≤ n - 1}:$$$ $$$\boldsymbol{length[i]}\textbf{ = }\boldsymbol{length[(i + x)}\textbf{ mod }\boldsymbol{n]}\textbf{).}$$$ Or in other words, a sequence of consecutive side lengths of size $$$\boldsymbol{x}$$$ that repeats.

Obviously $$$x$$$ must divide $$$n$$$.

I output YES only if there is either a period of length $$$\boldsymbol{ \lt \frac{n}{2},\;\;}$$$ $$$\textbf{or}$$$ if there is period of length $$$\textbf{exactly}$$$ $$$\boldsymbol{\frac{n}{2}}$$$ and $$$\textbf{no sequence of side lengths of size }\boldsymbol{ \lt \frac{n}{2}} \textbf{ repeats.}$$$ The special handling for $$$\boldsymbol{\frac{n}{2}}$$$ I've done accidentally, but it's necessary for AC.

The 3rd testcase is an example of where there is a period of length $$$\boldsymbol{\frac{n}{2}}$$$ but no sequence of side lengths smaller than that repeats.

In the rest of the test cases. Some test cases have a period of length $$$\boldsymbol{\frac{n}{2}}$$$ and also smaller sequences that repeat. An example is Test: #62. Their answer is NO

This is my solution. I used Main-Lorentz algorithm to count the periods of all lengths by concatenating the side lengths array to itself and dealing with it as a string. It runs in $$$O(n\;log n)$$$ time. I used this implementation from e-maxx, but modified it to only count the number of repetitions of each length without caring about the starting/ending indices. Note that a period of length $$$\boldsymbol{x}$$$ if it exists corresponds to repetitions of length $$$\boldsymbol{2x}$$$. There is a period of length $$$\boldsymbol{x}$$$ if the number of repetitions of length $$$\boldsymbol{2x}$$$ is $$$\boldsymbol{≥ n}$$$ in the concatenated length array (as in, a repetition for every index of the original array).

Regardless of the exact implementation to find the period lengths and/or repeated sequences. Can someone say if this approach is correct? If it exactly mirrors the state of the convex polygon having equal and parallel opposite sides?

The weird case handling of period exactly $$$\boldsymbol{\frac{n}{2}}$$$ is due to this line in the code if(it == M.begin()) break; I break out of the inner loop for repetitions of size $$$\boldsymbol{≥ n}$$$, (originally wanted to exclude $$$\textbf{2n}$$$ and $$$\textbf{n}$$$), but I forgot to break out of the outer loop.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +63 Проголосовать: не нравится

Nobody:

Me: get a successful hacking attempt, only followed by EvenImage's successful hacking attempt

Epic gamer move: get a successful hacking attempt at 1:59:58

»
7 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

About Problem 1C: https://codeforces.me/contest/1299/submission/70683614

This code can get Accepted.

But Why this code get Wrong answer on test 18 when I change eps to 1e-9?

https://codeforces.me/contest/1299/submission/70683551

And I change eps to 1e-10 will get Wrong answer on test 14 .

I thought I wanted to make eps smaller than 1e-9.

Because of 'Your answer is considered correct if the absolute or relative error of each ai does not exceed 10−9' .

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Will there be Editorial?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

Btw, exercise in English language: find everything wrong with grammar/syntax in "how many are there such subsets, that, when removed, there is not any".

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

When will editorial be published?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I have studied Div.2 E / Div.1 C editorial. But I got WA at test case #7... I think it's an overflow but I cannot find it.. Help me.. https://codeforces.me/contest/1300/submission/70754718 (Sorry for bad english and bad code)