21

Codeforces Round #800 Editorial

 2 years ago
source link: http://codeforces.com/blog/entry/103952
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
By Keshi, 2 hours ago, In English

1694A - Creep

Idea: AmShZ

Solution
Implementation

1694B - Paranoid String

Idea: AmShZ

Solution
Implementation

1693A - Directional Increase

Idea: alireza_kaviani

Solution
Implementation

1693B - Fake Plastic Trees

Idea: AmShZ, alireza_kaviani

Solution
Implementation

1693C - Keshi in Search of AmShZ

Idea: AmShZ

Solution
Implementation

1693D - Decinc Dividing

Idea: AmShZ

Solution
Implementation 1
Implementation 2

1693E - Outermost Maximums

Idea: Keshi

Solution
Implementation

1693F - I Might Be Wrong

Idea: AmShZ

Solution
Implementation by Um_nik

Thanks to Um_nik

2 hours ago, # |

← Rev. 3 →  

+27

fastest editorial, epiq round, ORZ

I'm a simple man, I upvote this post

  • 58 minutes ago, # ^ |

    In the consequence, you get upvotes too. Hee...hee ..You're amazing and smart both :-)

    • 22 minutes ago, # ^ |

      ← Rev. 2 →  

      0

      You commented right under my comment. Hee...hee...you're amazing and smart both :-)

2 hours ago, # |

Great, thoughtful problems. Good job.

2 hours ago, # |

Great job! Loved the problems, thank you!

2 hours ago, # |

Is there a proof for Div1C / Div2Е that all edges with min dis are equally beneficial ? I think it is not. In some case it's better to block a way with dis = min if we have another way with the same dis and less count of elements to block in future.

  • 95 minutes ago, # ^ |

    Note that, in the definition of "dis[u]", we are already including the cost of the edges we have to block to get from u to N. So all edges with the same minimum dis are equally beneficial.

2 hours ago, # |

woah! thanks for super-fast tutorial!

2 hours ago, # |

← Rev. 2 →  

+21

I originally posted this under the round announcement but perhaps it's better to post it here:

Thanks for this great div2 round !

I think the difficulty curve was a bit messy BUT the problems were interesting

Here is my feedback on each of the problems because I think it can be valuable to authors to know what people thought about the problems

A
B
C
D
E

119 minutes ago, # |

