and we're live
hi everybody i'm as always streaming to
youtube and twitch later you can
re-watch everything if you miss the
stream today's day of
athcudder grand contest
f number four d6
this one so we'll start with problem
the strider you can already like read it
like
the statement is very short so you can
read it now
most likely i will go for around four
problems maybe five if i'm lucky and it
will take from two to three hours
standing into dimensional plane facing
north
go one meter in the direction he's
facing then turn x degrees
counterclockwise
isn't this about greatest common divisor
if 360 or something like that
i think so i think it's enough to just
compute gcd with 360.
but before that let me ping everybody on
discord and twitter
hi lakshay have you ever thought to
teach data structures and algorithms i
kind of do it
sometimes on youtube
on youtube i have a lot of educational
videos
i didn't produce any in past month but
i want to you know make that more
frequently
from very basics if you want to
learn from very basics there are books
and courses for that
right now pashka twitch
he has a weekly he has weekly lectures
on
algorithm data structures if you want
something like that then
go follow him he has everything on
youtube channel as well
it's p maverick
because versus division two going on
oh i see well
yeah division three not division two
all right here let's try even without
opening editor
this gcd with 360.
i would say then starting from the
second problem i will be serious
so the answer will be 360 divided by
this gcd i think
hi rex balum what's up
okay accepted so let's just move on i'm
pasting link
to the second problem in the chat
and now the fun should begin
right we have a grit a by b
and everything painted white
choose vertical or horizontal if we
choose vertical insert one row at the
top of the grid
which is horizontal insert one column
right
now that's my slide from
uh from facebook hacker cup because i'm
making a video about the finals
all right they are saying that
every time either we add a row above
like that maybe multiple times
this is one so maybe in two first
operations we will do this
then in next operation we add a row to
the left
this way we expand the grid to the top
and left assume the grid eventually has
c
horizontal rows and d vertical rows find
the number of ways in which the squares
can be painted in the end
oh then paint one of the other squares
black and the other squares white
right every time
every time when i add a new row or
column
one of those i paint let's say that we
painted red
maybe i painted this painted this
painted that they
tell us what's the size the initial size
of the grid and the final size so i know
how many rows and columns i added i just
don't know the order
and i don't know which exactly sells
find the number of ways in which the
square can be painted in the end
from 1 1 to 2 2
okay and then there's a lot of ways
all right
yeah please use english in the chat
sorry about that but use english
how old is ericto i think there is even
a comment for that
i'm 26.
right or left so did they say left to
instead of right or something like that
oh right and you're right sorry
so actually this
drawing shouldn't be like that
it's like this
that's now quite ugly drawing
i guess you get the idea anyway
let's draw the whole grit
and its corner some part of it
was there at the very beginning
let's say that i don't know this is the
initial part
i cannot touch it
then in some order i added the remaining
rows and columns to the right and top
every time when i did that i colored one
square
example order can be this one
two three four
five and six
well for sure i know the number of cells
i need to paint
also this is impossible
impossible that in this row
within those four cells two of them are
painted
because just even if this is the first
operation there will be just one cell
here
if first i did this then in here i have
only one cell
so at most one cell here at most one
here and so on at most one here
what are other conditions
at most two here
i cannot achieve this
can i i can't
can we also discuss in the chat i
yeah you you can you can
say your idea
you can trace the path of the corner
but you know we can think indeed about
that maybe it's a good idea
the corner of the grid will move in some
way like this maybe
and this corresponds to adding rows and
columns
then every time i need to paint some
cell
like when i move to the right here it
means i'm painting one of those cells
i'm not sure if it helps me
what is the statement
well i pasted link in the chat so you
can just you know
scroll up but you can also pause the
video now and read it
let's remove yellow for now because i
don't see how it's helpful
if there is something here what does it
mean
if there are two things in the same row
then at least one of them
came from the column
also in every row and every column there
must be at least one
cell painted
if two of them are painted like here
i will say that the or even more
then the leftmost one was painted by the
row
like this or like that
if they tell me
if they give me some configuration of
cells
sometimes there are two in the same row
or column
then in every row i find the leftmost
cell
and i say this was painted with a row
within a row in every column i find the
bottom most
actually let's then mark it yellow
here we have a collision so this is bad
if and only if this thing will
mark all the cells then we're good
but that's not the only requirement is
it
maybe something should be monotonic
what rating would this be you can
measure my time and compare with code
versus problems
i don't know how to compare ratings
guard jose please don't repeat your
questions
i'm not focusing on the problem
what are the limits
three thousand three thousand
stream delay please check but
you mean bigger than 10 seconds
how do you know how big the delay is
right
if there is if this cell is painted
and it's the only one in this column
then apparently this whole column
is painted so they move square like that
is this possible
i wonder if this condition is enough
that if in every row i mark bottom most
yellow
in every row i mark left most blue and
those are this joint and
i mark this way everything
okay another idea i need to count the
number of ways
to paint cells if i just
investigate in what order i add columns
and throws
that was gupta's idea from the very
beginning
maybe let's paste this one more time or
just let's
let's use this drawing
when i move with corner to the right
then one of those cells is painted
then they keep moving
and let's say every time i move i
multiply the number of ways by the
number of
the number of cells from which i choose
and also from this this
this this and that
do i double count something here
i think i do
if instead my path looks like that
so it turns this way
and the painted cells are let's say like
that
that's possible this is counted in both
scenarios
oh
this is possible but anyway
red cells are split into two regions so
i can almost
say that i want to draw
i want to choose free red cells
somewhere here for its
free red cells somewhere there
that's kind of it and there should be
just
some polyline that splits them
let's say that you are yellow or not
green
and if some red is here can
i still split i can
this is possible scenario well it's not
possible because two reds are in the
same row but now it's possible
when is it impossible like this
and that's now it's impossible
green cannot be left top from red
this is also impossible
this possible right then
i can go column by column choose where
green should go
let's say that nothing is yet decided
you're about broke why why did it broke
what i did it break
oh on this skirt i gave a long wrong
link
thank you vanilla for
noticing a mistake
if the stream is in bad quality for you
you can watch on youtube instead
this is the link
if you're if you're just joining the
stream you can pause the video now and
you can read the statement
or just google extension or grab it from
the chat
if i'm choosing that in the first column
green goes here
or let's say it goes there what should i
do
then i need to
choose red somewhere here let's say
there
and again here somewhere there
then i choose the next green nothing
happens i choose the next screen let's
say
here nothing happens
if the first green was there then i
would just say that
red is somewhere here if the next green
is here
then the reds would be here and there
if this is every next column
then i will have dp over the current
column and max green
so max row kind of what is the topmost
row in which i put some green
whenever i increase it then i
say that reds
that's i should put reds here
but this will be cubic for every
pair c and max row i will iterate over
position of the next green
i think i know how to speed this up
enough
when green is here two tools two rows
above
the previous green then
in this case for red has four
possibilities here and there
so i will multiply the number of ways by
times four to the power
y four not four five so just
c to the power of two
this two is actually the difference
difference between this position and
this position
right and now if i don't finish with max
row being the very
topmost row like that then at the end as
well i need to
say that reds are anywhere here or
actually anywhere here
should be good can you will you cover
all grand contests
i'm trying but you know it takes a lot
of time
let's code this i will first
implement cubic dp make it work for
sample tests
and after that i will speed this up to
quadratic
i'm using windows and this is virtual
machine with linux with ubuntu
because i can only efficiently
code in linux i need to close
some stuff from previous contest
because in my ide there are like tens of
tabs open
i'm just hitting ctrl w a lot of times
right
again the plan for today is to go
through four or five problems from this
contest
link is in the description and in the
chat
we are now solving b extension
i said that this is dp of column and
max row
abcd is given
a is related to c let's call them
height 1 width one
i do it with two
and i will need to use modulo
model of this somebody asked the
question earlier this means you need to
print the remainder of the answer modulo
this value
if it was modulo 10 it would mean print
the last digit
this is some helper function
all right we start with dp of what
with one we go by columns
so now we need to decide about this
column
and max row is just height one minus one
this is the width of that smaller grid
from which we start
now i'm looking at column number this
and this is the number of already
occupied rows
for every column
for every max row
i tear it over the position of green in
the next
column
this is basically iterating over the
next row to take
p of c plus one
and now this is not the full code
because as i told you we need to
multiply by this
by what by the column id
to the power of difference if we are
above the previous max row
okay what is c is discounted from zero
zero one two three four when the ec is
equal to four
then i should indeed take four
rather than i don't need to do minus one
um power
of c to difference
this can be done in logarithmic time but
i don't need it right now
linearly many times multiply by a then
you will get a power
what do we print at the end
i will use dp of this last
thing max row maybe multiplied by
something
if the topmost green was on
roulette's second row from the top then
there is one row left and i need to put
red somewhere there
so that's in that case that will be
exactly
that many possibilities
i think it's this
like if you don't know what's going on
but still watching
you can it's very easy to start with
programming
and also to start with algorithms
if you're watching on youtube in the
description you will find some useful
links
all right i have overflows because i
don't use my functions
this shouldn't be just plus equal
because then indeed will get
overflows
387 right
everything works now this part is cubic
of course because
you have four loop times four loop times
four
that's cubic in total
but this part inside should be easy to
optimize
the pfc plus one and whatever x
is equal to dp of c
maybe this way every next thing
is extra multiplied by c
if green is below then it doesn't matter
there are two parts when we iterate up
to
max ring
up to this actually then
there is no difference so we don't need
to multiply by anything
and when we go above
like that then we have this difference
max crow what did i want to say max row
i can't i'm combined max green with max
row
right still works
this part is just prefix sums i need two
two prefix of something and this is
green
to some prefix i'm adding the same
constant
oh i messed up why
this is maxwell
so i take the sum
oh i don't use green oh then it's easy
to the same cell i added this value
some number of times
this should be equivalent
yep it's equivalent and now
this is something else
for every max row iterate above
and use this as i go with max rose i
will maintain
some kind of sum
and i will hear say some
added to the sum dp of me
oh this is me
i don't want that
and i want to replace this with just
itself
this should be equivalent to what i did
here
then obviously sum is multiplied by
c to count for this power
everything previous multiplied by
this and also add myself
i believe it should be in this order
because i added myself
here let's try
nope too much
can you just check the freezer now and
give me a hint
there is an editorial for sure try that
neil completed all problems of division
3 in 18 minutes
good for him
why is it not equivalent if i skip this
then this still works
if i skip this
doesn't work
no
this works this was some old line wasn't
it
oh here i should use the sum not me
all right now it's just quadratic
we can try the max test
yeah very fast
division three are for noobs
everybody was a newbie some like once
accepted we're moving on to problem c
shift
link goes in the chat oh yeah
there is this annoying thing in virtual
machine
that in google chrome this text it's
actually a rich text when i copy it with
ctrl c
i cannot paste it in windows
i can copy a text like this if i ctrl c
hit here then in windows i can paste it
but actually in chrome this is not
simple text it's a rich text and i
cannot copy paste it
what i need to do is i need to copy
paste this here
to just any text editor then from here i
can cut or
copy paste
right see shift
flagship style of other problems you
have some crazy process
analyze it and understand what is
possible there
gbm somebody answered you already that's
maybe not well
look
i'm not logged in maybe i am
don't i have some links here
okay in twitch but also in youtube there
are frequently asked questions
there is also link in the chat go read
that it includes
information on how to practice maybe i
have this comment
practice no i need to make it
let me real quick do it you can think
about the problem
all right
the link works now and this link
includes
if you're a beginner with competitive
programs handbook all right so
chat in the future if there is a
question how to start or anything like
that
there is a comment exclamation mark
practice
can you tell by writing if you don't
know english why are you watching
streams in english
you have a link read this this is the
answer in
written form read the link
but also streams aren't a good source of
knowledge if you don't know english
let's analyze this crazy process we have
a string
if on if position you have zero and on j
position you have one
i must go before j must be i must be
smaller
remove the j f character meaning
remove one and
insert it to the immediate left of this
what is the second value
okay how many times we apply the
operation
i believe that they just said that a one
can go before some zero
that color gives you a headache and
it has some heart problems right
the point is that they are hard indeed
right
this zero at the end will be useless
then one operation is to move one
somewhere to the left like here
maybe it's good to think that there are
zeros
they create some sequence
initially ones are somewhere let's
decrease the size of ones
the ones are somewhere but i can move
them around i can move
a one to the left this is just the
initial string
i didn't change much
i can say that positions but there are
zeros
and positions between them are numbered
like 0 1
2 3 4 and 5.
and once in every position between zeros
there can be some number of ones
in one operation i shift
i move a one to the left
so this sequence can be treated as
one one zero zero two zero that's the
number of ones on every position there
are two ones here
zero ones here and one operation
is to decrease some value by one and
increase some value on the left by 1.
the question is how many sequences i can
get with
at most k operations
i believe that this will be easy now and
also
you cannot make more than square
operations so
my first line of code will be something
like that
i can minimize k with n square
or actually the length of this sequence
square no for every value i know how
many times it can move by one to the
left
so i can sum this up but basically every
one it can
jump over every zero only once
so that's some limit but the upper upper
limit is n squared
what do you use for writing on screen
like that
this is one note and i have a drawing
tablet
there is it is answered in faq as well
lol and at table for benq what bank you
solved everything
nice
very nice banquet is much better than i
am
so what can i do about it i'm trying to
solve those problems as well
we will go from left to right or maybe
from right left is better
and it will be dp out of position and
maybe not the p
if i'm somewhere and let's say i moved
from the right
i would say that it will be dp of
position
and the number of items i moved from the
right
and the number of operations already
but that's just too slow
both moving and k can be up to n square
this would be
n to fifth power this is
that many states
and maybe even more maybe more
transitions
what's the question how many sequences
what can we get or what
find the number of strings yeah
i okay then if i want to get some string
with some persians then i want to get
there in optimal number of operations
so if at the end there will be one here
it means i just moved
one from there that's one thing the
other is
from this i can get some i can make some
new
sequence if and only if every prefix is
not smaller
for example this is achievable
because for every prefix the number of
the sum of values here is at least equal
is small greater than or equal to the
previous sum of values
the sum of values here is free
previously it was two
it still will be n to fifth power
that would be dp of position
sum of values so far
and the number of operations there
damn it
how can you continue tirelessly in such
difficult problems what do you mean tire
realistic
it's the stream is less than one hour
the real contest is two hours or five
hours
that's not tirelessly when you go to
school you need to think for several
hours
so that's this is nothing
what do you think is better vim or other
text editors like ginny
everything is fine because apparently
every everything has some user base i
used ginny
ginny's very convenient for me
genie has some features that veeam does
not
so veeam also has some features that
genie doesn't
can a person learn from reading the
solution and editorial yes
of course you can
it's not enough just to do it you need
to practice
solving a problem yourself as well
i'm thinking
oh the sum of values in my sequence is
actually limited by n
i created those values by counting once
so the sum of blue values
doesn't exceed n then
dpf position and sum doesn't exit
n and it's enough to move every
one by one all right
this is enough everyone
it wants to be somewhere at the very end
so i can just do it
with one operation
even this was already cubic
now let's think for a moment about the
easiest implementation
and cubic is fine
what exactly i want to do
limit was 300 right
yeah k is huge but
i already understood why it can be
minimized down to 300 maybe even 150
no 300 like if there is single zero and
then a lot of ones
and each one can move like that so the
limit is actually 299. i can
minimize k with n minus one
size of this sequence will be the number
of zeros okay can be minimized to the
number of ones
this way if i have the number of
ones and zeros maybe i have can have
something to fourth power complexity
because the worst case will likely be
for equal number of
ones and zeros and 150 to fourth power
this is fast enough
maybe depends on operations types of
operations but
time limit was here three seconds
instead of two
so i think this is good enough
i think
we need to do transitions
and i'm thinking about those transitions
moving something to the left
this was my first idea the moving from
the right and
maintaining this dp this is how many
how many operations are already started
and possibly finished this is the number
of
ongoing operations so i moved something
from the right but
i don't know where it will land
when i look at the number like let's say
now i'm deciding about this zero
i iterate over its new value
and i will update those dimensions
accordingly
it will be end to fourth power but
should be
should be good enough
the transitions will be very simple so
with prefix sums
i should be able to get it down to cubic
if needed
what about repetitive case what
repetitive case
i cannot get rid of the hundred that you
can calculate the number instead of
enumerating
did i ever want to enumerate dp is
always about counting not
enumerating can spell polish can smell
polish accents
i'm not surprised
i think i have quite thick polish accent
counting is enumerating in brackets
loops
what
calculate the number instead of
enumerating
so you mean that calculate with a
formula instead of for loops
but what do you do with the input you
have some sequence in the input
i always thought you were romanian
i don't feel offended that's fine i can
be romanian if you want
if you list all cases you count and
you enumerate the same synonym in this
case
okay so in math it isn't
i mean count the number versus
is can mean whatever but enumerate
specifically says that you want to
consider each one separately right
gbm not i'm not an expert on turkish
streamers or anything
i will create that blue sequence the
blue sequence was the number of ones
between every zero
if zero i have some
i'm going once
if it's one then increase the number of
ones
after the last zero there are some more
ones
i can print this sequence
so on samples i will check if
it's correct
it's some technical stuff
zero one one
between the before the first zero there
is zero ones
then one then one all right
good night good night to gbm
good luck in your journey
fine
should i move from the right
i guess so
let's maybe reverse this sequence
and now it is the
can i have cubic memory 27 million
all right it will easily fit in the
memory limit
let's start with dp of zero zero zero
equal to one way
this means tp of position ongoing
and operations
operations cannot exceed k and k needs
to be
minimized down to something
minimize to the sum of values
in blue
what about not reading k here at all
just at the end i will read k and it
will used
i i like this idea
but i will use and no
maybe
let's sum up the blue values
this is different from the final k at
the end i need to
to do read k this k just means
i i could basically answer queries about
different k but this is maximum
reasonable k
for every position
i have blue of i here blow of ice what
the the value here and now i can
decrease it so i can move stuff to the
right
or i can increase it by taking stuff
from the left the stuff that i already
started
new value here will be at most the
current value
plus ongoing i need to iterate over that
i'm going up to
okay
if five ones are still moving to the
left then it means i started at least
five operations
so operations cannot be smaller
and now the not cubic part
iterate over a new value here
what am i doing
i believe that this will not exit okay
but let's check with an assert and what
do i do
dp of i plus one no i'm going
new value minus blue i is that good
if i increase this by two
oh if let's say from five
the blue i is three new value is five it
means i put
two ones here
can this be smaller than zero
well this is ongoing minus new value
plus no this is by definition greater
equals here
this and operations plus how many new
operations i start
i start that many
if blue i was five but i want it to be
free
it means i take two ones and i move it
to the right
and finally we
read k
let's call it allowed
dp of what n
i'm going must be zero i need to finish
all the operations
and i let's call it open like operations
and i guess i should have completed
everything module yep
4 and 14 nice
this will again give me an overflow
so
[Music]
plus equal here
brackets are good here good and that's
solved there
add self is my helper function to add
one value to the other
modulo mod because i care about the
speed i will avoid the module operator
here
when you add two values you can do this
one one three all right
let's test this on kind of a max test
i'm not sure if it's a max test but
should be good enough
the number of counts is exactly 300
segmentation fault
305 outer bounds which one is out of
bounds
the sum of blue values should be hundred
five
wait oh
i'm not reading k k is whatever let's
say
123 that was invalid input
first goes the string then k
60 milliseconds
50 milliseconds all right
maybe that's not even max test maybe it
can be five times slower
still i will pass
and during app solving i can just submit
without checking a max test like this
during a contest i would check to avoid
penalty for wrong submission for runtime
errors
i don't minimize the menu of
what k end allowed
now here i iterate it up to a billion
and instead of giving me time limit
excited i just got segmentation fault
because i tried to access
element in an array which
exits the array size
is that coder beginner contest good if
your code versus rating is
1800 plus
you can try and see if problems are too
easy for you
accept it cool
i think that the last two problems in
beginner contest will be educational for
you so it's fine
maybe just absolve and just do e and
f but practicing some easy problems and
those increasing your speed is perfectly
fine
problem the secret passage you get
limit
you get link in the chat
is at color grand contest almost just dp
no i've let's check in editorial but
maybe
one of those two problems it wasn't
supposed to be solved with dp
c was dp okay b and c were both db
so that's my end to fourth posi solution
we can improve it to end cubic by
careful implementation
i agree those are some simple interval
operations if you split into cases of
new value greater than blue i
or smaller then just to some
interval you're adding something right
yeah prefix sums maybe diagonal prefix
sums if you
affect both operations and ongoing
all right secret passage
input is the same but without k given
the binary string of length 300 find the
number of strings
but the thing is that this limit
suggests again
dynamic programming and i hope that they
didn't
give free dynamic programming problems
in a row that would be
bad
remove the two characters at the
beginning of s erase one of them
and reinsert the other somewhere in s
if i do the operation and over two times
if i go possibly go for the whole string
then i will what remains is
some n over two characters and they can
be in any order
but sometimes i can choose to insert
again at the beginning then i will
remove it
maybe let's think about it like it is
allowed to remove the two first
characters
if i don't need one of them we can
remove both
i don't know if it will help
but it is possible
if i have a b c d
c e i can
remove two first characters and a
i insert somewhere in the string in
particular it can be the very first
position
like that then i again remove the first
two characters
insert one of them again it can be the
beginning
then i will have
those four characters
let's then just assume that it is
allowed to remove first two characters
but at least one of them needs to be
removed
then if i wish to continue
at least two of them so here
at least one is removed here at least
two
is removed unless i wish to stop earlier
at least three and so on
everything else will be just reordered
i will have this string plus this or
this character
this or that this or that
and maybe some other combinations can i
save those
two i think it's possible
if i if i decide to remove them both
then it's possible
i can achieve it by removing those
inserting one of them again then looking
at those two
removing that and inserting you
somewhere late
then looking at those two and doing
something
can i save
those three
i don't think it's possible
can't we upload 1080p low i can't upload
you if you mean that it's hard for you
to watch you can watch on youtube i'm
streaming them at the same
there at the same time
chat if you see somebody writing about
this
just use white to to comment youtube too
it will give them a link
i cannot save those two that's for sure
because my very first operation is to
remove one of them
i can save those two i cannot save those
three
i can save any combination any two of
those except for those
then that
removing those two is very special
i mean saving those two is very special
because
when doing this i needed to save one of
them so it would be
here than those two
yeah i cannot
save all three characters
okay
i can't
i hope that maybe we can say for every
prefix some
there is just some number of allowed
survivors
and then that would make problem a
little bit easier
but that's not the case
for in this prefix of length five
because we're talking about survivors
let's
choose conditions for survivors there is
at most one survivor here at most two
there
at most three here and in this prefix of
length
five three survivors are possible like
this one this one this one
unless it's those three i cannot save
all of them
if it will be somewhere later then yes i
can
save all of them by inserting something
from the left
between them
time to get better encoding yeah i
the process if the some process is
described in the statement you need to
understand what it can do
and my idea was my first idea was
maybe it can do everything
with the it can save any set of elements
at the beginning
assuming that's those two those
that set of conditions is satisfied
and of course then i would also need to
take care of
moving characters to the right but
i would maybe be closer to the search no
my idea isn't correct
the fact that i cannot save the three
characters here
it messes up my plan
do you practice other than on streams
rarely i try to stream what i do but
i do competition some competitions not
on streams and videos
i was you are saying youtube has better
encoding than twitch
okay because encoding is also name of
some technique
but i agree youtube has better encoding
than twitch
it's a trade-off it has bigger delay as
well
i think so twitch
is well
it's complicated never mind i will not
go into that
um
so
to save those two guys
i need to waste half an
operation i would say when looking at
them one of them gets erased forever
the the other one is inserted here or
maybe here
so that's like
after two operations i will reach this
position
not that this is why we have trouble
here maybe i need to think
where did i go
up to what position with what number of
operations
i don't know if that will be dp
maybe
but the position or let's say index i
the number of operations already used
such a pair it will tell me how many
elements from that prefix i
erased so also
how many upper how many characters were
saved and this
moved to the right if i moved something
to the right
then that for the next two values i can
save
both of them even when needed
by inserting one so
by inserting one guy next to you
then taking both of them and saving the
first blue
so this dp or maybe not even dp but a
pair
high end operations if
let's say we have prefix of link three
and i know there were two operations so
they were remo
they removed two characters one
character moved to the right
i know this number of characters that
are are moving to the right
all right that's something
then i will know if i can save two next
characters or not
if i decide not to do so then i just
take them both erase
i erase both and one of them
gets moved to the right
right fine
but they ask me
what's the number of final strings
find the number of strings
do you think i must have do you think i
must have a university degree to be a
programmer
i don't have a university degree and i'm
a programmer
so no you're asking a very easy question
if you tried to google your question you
would find
like thousands of cases where somebody
without a degree
became a programmer but studying helps
i studied for a few years and it helped
me a lot i learned
much i learned too much i met new people
both of those things help in career and
in real life
i mean non-career
the characters from the input matter a
lot
if some character is repeated a lot then
it doesn't matter which
which of them i decide to save
let's say that i make just two
operations
so from let's say that from first four
characters of the string
let's try to expand this a b c d c e
and then there is a a b d
d c this long string
i this i
move one of a or b to the right i move
one of c or d to the right
how many strings can i get this way
if i move d then obviously it doesn't
matter where exactly here i
insert it but something trickier is that
when i move a and b it doesn't matter if
i insert this a
and b let's say
a and b goes they both go here
or they both go here
that will result with the same string
and that's very tricky
maybe this is not a good example should
be more like that
say this is the string i from this i
remove c and move a to the right
from this pair i remove d and i move b
to the right
to the right
then those two positions
that are kind of the same
maybe i should look at the sub string
and check if i have enough characters to
make up this sub string
and then putting this set of characters
on the left or right it doesn't matter
but that will be too complicated with
multiple places where i can put stuff
are you monogamous no why are you asking
in particular monaghan is from united
states
and i don't think i have that kind of
accent
oh sorry
when did he start to stream live isn't
that displayed on youtube
the stream is 1 hour and 30 minutes
yes i'm from poland
if somebody is joining the stream now
the problem is
you're given a string in one operation
you take first two characters you remove
one of them and the other you move
somewhere in the string possibly again
on this first position
so maybe we remove a and we take c we
insert it
let's say here whatever
we do this operation many times how many
different strings can we get
the length of the given string is up to
three hundred
you should prioritize giving time to
chat considering solving such hard
problems i don't know what you mean
you mean i should spend more time
talking with the chat or less time
oh there are just zeros and ones why did
why did nobody remind me of this
well that's for sure a huge difference
only zeros and ones well
it's not a b c d and so on just a and b
are zero and one
when i'm done with a prefix
what will happen is i move some number
of zeros and some number of ones to the
right
i'm quite certain it will be just some
allowed interval
like if i move five items to the right
maybe three or four of them can be ones
and the remaining will be zeros
then there is some suffix of the given
string
i don't touch this suffix it's it's
there plus
i can insert there some number of ones
and zeros
how many different strings can i get
it's some sub
problem for us to solve let's focus on
this
there is some string binary string
and i have say
three ones and two zeros this is how
many items i need to insert there
how many different strings can i get
that's the question
this length of this is 10 plus i insert
five
more this will be the string i'm
creating
let's call this as this is s prime use
new version
and
can i get a one here yes i can but for
sure it will be one of those
if if this is zero then it's better to
say that this is
this zero and this one will be more
flexible in the future
so after some prefix
there is fixing prefix of
s prime it corresponds to already being
done with some prefix
of s and
i used some zeros and ones here
so it sounds like dp
of let's say this is j position j here
in string s
j and the number of ones and zeros used
are remaining
the sum of those three values it will
tell me
the current position in string s prime
but actually i don't
need to know this current position from
this
i consider adding zero or one if it
matches
the next character in s then i use it so
i increase j
by one otherwise i change one of those
values by one
that's very simple cubic dp
for the problem you're given a string
and you can insert there some number of
ones and zeros
how many strings can you get
i could run this thing only once though
so it's not that
for every prefix of the given string i
will consider separately
i will consider doing something in the
prefix and then
run this thing i cannot do that
unless i take the input string i move
from the right
this will be pre-processing so j
is going from the right end
of string s i can create s prime from
the right
ones and zeros is the number of ones and
zeros used
starting from we will here start from
dp of n
and zero zero and
then after this cubic processing
i will look at my input string i will go
from the left and consider this thing
with operations
and for every prefix after i'm done with
that prefix
i can ask the pre-processing about this
suffix and there
if i want to insert two ones and three
zeros then
what can happen there something like
that
but
i will have over counting
maybe this prefix and
extra five zeros and four ones it can
create the same thing as this
the ic prefix i meant suffix as this
suffix and two ones and one zero
how can we get better dynamic
programming practice
solving dynamic programming problems
you're welcome
less time to the chat uh regarding
techie
chan's previous message i don't think i
spent more than 10 percent of time
talking with the chat do i
anything smaller than let's say
25 percent of the stream should be fine
tuesdays aren't a big problem anyway
because it's a hard stream
so not a lot of people
keep watching when it's easier stream
it's a bigger problem that i get tons of
questions
i appreciate love of from india but
you're repeating your comments so you're
spamming please stop
you don't need to waste my time by
requiring me to answer
to something like love from india come
on
my tummy is hungry and it makes sense
maybe we should go from the right
and forever string s prime
what about trying to understand
the longest suffix for which it's
possible to create this string
hmm
can you please bring tourists to your
channel to share his experience his
experience
is same as everybody in the top he
solved
either thousands or tens of thousands of
problems that's it
you can let him know that he's welcome
to my channel
after removing some stuff for prefix
the information i will have is that
five zeros and seven ones survived
and i move them to the right
and actually i had a limit that it is
some
some interval is possible
if
if five zeros and
nine ones can survive
but also seven zeros
and seven ones then i claim that as well
six zeros and eight ones can survive
something like that
maybe for every number of zeros i just
care about the maximum number of ones
that can survive
i can always remove an extra character
being the first or second
so if a one can survive from the prefix
i can put it at the very beginning i can
erase it while
the second character just moving to this
first position
so yeah if a zeros and
b ones can survive then also a minus one
b
or a and b minus one can survive
it's a proper definition for every
prefix to know for
some number of surviving zeros was the
maximum number of surviving ones
right now the second dp when moving from
the right
it maximizes maximizes no
it minimizes used prefix of
s
maybe the same can be achieved with
longer prefix
but i'm not trying to do maybe then we
will avoid double counting
by asking hey if i have five zeros and
seven ones
and this prefix
my question is actually different oh
when the length is the same but the
number of ones is zero and zeros is
different then i will have
i will get distinct strings
because the number of ones is different
all right
maybe there is no over counting maybe we
are done here
this will be cubic preprocessing
on string s from the right
then from the left i will have for every
number of surviving zeros i need to know
maximum number of surviving ones
that's actually quadratic dp
but doesn't hurt to make it cubic maybe
it will be a
bit easier to code for every position
the number for every number of zeros and
every number of ones
this boolean value whether it's possible
or not
that i'm done with this prefix and this
number of zeros and ones survived
then asks suffix of s
okay if you if i'm asking about you and
you
get that many surviving ones and zeros
what's the number of possible strings
i need to think one more minute about
over counting something
taurus doesn't talk in his channel i
mean
then apparently he doesn't like to talk
about like stupid stuff like how to
practice
like it's public knowledge how to
practice
so why would he be more talkative on my
channel than on his
i understand why people from the top
don't want to
waste time on answering questions that
are answered already thousands of times
in code verses
because yes it's a waste of time it's
just repeating some stuff
this tp
is fine then it uses this one
this is the number of strings of length
this plus that plus that such that if we
try to use as
short prefix or suffix of s as possible
then we will get
up to here
what about strings
that
can get longer
as short as possible
but maybe we can use
more characters from us should we count
that case
no we shouldn't all right
let's try that we will start with
pre-processing
from the right
goodnight csk
always a lot of people are watching in
india and
now it's what plus four hours 11 p.m in
india
or 20 past 11
a reasonable time to go to sleep
this is well let's reverse
the string i wanted to do preprocessing
from the right
so no reverse and to do it from the left
we start from this that's the number of
ways
a number of ways
let's just copy thank helper functions
for module
only itself will be there
actually in c i had a better function
faster one
this is dp of
position the number of zeros and ones
nothing to write here
really
wait didn't we use as big prefix of s as
possible
right
yes we do let's get for a moment back
here
[Music]
whenever possible we use character from
this because we want
th those should be left for later
because they are more flexible
dp of j100s is the number of strings of
length this plus that plus that
such that if you greedy try to make take
as many characters from s as possible
then you will take
that many now how will i use it
when i get here after the first three
characters
this suffix is not touched i know that
some characters from the left have
moved here then can i just use dp of
this length so strings that will
use this length
what if i take 0 from the left and i put
it here at the very beginning
and it matches this character so this
actually should be longer by one
then i will count it here
the code will not be very difficult so
i'm even though i'm not sure about the
correctness i will implement it
nor should i analyze the sample test
no coding will be easier
i have string of length i plus zeros
plus ones
all right d and now i
append one more character
and either it matches the position i or
not
this is for matching case for not much
in case
if this is zero then one wouldn't be
much i would need to take
some extra one coming from some
somewhere else
i'm doing something wrong yeah it should
be
this
because that's not length of my string
that's next position to take from s i'm
now taking
creating kind of a longer longer string
like that maybe let's do it with
condition that
i plus ones plus zero smaller equal and
it will be a bit faster
i don't need anything longer than that
because that's the length
all right
yep looks fine in particular
dp of n zero zero this should be one
because i can create exactly the same
string
answer didn't fail so that value was one
maybe i shouldn't name every dp dp but
because now i will need the second one
and i need another name
because we reverse as
back to the initial form
we go from left to right and
i care about the number of zeros and
ones
that the boolean thing
by default everything is false but this
one is
true
once and zeros they will not exceed that
zeros goes first
this is process described in the problem
i can take first two characters
remove one of them and the other one
move somewhere to the right
so most of the time we move by two
can of i plus two
zeros once
is this possible can i increase the
number of zeros
i can if one of you
one of removed characters is zero
similarly if at least one is one
all right but that's not the only
possibility maybe i moved one of zeros
and or once exactly here
to match it with the first character
so this can be possible as well
and what could be the point of that
well is that
true
if i have let's say one on the first
position
but i move one from the left here i
remove one of them and the other i have
okay i can just remove the first
character if something was
there already
okay so that works
in particular the first character can be
removed because i just
removed the first two and i saved the
second one
but maybe it's unnecessary and maybe
even it leads to over
counting
okay so i can remove you
i can save you as well
and what do i do with all those values
oh if not ken of
i can remove the first characters but
only in this case
if the if two last characters
or right now two first characters if
they exist
if this is possible should i use
something from
pre-processing
dp of n minus i zeros and once
i'm so much unsure about this
six
all right instead of eight it should be
eight
here i think something more is possible
i think that we can move by one and
change something like
a zero into one i think
like that
how to do it i if this first character
is one
and i have at least one zero
zero is moved from the left i put it
here
i have zero one i remove them and i take
one
and move it to the right
symmetrical case
still six
is n minus one good here
what about up to n
maybe i should move up to n nine
that's bad yeah
i'm not
maybe i'm very far away from correct
answer
time to analyze the sample test
oh do you see what i'm saying
my answer is always too big by one maybe
i'm just counting empty string or
something like that
okay let's test this theory by
submitting
all of that i don't care about this
debug
it's related to my compilation flags and
i don't need to change code to submit
this
just i have two compilation buttons f8
and f9 you can see the full command here
at the bottom when i hit with f9
it's compiled with the local and it's
defined somewhere here
that only if flag local is set
then debug line is triggered and it will
actually
print something right right who write it
neil thanks
i'm doing at cutter grand contest 46
and i wanted to maybe end the stream now
but
because of rate maybe let's do one more
problem
didn't know neil's dreams aren't
do you never visit code versus he
streams once every few days
very often we've commented like
editorial for
division two or three contest
should i understand why it's too big by
one
am i counting
empty string or what
let's analyze for much
shorter string
itself should be counted
from one one that's correct
isn't it
oh yeah okay so here i zero zero
zero one zero
i one okay so for
s input one my
program found two cases and the answer
one is correct but only after i
subtracted one
do i count empty substring
this means that i start from the very
beginning
that sounds good
i think that this needs to happen
dpf00 i needed that at the very
beginning
because i start from that i start from
empty substring and i build the
preprocessing dp on the top of that
and yeah that's good but then it's it's
unnecessary
one and i keep adding this thing
so let's try with this fix remove
subtracting one let's just try to print
answer
see if it works on samples
it does then
i copied the sample test by mistake
it will be compilation error
it is compilation error
tell something for greedy problems what
should i tell them
all right abcd done
let's try a permutation cover
also the is it again dp
yeah how could they give
b c and d in a row all about dynamic
programming that's very bad
i don't want to maybe it's fine if two
problems
in the contest are about similar topic
especially if they are not two
consecutive problems
but here bcd at least b was
very different but c and d are almost
the same statement
both about doing operations on the
string
counting number of strings that can be a
result of some process
and it's up to 300 so both are dp but
also b
is dp i don't like it
all right permutation cover you're
you're getting a link
find the lexicographically smallest
sequence p
satisfying every
element in p must be from 1 to k
the input is the number of occurrences
of every value
there's a continuous sequence of k that
contains the term
if the input is two free two for free it
means that there are two ones
four twos three freeze
i need to create the sequence out of
those
and this is the output
indeed there are four twos
fine this is condition number two
the condition number one just means that
there are no other elements
it could be just skipped it it should
say this and there are no other elements
for each term there is contiguous
subsequence of length okay
all right
this is this these are elements from 1
to k
some permutation of them then when we
look at this
2 it's also a part of such a thing
it's here when we look at these two
it's also part of such a permutation
free also part of such permutation blah
blah then
finally this
the first k elements for sure they need
to be
a permutation like that
because the first element must belong to
something
then
there are three possibilities the next
permutation is this
the next occurrence or it's this
or it's this
because two must belong to something
in the first case it means exactly that
the first element is equal to this one
determine whether a sequence p exists
we don't need to count this time
hello hi atra atarva
how are you
why are you using caps lock how can one
improve on greedy problems
oh i see that you used capstock
previously too
okay what about not using uppercase when
not necessary
and i answered your previous question i
don't know i joked about it right
okay here you go solve greedy problems
you're welcome
let's focus on just answering yes or no
if every element occurs the same number
of times
then that's easy because i can just make
one two three one two three one two
three one two three
i believe that the frequencies can only
differ
twice if there is 10
then the biggest value can be 20.
that's because
is it true
the first k elements they create the
permutation
maybe it's better to talk about it
without spaces
and now three consecutive elements are a
permutation
something like that
all right then first three elements are
permutation
when we look at fourth element it must
belong to some permutation two
the right most possible case is this
or maybe like that or maybe like that
um
right what about this in k consecutive
elements
let's say that case 4 and or 5 i'm
looking at those five elements
there cannot be three equal values
if this is value x
this is value x and this is value x then
this
x doesn't belong to any good interval
being a permutation from 1 to k
because it will for sure contain
some other occurrence of x
observation
at most two occurrences same value
among k consecutive values
consecutive and
in first k there is at most two
second k at most two at most two and at
most two
there is something about rounding then
at the end but
roughly for every k values
only two of them can be equal
and another observation is that
every twice k minus one consecutive
values there must be every element
otherwise the middle value it doesn't
have
an answer it lacks some value
the middle element in that interval
if something is very low frequency then
yeah maybe it's possible to
put it in the middle of such an interval
let's investigate
one two three four five six let's say
that six is very uncommon
i can mess up this part doesn't hurt
but then
what about this element well
this is perfectly possible
this space is just for for
making it easier to read
yeah it is possible that an element
occurs once every
2k minus 1 positions
i can repeat this pattern a lot
note which but that can convert every
entered comment to lower case
i mean maybe there is one that bans
every
every person who uses uppercase or
uppercase like at least twice that would
be useful
there is nice
in this case can i
have many occurrences of the same value
i'm kind of forced for this there will
be some trade-off between elements
that occur very few times and a lot of
times
if i have an element that occurs almost
never
then i cannot have anything else that
occurs more than some
some other element
that was a sequence for six being very
rare what about six being very common
then i have can have this
right for every k plus one
elements i will have two sixes
two divided by that
assuming that the whole sequence is
divisible by that
here that
okay any x
but this is mutually exclusive i believe
hmm
i have some permutation
now let's say that five and six i want
them to be quite cool
then i will put them at the very
beginning
and i can repeat them here
five and six
this is kind of
interval where everything from one to
five
appears twice maybe i will build
intervals
and in each interval some elements occur
once
some elements occur twice
is that good enough
it would make things much easier
after this if i want to without putting
this bar
do something here so that it would use
the fact that this is a permutation
then i would need to put one two and
three here in some order
but apparently this interval it shows me
that one two and three they should be
rare
if i wanted to use more ones then i
would put a one
here after some reordering
like one would be here and it would be
there
yeah like that
one of my favorite youtubers is
streaming on twitch
is it me well thank you
okay is what
this would mean oh and
i will need to answer not only yes no
damn it
but if it's yes and no then looking at
this
i want a lot of tools so i would create
two one three two
okay the frequency
is this two three four two for free
i created this interval it's good and it
uses two twos
so the remaining count is this the
remaining requirement for every value
then those two i want them to appear a
lot
i can make it like that
and 0 0 0. then i remove a bar and we
have a good sequence
it's actually the same as
their sequence but
i guess that it's a coincidence let's
try
another one
three two three two right
one and three are
more common so let's use them more one
three
then two four then one free again and a
bar
the remaining counts are one one one one
so one two three four
right let's compare it
they have one two three four and then
one free did i mess something up
one three one two
oh yeah they they have for them the
split is
into different sizes
they have this kind of split i still
don't know if it's good enough to look
at splits
i hope
to check if
the sequence of counts is possible i
simulate the whole process
every time i look what is most frequent
maybe multiple elements then i take all
of them
i put them then remaining elements then
them
again like here i saw that
one and three should be more common so i
put one
three remaining ones then again one
three and that's my interval
that decreases counts a little bit
i think that this process
always decreases everything by one and
some values by two
instead this will work
if and only if
max is equal twice mean or or smaller
than that
i think that this is my requirement
that there is a solution
if it is like two and four
yeah that's possible too
if the interval case is correct
then and i need to find
lexicographically smallest
then it's about whether possible to put
one here
then a bunch of stuff
it was it is always some xyz
then remaining then xyz
xyz will be sorted like one two three
remaining also will be sorted
if possible i want x to be one if not
then two if not then three and so on
similar stuff for y and z
so gets
the sequence of counts
remember that after your operation this
must be true
in particular if you use twice this
value that will be bad because this will
get down to zero and other values will
still be positive
that's bad not all but indeed we can use
one it's okay to use twice
this value now can we use two
we cannot we cannot in this repeated
process
but can we use it in remaining
without using anything else in those
and yes we can
then we try to put three here
and is that allowed let's see
i will use one twice so this will remain
two i use once this will remain
is now i try to put three here
actually i try to put one here but
that's not possible then the best
the next best is free yeah
that will be left
the last value is four i need to do it
because this prefix must contain all the
values
and then i repeat value from the
beginning
is this better than one two
three four and one two
that depends on what will happen in the
next interval
that's bad
i cannot greatly make a decision about
interval now because
i don't know what's optimal in the next
step
if in the next step we will start with
one
then sure use this and then here it will
be one it will be better
i think that we have this decision only
in this strange case where
everything is sorted
if we have let's say in the prefix one
three then two four
then one three then it's obvious that
two should go here if possible because
it will make the prefix better
three should go to the middle if
possible
so we don't we aren't sure about our
decision only in this
case when it's optimal to use 1 2 3 4
up to k and then again some prefix
but that should be the only case
advice to approach counting problems
this stream is one huge advice
i solved today three problems about
counting so
watch that watch the past two hours and
that's how i solve them that's your
advice
i'm not aware of good pieces of advice
for
like learning math or programming here
algorithms
in math is there something like good
advice about geometry problems
just solve geometry problems
one then if possible two
if possible free
i will need to here repeatedly answer
um
i need to answer something like this if
the first two elements are 1
2 can i finish it in any way so it would
be a good interval
good interval means that the remaining
counts are solvable
and i'm not saying if 2 is repeated or
not or if
one is repeated or not
just this
then i can for this check iterate over
the prefix of that
what's the complexity the
total length will be thousand
i will first have something to like
fifth power
but then i will improve
i can download tests if necessary
i mean my solution will be first very
slow
but i want to implement it to see if it
works at all
and if yes then keep improving
if i chose a few values already
then to check if this is possible
let's say that more of them let's say
that k6
and here i chose values one two four
and there are there is some sequence of
necessary counts
if it's one to four three is not present
so apparently all of that is in that
i mean three is apparently here so this
is that repeated prefix for sure i don't
need to iterate over
anything if it's increasing though like
this
then i don't know and maybe this is
like the split and one two are repeated
then three four five six
are ones then one two again
but in case of one to four i already
know that they will appear
twice three will appear once
five and six i can decide about them the
for each of them
if it's equal to maximum let's decrease
you by two
what about looking at those counts
finding menu finding maximum
and if this is the case like three two
three two then i can do
everything no i cannot
in this case minimum can be decreased by
by one only
and maximum doesn't matter by one or two
for every sequence of counts i will just
find
off maybe in constant time even after
understanding what values are here there
some requirements
what needs to happen if the sequence of
counts
is like this
then everything can happen let's
remember
from every value i will subtract one or
two
it cannot happen that i will subtract
two from everything
and that's i that's the only requirement
and after that this condition must be
still true oh here i can do
anything i cannot break this condition
if there is 4 here
then that's something i cannot decrease
4 by 2.
if i do that it will no if i decrease
four by two
then i need to decrease sixes by two as
well
so that's some condition
best way to calculate blah blah i mean
i i don't think it's a good strategy
strategy for me to
read problem from the chat and switch
completely to that problem
for quality yeah youtube
you need to use maybe i should work on
the comments
eric tattoo channel on youtube is for re
streaming at the same time
and on youtube you can decrease the
quality
no my mouse is that not
um
does it matter that i cannot decrease
everything by two
if i do that's kind of
allowed it just means one two three four
five one two three four five that's like
two intervals in one i would say that
it's fine
but also then just one two three four
five will be good
and is that the best thing i can do
well one two three four five and then
one is also
equally good just can be only better
maybe not
and let's think about this hard decision
of one two three four
one if i detected that
one two three four is a good
prefix
then i can finish this with one or one
two one two three one two three four
so should i for each of those cases run
the whole algorithm for the
remaining part to understand what will
be there
so i might need to choose
between one two three four one two three
four one
this
the last one is kind of unnecessary
because it's just combination of
two sequences from one to k
depending on each of those something
else will happen here on the
right for each of them
i can run the algorithm maybe just for
this single interval
so i would know what to put here again
maybe without knowing how to finish it
but the first four values i would know
and are the first four values enough to
distinguish
what if this is two one
three two three four
and this is one two three four
if it's like that then those prefixes
are
same
maybe it's trickier to compare
between something like that two and
three it will be the same if this is
free
so maybe this is three and four this is
four in both cases then we have
one two here one two three here possibly
we repeat
three and maybe four
i don't see how to distinguish that
and i need to take a p so short break
i will be right back
i remembered something in this case we
know exactly how it will finish
the fact that three four peak values are
in the prefix it means that
exactly those will be repeated so free
far at the beginning means exactly this
four at the beginning mix means exactly
this
and you think so
if there is this kind of tie
then it doesn't matter which one i do
if instead this was just let's say three
and then one two four
and three so
similar to make a tie
this would need to be one two four
is that even possible three then one two
four
okay three matches
you then one two four
three
okay so this is possible
and then the question is if remaining
part is smaller than one to four
maybe this is just always the best
putting one here sounds superior
because often you will be able to start
here again with a one
and that will beat everything else
when can it happen okay if it's possible
to put a one here then this one wins
because
one beats a two on this position
a bar actually should be just one
character white
it'll be better
right one beats everything here
and you cannot put two ones there
because that's not
a permutation
i mean well it would
just mean that this is an interval so
this is great
whenever we can start with a one
we're good when this is not possible
when we don't have enough once
after this
if we have counts let's say like this
say four eight
four seven seven
then i need to use this value twice
and this value just once so
the value here will be 2.
in this case it will be two and
one three four five
and the two two is repeated because it
was maximum
still sounds quite good
it won't be if i put put it like that
then this is five
maybe not because two and four also can
be doubled
so it would be like that two four five
one three two four five
[Music]
if you're if anybody is joining now i'm
solving this problem you can google
permutation cover
the add color permutation cover or you
can
grab link from the chat
what was the previous count for this to
happen
before that counts must be equal to
6 and everything else appeared i used to
just once
from that by using one twice i decreased
to this situation and now
this is just one
[Music]
i can
if something is not minimum then i can
use it twice
if one is minimum then it might happen
that i cannot use it
but after this
possibly this too can also cannot be
used
if that was the case
for for this i would have
four five one two three four five
two and one two three are so rare that
from now on they will always be used
just once
maybe that's important from now on
if you cannot do something
if you cannot use something twice it
means that
you will need to forever use it
once maybe same goes the other way
if you need to use something twice you
will keep using it twice
if this is the case that something is
twice the other value then yes
forever those are used once this is used
twice
what if it's almost like that
what if it's four and seven
then i
can use both ones i
can't use both twice
i can use one one basically this cannot
be used twice
this is one this is whatever
let's say star means whatever
star
for this first element forever it will
be used once
this other element it can be used once
but then forever twice
if it's four and six then for now you
can do everything except for one two
so this one two three four better
by any chance
well we have particular examples so
let's analyze it
if we use one two three four then we'll
get
counts remaining counts like that
four four seven eight
and five one can be used twice
along with four and five
then those two elements
and then those that i used twice
so this is better
right i think that this is the best
possible
prefix
no what's the comparison between one two
three four and
one two three four one two which one is
better
can does this make sense for my example
i think so with one and two
two will be decreased once more no
that's impossible
i need to take
i need to think about another example
but we're comparing
those two
the first one may stands a chance only
in this case
then it must be two free
can you use
one or two in pessimistic case maybe you
need to use free
why did they type 4 here
i don't know that was a type
we are considering this case then
this will be free or above
i guess that this is the best then this
is second best third best
and kind of far best but actually it's
this so the
quality are there and low
i mean low priority let's say i will try
to use them in this exact order
and those two are really the same so
let's say that this is
not allowed
let's let's try that then
do i have a solution and do i have a
fast enough solution
quadratic
okay hundred thousand thousand would be
nice to have
k times length square
i will choose element by element for
every interval
[Music]
i will want to know if this can be
finished
let's just start coding
should i number them from zero to k
minus one
yeah i will do it
if max is if this condition
isn't true at the very beginning then
already we can say no this must be true
will i maintain them big and small
they want to function
don't like typing max element so helper
functions
you get max
greater than this
in this single case
minus one
is this c plus plus yes it is
but i'm warning you that i'm doing
something advanced
so if
if you're not doing competitive
programming you will not find this
stream useful
on first days i do i do coding
interviews so that's easier
and more useful in life
very educational streams great work
thank you
it should say minus one no i didn't read
k
should say minus one only for the third
sample
it did
while we are not finished
[Music]
choose elements one by one
first check if it can be one
some partial interval maybe
i don't like this name let's call it
partial
this is all increasing
we will try to use this value
not really after i have one and three
if i have one free then do i want to put
far here
no i don't i want to put two here
and that would represent repeating 1 3
at the end
so always try to put here a very small
value one actually cannot be used
repeat many times for every volume
if not used
then do it if possible
check if okay
if okay used values true and break
from the for loop this one
i will remember how many elements i used
already here
if i didn't add anything new then break
otherwise i added one new element
this difficult part remains
after that
feeling partial will be easy if
everything was used
then this is the case i was working on
here i say that we prefer
one and one two one two three
and so on but i need to do some extra
logic for that
to check if after using one everything
is good
then after using one two and so on and
so on
let's call it tricky part else actually
it's not tricky because that's the case
where let's say i used
one two four out of five numbers from
one to five
then for sure here three and five will
go and then again one two four
so that's very easy
now this i added three and five
now let's again add one two and four
or let's finish but
i think i need to change this
this would work if this was
partial but maybe i will add those
values
at every moment i prefer
to finish now
one two three
oh this will be resolved
easily what happens is
one two three four this prefix actually
just means that i used
one here
and everything like that i will choose
the first value
and after that if possible let's cut it
here
then one two if possible cut it here
this order will be automatic
if i used two and four
i try to cut here if that's possible
then
blah blah blah cool
so this should be good
then this is impossible
one two three four why didn't i cut it
i think that i do nothing here and i
will leave it as
one two three four one two three four
one two three
four yeah and i will just print elements
of partial
but a case like one two three four one i
consider by
kind of cutting after one and saying
that okay now goes
now go non-existing elements in my
prefix and then
partial contains just one in this case
then two three four
then partial again should be good
check if okay
check if i can do something here
and say that this element is used
twice
everything not here i
allow it to
[Music]
maybe
search good max to check that i didn't
mess up
something after partial steps this is
possible right now
try to say that this value goes twice
and basically everything else if your
maximum
decrease by two otherwise otherwise
by one
those already i want them to decrease by
two
those unused
by two only if you're maximum
wait but something is already forbidden
when i have one
two four
if i have prefix one two four i cannot
say now that three
[Music]
gets used twice but if that was possible
anyway then i would use one two three
four so i'm good
i don't need to care about order of
values
get max for everything else
up to k nothing and doesn't exist
if not in partial
temporarily let's do this
but i need to move it back
how is it called valley
if not used
if this only then it decreased by two
else by one and i need to now check if
oh i made stupid functions because they
work on count
let's use a hack very ugly one
and okay is whoever
get max is smaller equal
twice get me
and not declared sure it should be k
okay
that's not good i think that i'm not
updating count
and everything increased by one
one three two four
it's not good first one is
two three one two three then two and
three two
i should cut after two oh yeah
at every moment try to cut exactly here
after i added a new value
and here obviously break if you didn't
find anything good
but also now consider this current
partial
the question is do you really need to
decrease all the remaining maxima
or am i fine without it
if used of x
by two else by one
if good of new count
then break i stop after this moment
this will also be just good
let's call it is good
a bit better naming
maximum
not exit doesn't exit twice minimum
two one three two two three one two
three
for a second one two three four one
three
one two three four and four third this
all right now
one more thing is
can it happen that i should just use one
two three four
and instead i'm trying to use something
bigger
let's do if powershell
of zero is greater or equal one
if it's not zero
can it be empty
or maybe just this i should do at the
very beginning
but one is better
this in our thinking process this
corresponds to not starting with one
something like two four and then one
three
then two four if instead of that i can
just do one two three four and stop
nothing gets repeated that's better
actually if i have one three then
two four then one three then still 1 2 3
4 is better
i should maybe just consider 1 2 3
4 and check if it's lexicographically
smaller
um
consider one two three four and adjust
it
can it happen that something was already
zero hmm
can't if he's good
then
compare that with the partial thing
if partial is any kind of prefix of that
we're good
if not then this is better
he would be better
then i think that i should just do this
or just fill it with everything from
zero to n minus one so make just first
this case
it should not change anything here
i think it doesn't what's my time
complexity
there are thousand elements in total
for every position
i try k values for each of them i do
something in complexity k i think it's
thousand times k
square and then that's fast enough
let's try
nope
the stream is 3 hours 20 minutes that's
not
i don't want to write a brute force
anything like that
should i no just
let's find a test
model of my child i think it's argo
human
but i don't think it's that
good i will try other chairs in the
future
manage to solve my puzzle with dp using
your videos
that's good i don't know what your
puzzle was but
it got their tests
that will be at quadrant contest 46
agc 046
problem e in
test 1 0 1. txt
that's a big test no
maybe 0 6 it took 1 milliseconds
no
11.
no each of them is really the same
what recovered okay
that's not this problem it's d
is it wait what what
problem am i solving
why am i in file d dot cpp did i solve
did i solve the secret passage
did i overwrite my solution
oh yes i did okay never mind
so i got a good test
this is what my program finds
this was what was zero six
go to out
what's going on
my program is using only values from one
to five
do you use 5 instead of case somewhere
what's going on
did i copy the input wrong to 5 and then
there are so many values
oh i didn't copy the first digit
okay that takes place
the mystery how to compare them
conveniently
i don't want to do it with diff
the prefix is the same
i keep using one one and then something
yeah this is the same
to my out
should i break this in some way
i see messages now from two minutes ago
about
copied copying 5 rather than 15 sorry
about that
sometimes when i'm very into something i
forget that i stream
uh yeah andreas i'm so
to jump one two three steps it doesn't
sound like a puzzle it sounds like
a competitive programming problem
but i'm glad that dynamic programming
helped you
hmm can i here
replace every space into new line i
don't know how to do it
the same
the same
still the same what about suffixes
suffixes look the same okay
those are the differences
lines around 392.
let's go there
what was the first difference 392.
this
what did i say three twenty twenty nine
i can't speak
it's indeed different
i print
one
i want to understand intervals here
there is stuff up to 15
2 from 9. i guess that's repeated part
then i would guess that this is new
terrible or maybe
repeated will be from two to nine no
like that
in my program we have from two to nine
that's repeated then we have values 1 10
11
12 13 14 15 then repeated that
my interval starts here in their
solution
repeated are
what
i think that my solution is wrong guys
this isn't split into intervals as i
thought
it's not like i thought i thought that
we will have those separate intervals
because otherwise i did
i didn't have any idea how to solve a
problem
and yeah this is i think example of
case where something else is better
we use the fact that previous interval
ended with some values
so we can use some other values here
for giga ram is enough to practice
competitive programming your phone is
enough
the web development i don't know about
that competitive programming doesn't
require
any power computer from 15 years ago
will be good enough
okay quick look at the tutorial the
beginning to see if indeed it's
completely else
but i think i lost here
step one the maximum element among ai is
at most twice the minimum element
fine
all right they use this is observations
i did
this is an observation i didn't have so
that's it i lost my solution is wrong
like completely wrong well
played cyberpunk yet and no i heard it's
backed so i will wait half a year and
then play
and it's not that i have a lot of free
time right now
and you didn't even see my rate oh thank
you senator gunn for the rate i
have a good stream so i now announce it
from three
minutes ago uh what's what happens is
that
i believe that i don't get the message
no i got the message from four minutes
ago sorry about that
yeah i was quite focused sadly that's
the very end of the stream
like and this minute i'm finishing
that's some unfortunate timing but thank
you for the
rate
why did i not participate in the last
global round on cut forces
i didn't have time or something like
that i didn't remember
it's not default for me to participate
in every contest there is
maybe it's more like by default i don't
participate if i have time and i want to
then i do
you got your discord server back from
monaghan yes
it's now my server but he's a lord he is
a moderator
is how is it called day of code
advent of code is this is it still
happening
i think it is
and here you go i'm right i'm writing
like i'm kind of how is it called
forwarding the rate
thank you everybody for watching this
stream today
i the past half an hour or one hour
however long i tried to solve e that was
kind of wasted because my solution is
completely wrong
it's not that i now buy i don't want to
now just see in the editorial solution
and implement it
i just need to look at some observations
here understand it and spend
additional half an hour or an hour to
solve it
prime agent for the win
if you say so then that's a good trade
larry larry streaming advent of code
right now oh
then if i saw that message earlier i
would
rate him but now too late
right
okay two seconds thank you everybody
join
the discord check the calendar
and yep see you next time on thursday i
will do easier problems because
those from coding interviews bye bye
welcome so many people how are you doing
we're trying to figure out how to solve
a problem that i'm not very good at
solving
thank you by the way welcome by the way
how are you doing
by the way
chickens also great times right they're
just great great times
you doing well blue hawk welcome and oh
dude
oh hey welcome oh my goodness there's so
many of you guys there's just so many
hey hop into the theater okay we're
doing advent of code
day 13 part two hop on in
we got ourselves lots of room
hey lots of room in this aoc season okay
aoc and i are here just trying to figure
everything out so why don't you get a
little popcorn all right
you can get some coconut oil you can get
what you need
and get in okay but i know there's a lot
of you i'll have to you know aoc is not
falling out of her seat
she's just very excited okay she's very
excited young lady
and she can't help how excited she is
she does she has no