Codeforces Round #863 (Div. 3)

20 months ago, # |

As a tester...! wait a minute, something ain't right

→ Reply

RollBack

20 months ago, # |

Hope to become Expert again

→ Reply

Salyone

20 months ago, # |

At last a Div. 3, a good opportunity for improve rating.

→ Reply

Math_is_Good

20 months ago, # ^ |

Lol, it didn't age well.

→ Reply

Taanvirr

20 months ago, # |

← Rev. 2 →

+12

Need more frequent Div.3 contests for beginners.

→ Reply

_.baba_yaga._

20 months ago, # |

lessgo..

→ Reply

20 months ago, # |

+38

As a tester, I feel that the problems are very interesting and everyone should participate in this round.

→ Reply

d_sqaure

20 months ago, # ^ |

Just asking to confirm, there wil be no interective problem,right ?.As, in a previous contest there was interective problem and didn't mentioned in blog.

→ Reply

20 months ago, # ^ |

You can trust this blog.

→ Reply

The_Dragon_Warrior

20 months ago, # |

Hope to become pupil today!

→ Reply

fangqing

20 months ago, # ^ |

Hello, can we make frined? Or, we can make progress each other.

→ Reply

sheverlu

20 months ago, # |

hoping for Expert

→ Reply

AVdovin

20 months ago, # |

+11

Is it Div2.25?

→ Reply

Cooper1214

20 months ago, # |

+18

came back here in the middle of the contest, just to downvote. what kind of div 3 is that?

→ Reply

twosat

20 months ago, # |

-25

I don't think this round is too hard for a Div. 3 Round after AKing it, I think it normal and DE is even too easy for their place.

→ Reply

JEE_MAIN_LOOSER

20 months ago, # ^ |

I am not so sure About D .

→ Reply

cockatooo

20 months ago, # ^ |

+43

I like how you submitted C and G in the same minute, with completely different templates lmao. Imagine cheating then bragging online about it ICANT.

→ Reply

twosat

20 months ago, # ^ |

See if I'll be skipped then.

→ Reply

Muhammad-Daniyal

20 months ago, # ^ |

So do you really think that all the people here are little babies and they don't know how a code can be changed after being copied. Such a fool you are!

→ Reply

twosat

20 months ago, # ^ |

I'm not foolish enough to copy one code without editing the template.

→ Reply

Lwchicky0

20 months ago, # ^ |

← Rev. 2 →

it seem unrated.

→ Reply

Harshjain4001

20 months ago, # |

worst Div. 3 contest ever.

→ Reply

Loic_

20 months ago, # |

-20

Nice problems except for F. F is simply a trash problem.

→ Reply

WannaSleep43

20 months ago, # ^ |

LoL, nice problem...

→ Reply

SleepingThread

20 months ago, # ^ |

← Rev. 2 →

For F: You need to get all the simple cycles in the graph,

check if there is exactly one cycle where its nodes degree is 4

And for all other cycles, the degree of its nodes should be 2 except for only one node (wich is part of the main cycle and its degree is 4).

Easy :)

→ Reply

20 months ago, # |

Is there any way to solve "Living Sequence" without digit dp ?

→ Reply

EleCursity

20 months ago, # ^ |

+26

consider the number k in base 9.

→ Reply

MrOtter

20 months ago, # ^ |

+21

https://oeis.org/A052406

→ Reply

jalanprakhar

20 months ago, # ^ |

Can you tell me your digit dp approach?

→ Reply

20 months ago, # ^ |

← Rev. 2 →

First you need to binary search for the number, let's say x.

Then, the check(x) function is pretty straightforward if you know the standard digit dp approach. Just skip "4" at all the order from $$$0$$$ to $$$log_{10}(n)$$$ in x, and do calculations for other numbers as usual.

→ Reply

jalanprakhar

20 months ago, # ^ |

I am really sorry if the question sounds dumb , but in the questions that I've done based on digit dp, we are always given an upper bound , which we dont have here, how can I compute the kth number

→ Reply

TheBhediyaOfDalalStreet

20 months ago, # ^ |

You need to count number of numbers less than or equal to k, that have a 4 in them (or don't have a 4 in them).

This is you recursive function. You can use it along with binary search to solve the problem

→ Reply

20 months ago, # ^ |

Yeah sorry, check the edited answer now.

→ Reply

jalanprakhar

20 months ago, # ^ |

Thank you so much man, helped a lot!! :)

→ Reply

adityasah09

20 months ago, # ^ |

My digit DP solution was giving TLE E Solution

I did binary search for the answer with low=1 and high = 5*k, and in checker function i used Digit DP which tells me how many numbers are there which has digit as '4'. According to me in worst case no of operations : 100 (for binary search)* 50(checker fn Digit DP)*10000 (t) = 10^7. Am I missing out something or is there any way this approach can be optimized. Thanks

→ Reply

Just change endl to '\n'.

20 months ago, # ^ |

→ Reply

adityasah09

20 months ago, # ^ |

Thank you so much for the reply. But why that is happening I am curious to know

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

Isn't it this piece of code takes care of that. Sorry if I am bothering you Thanks

→ Reply

fuwad

20 months ago, # ^ |

std::endl prints a new line and also flushes the output stream, where '\n' just prints a new line, that is the difference as far as I know.( which is why endl takes more time comparably)

→ Reply

Abito

20 months ago, # ^ |

Define $$$f(x)$$$ as the number of integers that don't have 4 in them. Now for each power $$$i \le 15$$$ we can find $$$f(10^i)$$$ which is $$$9^i$$$. Now for any other integer $$$x$$$ we can find $$$f(x)$$$ by going through each digit $$$i$$$ of value $$$x_i$$$ and adding to the answer $$$f(10^i)*x_i$$$ if $$$x_i \le 3$$$ or else adding $$$f(10^i)*(x_i -1)$$$. Now we can do binary search to find the answer.

→ Reply

Wolowitz

20 months ago, # ^ |

We can have 9 digits. So just check if the number can fit if my ith digit was k. Then subtract the weight of it. Do this for every possible digit

→ Reply

SilverWing05

20 months ago, # ^ |

https://math.stackexchange.com/questions/3958169/find-nth-number-which-does-not-contain-the-digit-c

→ Reply

20 months ago, # ^ |

Use digit dp too but got hacked. The time is too tight for this approach. :(

→ Reply

20 months ago, # ^ |

what was your complexity? I used digit dp for E. Time complexity was $$$O(logMX*20)$$$ per test case Where $$$MX=1e18$$$

→ Reply

20 months ago, # ^ |

I set Mx to 5e12

→ Reply

20 months ago, # ^ |

the $$$MX$$$ refers to the upper bound of the binary search... how did you pass samples with setting it to $$$5e12$$$?

→ Reply

20 months ago, # ^ |

When k = 1e12 the answer is about 3e12, so I set it to 5e12

→ Reply

20 months ago, # ^ |

oh mb, I calculated wrongly lol.

→ Reply

20 months ago, # ^ |

I find a litte mistake which leads to a big constant. It's my fault:(

→ Reply

https://mirror.codeforces.com/contest/1811/submission/200755771

20 months ago, # ^ |

oh :(

→ Reply

Hmys

20 months ago, # ^ |

You can look at my submission. I just thought of the elements of the sequence as base 9 numbers, and then converted back. Very short code. Though I could see it being confusing (for non IMs haha) if you didn't think of that way of viewing the problem.

→ Reply

tanmaytaneja2

20 months ago, # |

khatam

→ Reply

Wolowitz

20 months ago, # |

← Rev. 2 →

-22

[.]

→ Reply

serenhade00

20 months ago, # |

How to solve C?

→ Reply

M_A_Noman

20 months ago, # ^ |

← Rev. 2 →

Just check the minimum of the consecutive elements. The first and last element will be as it is. For example

3 4 4 5 3 will remain as it is then the sequence will be min(3,4),min(4,4),min(4,5) and the last element 5 will be as it is

so the ans will be 3,3,4,4,5

→ Reply

asr_003

20 months ago, # ^ |

← Rev. 2 →

what is the logic behind this?

→ Reply

codefforces

20 months ago, # ^ |

← Rev. 2 →

$$$min(3,4)$$$ is the largest value of $$$a_2$$$ that you can pick (otherwise $$$b_1$$$ will become more than 3, a contradiction). It turns out this suffices as well (after copying the edge values).

→ Reply

bad_imagination

20 months ago, # |

G1 was much easier than C/D/F

→ Reply

Pensive

20 months ago, # |

← Rev. 3 →

+24

This round was pretty interesting for me. Found C much harder than D. Although I did copy E after googling from here, had an insane last minute adrenaline rush trying to guess/brute-force necessary conditions for flower graph in F!

Thanks for the interesting problems — will go and prove F now :blobsweat: Update: hacked lmao

→ Reply

rohanmitra2420

20 months ago, # ^ |

same, had to google for E as well

→ Reply

20 months ago, # ^ |

-24

kill yourselves

→ Reply

20 months ago, # ^ |

i stand by what i said

→ Reply

0gnjen1

20 months ago, # ^ |

Woah edgy boy

→ Reply

20 months ago, # ^ |

vužgal bum te ognjene

→ Reply

20 months ago, # |

← Rev. 2 →

+13

chromate00 Orz for the great performance!

→ Reply

chromate00

20 months ago, # ^ |

+11

Thank you! The contest was very fun (Thinking about G was not, but anyways, it was fun)

→ Reply

down_07

20 months ago, # ^ |

+10

Will you make miku's hair blue again after you reach expert?

→ Reply

chromate00

20 months ago, # ^ |

yes actually I have saved the blue version for that

→ Reply

20 months ago, # ^ |

Having saved the blue version, you should start thinking about the purple one :)

→ Reply

20 months ago, # |

← Rev. 4 →

-6

I dont think problem D is a good problem that if you know the conclusion fn*fn+1=f0*f0+f1*f1+...+fn*fn, it will be very easy to solve it, otherwise it's very difficult. Although it's a comman conclusion.

→ Reply

djay24

20 months ago, # ^ |

Can you prove this conclusion?

→ Reply

20 months ago, # ^ |

Here it is

→ Reply

djay24

20 months ago, # ^ |

Thanks, did you solved D? Approach?

→ Reply

20 months ago, # ^ |

← Rev. 2 →

Even after getting to know about this during contest, i couldn't. Like removing $$$(x, y)$$$ from grid creates some regions and i was getting confused in how to divide them such that we get fibonacci squares and that too distinct.

→ Reply

20 months ago, # ^ |

← Rev. 2 →

Since you konw the conclusion then every time you must cut off the biggest square,otherwise you cannont cut it into only n+1 sqaures. Then we can solve it recursively

→ Reply

20 months ago, # ^ |

← Rev. 2 →

Common conclusion ? Ahh you are from china, never mind

→ Reply

JEE_MAIN_LOOSER

20 months ago, # ^ |

Nope. It's not common Sir up until you aren't from china.

→ Reply

Hmys

20 months ago, # ^ |

I think if you draw it up, and look at some examples it is not so bad. Basically if x can be written as sum of distinct even-numbred fibonacci numbers, and y odd ones (or opposite depending on parity of n), you get the answer. And its not that difficult to see if you look at the sample images they provided, and draw some bigger examples yourself, and try to see how the single square can move around.

→ Reply

6_month_challenge

20 months ago, # |

← Rev. 5 →

Why my code tle at test 24 in G1, i think it's pretty decent enough to pass, just running 2 dp's one for maximum length and second one to calculate answers. Please help submission:200780428

→ Reply

AhmedBeruny

20 months ago, # |

for problem C, How can you get output for this test case 0 1 2 1 0 ? the described constrains were incomplete I think.

→ Reply

M_A_Noman

20 months ago, # ^ |

I think there will be no such case as the setter says array b is created from the array a by taking the maximum element between two consecutive elements.

So array b will be in increasing order always.

→ Reply

electric_boogaloo

20 months ago, # ^ |

Not necessarily true, b doesn't have to be in increasing order as the first test contains such examples as [2, 2, 1], [0, 3, 4, 4, 3] and so on. But 0 1 2 1 0 isn't a valid input for our problem either, closest we can get is: [0, 1, 2, 2, 1, 0] from 0 0 1 2 1 0 0.

→ Reply

Zuleen_2061

20 months ago, # |

This is probably my worst-ever performance in a div 3 contest, never felt more let down in my coding...lol!

→ Reply

https://codeforcer.blogspot.com/2023/04/problem-863a-insert-digit-full-detailed.html

20 months ago, # |

I'm curious about there will be how many FST of problem F.

→ Reply

eternal_happiness

20 months ago, # |

Problem E editorial: https://oeis.org/A052406

→ Reply

deepaksolution

20 months ago, # |

← Rev. 3 →

-44

Problem :- 863A Insert Digits Solution is here with explanation and code of it

Problem :- 863C Restore the array Solution is here with explanation and code of it

https://codeforcer.blogspot.com/2023/04/problem-863c-restore-array-full.html

Problem :- 863D Umka and a Long Flight Solution is here with explanation and code of it

https://codeforcer.blogspot.com/2023/04/problem-863d-umka-and-long-flight-full.html

→ Reply

kanishk779

20 months ago, # ^ |

+12

Where is the full explanation in your blogs? Do not misguide other participants.

→ Reply

cosenza

20 months ago, # ^ |

He's just copying YocyCraft's explanations

→ Reply

Nahida__

20 months ago, # |

E maybe little tricky,but others are interestring. And feel the difficulty of D than that of E.

→ Reply

Nahida__

20 months ago, # |

E maybe little tricky,but others are interestring. And I feel the difficulty of D than that of E.

→ Reply

kmparvez

20 months ago, # |

In problem statement of D. Umka and a Long Flight it states,"A checkered rectangle with a height of Fn and a width of Fn+1" means width always greater then height. Then, how can y be y > Fn at test case 3 (3 1 4 , output: YES)? n=3 x & y should x<=5 and y<=3. what did I miss?

→ Reply

djay24

20 months ago, # ^ |

1 <= x <= Fn, 1 <= y <= Fn+1

→ Reply

kmparvez

20 months ago, # ^ |

← Rev. 3 →

I got it. Thanks for your reply.

→ Reply

kanishk779

20 months ago, # |

Can someone provide an unofficial editorial for problem C?

→ Reply

eternal_happiness

20 months ago, # ^ |

Obviously, ans[1] = b[1] and ans[n] equals b[n-1], we can fill the rest by taking min(b[i], b[i+1]), because then, max(a[i], a[i+1]) = b[i] will hold

→ Reply

minhle27

20 months ago, # ^ |

lol this is how you prove it?

→ Reply

M_A_Noman

20 months ago, # ^ |

first and the last element will be in their place as it. Other element will be min(a[i],a[i+1]) for all i=0 to n-1

→ Reply

testmayank123

20 months ago, # ^ |

what about this test case 0 1 2 1 0

→ Reply

20 months ago, # ^ |

It's an invalid input. Consider for 1 2 1. If 1=max(a, b), 2=max(b, c), 1=max(c, d), then b==2 or c==2 must hold. If b==2, then 1=max(a, b)>=b==2, or if c==2, then 1=max(c, d)>=c==2. Both of them will have contradiction.

→ Reply

Leftist_G

20 months ago, # |

Well, E is really tricky and F is a little trash.

→ Reply

Leftist_G

20 months ago, # ^ |

BTW, I think BD is nice.

→ Reply

Chimpanzee

20 months ago, # |

Nice problemset. I like task D

→ Reply

20 months ago, # |

E is classical and F is kind of bad.

BCD are nice problems.

→ Reply

20 months ago, # ^ |

B is the worst

→ Reply

20 months ago, # |

The person who came up with problem b should be beheaded!!!

→ Reply

Raks_splunk

20 months ago, # ^ |

Bro relax lmao(I totally agree).

→ Reply

20 months ago, # ^ |

Tbh, B ruined my contest ... I am pretty bad at grid and these pattern problems. Had to move to C, which felt quite confusing and then somehow i got a simple solution to work. In the end even after solving E, it took me 25 mins to solve B.

→ Reply

20 months ago, # ^ |

Well I solved A, B, C, D but because of the wasted time on B I couldn't solve E in time.

→ Reply

20 months ago, # ^ |

why

→ Reply

20 months ago, # ^ |

my solution to B:

il int find(int x, int y) {
	if (x > n / 2) x = n + 1 - x;
	if (y > n / 2) y = n + 1 - y;
	if (y <= x) return y;
	return x;
}

int main() {
	for(int T= read(); T--; ) {
		int x, y, xx, yy;
		read(n, x, y, xx, yy);
		printf("%d\n", abs(find(x, y) - find(xx, yy)));
	}
	rout;
}

it's quite easy!!

→ Reply

20 months ago, # ^ |

you can shorten your find function to

int find(int x, int y, int n){
    return min({x,n-x+1,y,n-y+1});
}

→ Reply

20 months ago, # ^ |

Wow that's nice

→ Reply

20 months ago, # |

← Rev. 5 →

+21

A: Find the first digit less than d and insert d before it. If there's no such digit, insert at the end.

B: We need to find there are how many cycles between start and end. Let's number cycles from outside to inside 0, 1, 2, ... then (x, y) is contained in cycle min(x-1, n-x, y-1, n-y). Then the answer is the difference of cycle number of start and end.

C: b[1], min(b[1], b[2]), min(b[2], b[3]), ..., min(b[n-2], b[n-1]), b[n-1] is an answer.

D: If n<=1 answer is true. Otherwise, let h=fib[n], w=fib[n+1], we must cut a h*h square from left or right. If we cut from left and (x, y) is remained in the right part, which is a fibonacci ractangle of order n-1, we can solve the problem recursively. Similar for we cut from right and (x, y) is remained in the left part. If no matter we cut the square from left or right, (x, y) can not be remained then answer is false.

E: Represent k in base-9, and add 1 to digits >=4.

F: First for a k-flower, number of nodes n=k*k and number of edges m=k*(k+1). Then there must be k nodes with degree 4, and other nodes with degree 2. If so, 4-nodes must form a cycle of size k (we can take all edges between 4-nodes and check if they're a cycle), and all other edges must form k cycles of size k, and each cycle contains one 4-node and k-1 2-nodes.

G: First calculate prefix-sums of occurences of each number in range [1, n]. We first run dp for max_size[i]=(max size of nice path end at i). Let max_size[0]=0, and for max_size[i], we check for each 0<=j<i, if there're at least k occurences of c[i] in range [j+1, i], we update max_size[i] with max_size[j]+k. Then we let dp[i]=(count of nice paths of size max_size[i] end at i). Let dp[0]=1 and dp[i]=0 (1<=i<=n) at first. Then for each j<i, if max_size[i]-k==max_size[j], we have dp[j] ways to choose first max_size[i]-k elements, and we have C(cnt, k-1) ways to choose other k elements (here cnt is count of occurences of c[i] in range [j+1, i-1], we can calculate it by prefix-sums).

→ Reply

Chimpanzee

20 months ago, # ^ |

+29

Your solution for E is very cute

→ Reply

puspendra_09

20 months ago, # ^ |

Can you explain your intuition for problem E? Thanks also just want to know if it is some type of standard problem.

→ Reply

20 months ago, # ^ |

Because digit 4 is forbidden, we only have 9 available digits, so remained numbers are some modified version of base-9 numbers(012345678 --> 012356789).

→ Reply

Ian_Nepomniachtchi

20 months ago, # ^ |

+16

I am just curious that suppose if there would have been two numbers forbidden then would the same approach have worked...like base-8 numbers. and if yes...then can you please tell how?

→ Reply

Omar.Gawdat

20 months ago, # ^ |

in B can you explain how did you deduce that the cycle is min(x-1, n-x, y-1, n-y).

→ Reply

20 months ago, # ^ |

It's the minimum distance from a cell to the boundary of square.

→ Reply

NerfThis

20 months ago, # ^ |

For problem F, can you explain how you come to the conclusion that there must be k nodes with degree 4, and other nodes with degree 2 ? Are we assuming the entire graph is connected?

→ Reply

20 months ago, # ^ |

That's by the defination of k-flower.

→ Reply

NerfThis

20 months ago, # ^ |

I see. I misunderstood the statement of F and tried to solve a different problem.... Thanks!

→ Reply

ayush_n

20 months ago, # |

How to solve Problem D

→ Reply

becaido

20 months ago, # |

← Rev. 2 →

+55

Is the validator of problem A wrong?

It says $$$1\leq n\leq 2\times 10^5$$$ in the problem statement, but when I hacked with n = 2e5, it showed

" Validator 'validator.exe' returns exit code 3 [FAIL Integer parameter [name=n] equals to 200000, ...e range [1, 10000] (test case 1, stdin, line 2)] ".

Also, I think the pretests are weak too, $$$O(n^2)$$$ and $$$O(n^2\times\log(n))$$$ solution can pass.

→ Reply

20 months ago, # ^ |

you'd better show your generator.

→ Reply

K-423

20 months ago, # |

← Rev. 2 →

+93

What the fucking description of F!

→ Reply

20 months ago, # ^ |

It's not thaat bad tbh)

→ Reply

K-423

20 months ago, # ^ |

← Rev. 2 →

+44

most of my friends took 10-20 minutes to understand what k-flower actually looks like.

→ Reply

Chimpanzee

20 months ago, # ^ |

-34

then most of your friends aren't very bright

→ Reply

K-423

20 months ago, # ^ |

if you think so, whatever, you are right

→ Reply

https://www.geeksforgeeks.org/finding-the-nth-term-in-a-sequence-formed-by-removing-digit-k-from-natural-numbers/

20 months ago, # ^ |

I thought I should determine whether there is a flower in the given graph...

→ Reply

L1gma

20 months ago, # |

Problem E has striking similarity with above gfg article. Maximum users have googled it and copied the snippet of this article as it is without any changes. Please try to filter out those code solutions while checking for plagiarism. MikeMirzayanov

→ Reply

codeX_pro

20 months ago, # ^ |

-18

Wolfester 200768712 Solution can be seen to copy exact helping functions from the above mentioned article. This is a serious concern for the integrity of contest. Pls ban this user from codeforces

→ Reply

rohanmitra2420

20 months ago, # ^ |

+22

3rd party code posted before contest is allowed

→ Reply

vaibhavsinghz

20 months ago, # ^ |

So, will these questions be taken into consideration for plagiarism?

→ Reply

Valenz

20 months ago, # ^ |

Problem E? I dont think so. Div 3 is usually inteded to be more classical, so expect some similar problem ideas.

→ Reply

Wolfester

20 months ago, # ^ |

← Rev. 2 →

This doesn't come under cheating. Using third-party code available before the start of contest is allowed.

→ Reply

anosh21

20 months ago, # |

Catch Cheaters https://mirror.codeforces.com/blog/anosh21

→ Reply

_Hridoy

20 months ago, # |

+20

F is quiet confusing.

→ Reply

20 months ago, # |

-21

make it unrated

→ Reply

harshbutani01

20 months ago, # |

Can someone provide a counter example for this submission?

→ Reply

vgtcross

20 months ago, # ^ |

← Rev. 2 →

Input:
1
7
0 1 2 2 1 0

Correct Output (for example):
0 0 1 2 1 0 0

Your Output:
0 0 1 2 0 0 0

→ Reply

harshbutani01

20 months ago, # ^ |

Thanks for the counter example!

→ Reply

ASHWANTH_K

20 months ago, # |

there is some issue with testcases of A problem.
N <= 2e5
but in hacking phase, i could not generate testcases where N > 10000

→ Reply

Nxxlt

20 months ago, # |

+17

Div.(2+1e-6) round.

→ Reply

procoderomk

20 months ago, # |

One other way to do E is my considering 9 based numbers instead of 10 based(decimal) numbers. Convert k to a 9 based number and change all 4's to 5, 5's to 6, 6's to 7, 7's to 8 and 8's to 9

→ Reply

sundaram__anand

20 months ago, # ^ |

Thanks you StackExchange !!!Hats off for working this out yourself.

→ Reply

jeal0uspengu1n

20 months ago, # |

I was trying to hack A, but getting the following error!

Validator 'validator.exe' returns exit code 3 [FAIL Integer parameter [name=n] equals to 200000, ...e range [1, 10000] (test case 1, stdin, line 2)]

→ Reply

ASHWANTH_K

20 months ago, # ^ |

same issue i am facing

→ Reply

raghavmangla04

20 months ago, # |

-12

i guess this contest should be unrated as solution to problem E was available online and a lot of people just straight away copied the code!! Link:https://stackoverflow.com/questions/54851335/program-to-compute-n-th-number-that-doesnt-contain-given-digit

→ Reply

iiand

20 months ago, # ^ |

Come on, it's Div3. There must be several easy problems in such contests, so for almost every easy problem you can find a " coincident problem "

→ Reply

YENGOYAN

20 months ago, # |

I think there is a mistake in the G2 problem's tests ( 29th test ), in my opinion the answer is at least 1, but the right output for the 29th test is 0. Can anyone explain how is it possible? My submission

→ Reply

nathan_luiz

20 months ago, # ^ |

The answer is probably divisible by $$$10^9 + 7$$$.

→ Reply

Nokemono

20 months ago, # ^ |

← Rev. 3 →

I made the same mistake and it passed G1. Can you try hacking me with the same test case ?

My Submission

UPD: The test-case does not fit the constraints of G1 so a test-case with answer divisible by $$$10_{}^{9} + 7$$$ which satisfies $$$1 \leq k \leq n \leq 100$$$ is needed

→ Reply

cockatooo

20 months ago, # |

← Rev. 4 →

An alternative solution of C, which might be easier to come up with (compared to the $$$(b_1,min(b_1,b_2)...)$$$ solution):

First note that if $$$b_i > b_{i+1}$$$, we must have $$$a_i = b_i$$$, otherwise if $$$a_{i+1} = b_i$$$ then $$$b_{i+1} \geq b_i$$$. Similarly, if $$$b_i < b_{i+1}$$$, then we must have $$$a_{i+2} = b_{i+1}$$$.

After doing one pass and dealing with these cases, there may still be some $$$a_i$$$ that are left assigned. Now we check whether for each $$$b_i$$$, at least one of $$$a_i$$$ and $$$a_{i+1}$$$ is equal to $$$b_{i}$$$. If not, we assign them. If we traverse in increasing i, we assign $$$b_i$$$ to $$$a_i$$$ first, and if $$$a_i$$$ is already filled we assign to $$$a_{i+1}$$$. In optimization terms, we make sure all constriant are active.

Finally fill the rest with 0.

This always works if the input is correct.

solution: https://mirror.codeforces.com/contest/1811/submission/200724266

→ Reply

ID3

20 months ago, # |

+11

So, problems B and D ruined the contest, right?

→ Reply

aqua4

20 months ago, # |

Are submissions going to be re-tested with successful hacks?

→ Reply

jackylova_fan_fan_fan

20 months ago, # ^ |

Yes

→ Reply

jackylova_fan_fan_fan

20 months ago, # |

So hard div3，(sad).

→ Reply