Can someone explain the last statement in Div2B solution to me in simpler worda? Im unable to understand why we should add r-1 to the answer

  • 115 minutes ago, # ^ |

    ← Rev. 6 →  

    +4

    Let's introduce the "eating" idea

    01 -> 1, that means 1 can eat 0 (the 1 is kinda "eating" the 0 to its left)

    10 -> 0, that means 0 can eat 1 (the 0 is kinda "eating" the 1 to its left)

    Say you consider the blocks of consecutive same numbers

    [0...0][1...1][0...0][1...1]

    Each block can eat the block right to its left. This way, only the last block will survive at the end of the process. So we need the last block to be of size 1

    What they say in the editorial is that they fix the right border of the substring (call it ), now if the char is the first of its block, all the substrings having their left border to the left of will be paranoid (because of what I explained earlier) and there are such left border (we do because we don't want to consider the case as we handle it separately by adding to the answer).

    For example if you fix to be 3, the left border can be or so you have ways of choosing it.

    • 63 minutes ago, # ^ |

      I tried this 'eating' approach (160867965). While I don't understand it completely, it seemed to work with the testcases in the problem and few others that I made. It failed the longest testcase so I'm assuming it's overflowing? I tried to find small counterexamples on cfstress but it didn't help. Could you kindly tell me if my approach is correct or not?

      • 33 minutes ago, # ^ |

        does not prevent overflows.

        • 21 minute(s) ago, # ^ |

          and I learn a new thing. Gosh, I wasted so much time over this. It passed (160900152) Thanks!

      • 24 minutes ago, # ^ |

        ← Rev. 3 →  

        +1

        it gets AC by using long long everywhere 160900072

        If you have any question about things that aren't clear don't mind to ask me

    • 6 minutes ago, # ^ |

      Can you give some problems that uses this eating concept

  • 114 minutes ago, # ^ |

    If it ends on different numbers, then it works. So, all substrings starting from to and ending in need to be counted, and we add the options to .

116 minutes ago, # |

Loved this round!

Here's my solution for div1E (could be the same, but the interpretation seems different). Consider numbers by increasing, suppose we have considered all numbers up to (all the rest are for now). Suppose we now place at an empty position. We define and as the smallest number of operations to get to zero if we start with the left/right relaxation respectively. At this stage we can consider all such that is actually , and add to the answer. Note that initially .

How do and change when going ? If there are no 's, we do nothing. Otherwise, for a position :

  • if there are 's only to the left of , then doesn't change, and new , as we will change to , and reduce to the previous stage,
  • if there are 's only to the right of , then doesn't change, and new similar to the above,
  • if there are 's on both sides, then both new .

These updates can be done via a segment tree with lazy matrix multiplication.

111 minutes ago, # |

I couldn't prove the complexity of my accepted solution for div 1D, which seems to be quite different from the official implementations. (Editorial for the task still not out as i write this)

What I did:

First, note that if is a valid pair, then all such that are valid, as you can simply remove prefixes and suffixes from the increasing/decreasing subsequences.

Next, we can find the largest such that is valid for some in using this. We also note that we can do the same in reverse (i.e. find the smallest such that is valid for some , by simply flipping increasing and decreasing).

Now, we first let , and find the corresponding maximum . Then we do the reverse starting on and find the least such that is a valid pair. Note that here must hold as is not valid. Then we just repeat this process, each time finding maximum for , then finding minimum for . Do this until eventually and we can simply add up the answer using a loop.

This solution looks like and I could neither prove a better complexity nor come up with any construction that leads to TLE, I wonder if anyone can help think of one (proof or counterexample), thanks a lot :D

Code

105 minutes ago, # |

1693A — Directional Increase

I think in the second condition bj==0 should be there instead of bj!=0.

  • 98 minutes ago, # ^ |

    Thanks!

97 minutes ago, # |

Thanks for the superfast editorial

88 minutes ago, # |

← Rev. 2 →  

+4

I ACed problem D at . The adrenaline rush was real, I have never felt the the flow of time like today, I could feel every second ticking inside my mind near the end. Thank you for this round.

D

74 minutes ago, # |

Alternate (I think) solution for 1D briefly:

An array is decinc if there is some such that when you split the array into quadrants based on whether and on whether , then the quadrant with and and the quadrant with and is increasing, and the other two quadrants are decreasing.

For a fixed , we can see that there are basically three choices of we need to consider: two where and are on the same side of , and one where they're on the different side.

The value from this approach is that for a certain , the furthest to the left of you can go is independent from the furthest to the right of you can go. So for each , we want to calculate these furthest left and right endpoints based on the increasing/decreasing constraints.

I did this by maintaining binary search trees containing points where the increasing/decreasing constraints are violated for each of the halves and , moving from to . Unfortunately this part had very high constant factor and TLEd in Kotlin. My C++ solution ran in about 1 second.

After finding the furthest to the left and right you can get from each , we can simply calculate for each left endpoint what the farthest right endpoint we can get is using a linear scan. The overall complexity is (with high constant factor).

74 minutes ago, # |

Div 1 A ~ D are good problems compared to some previous rounds, really satisfied with solving them!

71 minute(s) ago, # |

Can you explain Div2E in a bit more detail? I don't understand why always choosing the maximum dis_n is correct. It seems possible that dis_n can be updated later by dis_{n'}, where dis_{n'} < dis_{n}.

Is it crucial that all edges are length 1? If the edges are not length 1, would a dijstra-like solution still work?

63 minutes ago, # |

In problem 2 & 3, the constraints for n < 10^9, still it gave me wrong answer for using int for input, while it worked with long? Any idea why this happens? TIA P.s i used Java

44 minutes ago, # |

← Rev. 2 →  

+1

There were some weak test cases for problem Div2 C, 160878758 this solution fails for the test case 

1
2
1 -1

yet is still AC.

38 minutes ago, # |

← Rev. 2 →  

+2

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.

Divison 2

Divison 1

If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

32 minutes ago, # |

Great job! Loved the problems, thank you!

11 minutes ago, # |

Div2 problem B was wild...I think the insight to recognize that even if there is one difference, that propagates all the way up the string and "eats" everything before it was a pretty amazing thing to hide.

10 minutes ago, # |

the problems were really well thought!

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK