Codeforces Round #863 (Div. 3)

13 months ago, # |

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

→ Reply

RollBack

13 months ago, # |

Hope to become Expert again

→ Reply

Salyone

13 months ago, # |

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

→ Reply

Math_is_Good

13 months ago, # ^ |

Lol, it didn't age well.

→ Reply

Taanvirr

13 months ago, # |

← Rev. 2 →

+12

Need more frequent Div.3 contests for beginners.

→ Reply

_.baba_yaga._

13 months ago, # |

lessgo..

→ Reply

13 months ago, # |

+38

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

→ Reply

d_sqaure

13 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

13 months ago, # ^ |

You can trust this blog.

→ Reply

The_Dragon_Warrior

13 months ago, # |

Hope to become pupil today!

→ Reply

fangqing

13 months ago, # ^ |

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

→ Reply

AVdovin

13 months ago, # |

+11

Is it Div2.25?

→ Reply

Cooper1214

13 months ago, # |

+18

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

→ Reply

twosat

13 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

13 months ago, # ^ |

I am not so sure About D .

→ Reply

cockatooo

13 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

13 months ago, # ^ |

See if I'll be skipped then.

→ Reply

Muhammad-Daniyal

13 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

13 months ago, # ^ |

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

→ Reply

Lwchicky0

13 months ago, # ^ |

← Rev. 2 →

it seem unrated.

→ Reply

Harshjain4001

13 months ago, # |

worst Div. 3 contest ever.

→ Reply

Loic_

13 months ago, # |

-20

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

→ Reply

WannaSleep43

13 months ago, # ^ |

LoL, nice problem...

→ Reply

SleepingThread

13 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

13 months ago, # |

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

→ Reply

EleCursity

13 months ago, # ^ |

+26

consider the number k in base 9.

→ Reply

MrOtter

13 months ago, # ^ |

+21

https://oeis.org/A052406

→ Reply

jalanprakhar

13 months ago, # ^ |

Can you tell me your digit dp approach?

→ Reply

13 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

13 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

13 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

13 months ago, # ^ |

Yeah sorry, check the edited answer now.

→ Reply

jalanprakhar

13 months ago, # ^ |

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

→ Reply

adityasah09

13 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'.

13 months ago, # ^ |

→ Reply

adityasah09

13 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

13 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

13 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

13 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

13 months ago, # ^ |

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

→ Reply

13 months ago, # ^ |

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

→ Reply

13 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

13 months ago, # ^ |

I set Mx to 5e12

→ Reply

13 months ago, # ^ |

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

→ Reply

13 months ago, # ^ |

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

→ Reply

13 months ago, # ^ |

oh mb, I calculated wrongly lol.

→ Reply

13 months ago, # ^ |

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

→ Reply

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

13 months ago, # ^ |

oh :(

→ Reply

Hmys

13 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

13 months ago, # |

khatam

→ Reply

Wolowitz

13 months ago, # |

← Rev. 2 →

-22

[.]

→ Reply

serenhade00

13 months ago, # |

How to solve C?

→ Reply

M_A_Noman

13 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

13 months ago, # ^ |

← Rev. 2 →

what is the logic behind this?

→ Reply

codefforces

13 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

13 months ago, # |

G1 was much easier than C/D/F

→ Reply

Pensive

13 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

13 months ago, # ^ |

same, had to google for E as well

→ Reply

13 months ago, # ^ |

-24

kill yourselves

→ Reply

13 months ago, # ^ |

i stand by what i said

→ Reply

0gnjen1

13 months ago, # ^ |

Woah edgy boy

→ Reply

13 months ago, # ^ |

vužgal bum te ognjene

→ Reply

13 months ago, # |

← Rev. 2 →

+13

chromate00 Orz for the great performance!

→ Reply

chromate00

13 months ago, # ^ |

+11

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

→ Reply

down_07

13 months ago, # ^ |

+10

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

→ Reply

chromate00

13 months ago, # ^ |

yes actually I have saved the blue version for that

→ Reply

13 months ago, # ^ |

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

→ Reply

13 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

13 months ago, # ^ |

Can you prove this conclusion?

→ Reply

13 months ago, # ^ |

Here it is

→ Reply

djay24

13 months ago, # ^ |

Thanks, did you solved D? Approach?

→ Reply

13 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

13 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

13 months ago, # ^ |

← Rev. 2 →

Common conclusion ? Ahh you are from china, never mind

→ Reply

JEE_MAIN_LOOSER

13 months ago, # ^ |

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

→ Reply

Hmys

13 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

13 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

13 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

13 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

13 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

13 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

13 months ago, # |

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

→ Reply

eternal_happiness

13 months ago, # |

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

→ Reply

deepaksolution

13 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

13 months ago, # ^ |

+12

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

→ Reply

cosenza

13 months ago, # ^ |

He's just copying YocyCraft's explanations

→ Reply

Nahida__

13 months ago, # |

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

→ Reply

Nahida__

13 months ago, # |

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

→ Reply

kmparvez

13 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

13 months ago, # ^ |

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

→ Reply

kanishk779

13 months ago, # |

Can someone provide an unofficial editorial for problem C?

→ Reply

eternal_happiness

13 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

13 months ago, # ^ |

lol this is how you prove it?

→ Reply

M_A_Noman

13 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

13 months ago, # ^ |

what about this test case 0 1 2 1 0

→ Reply

13 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

13 months ago, # |

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

→ Reply

Leftist_G

13 months ago, # ^ |

BTW, I think BD is nice.

→ Reply

Chimpanzee

13 months ago, # |

Nice problemset. I like task D

→ Reply

13 months ago, # |

E is classical and F is kind of bad.

BCD are nice problems.

→ Reply

13 months ago, # ^ |

B is the worst

→ Reply

13 months ago, # |

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

→ Reply

Raks_splunk

13 months ago, # ^ |

Bro relax lmao(I totally agree).

→ Reply

13 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

13 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

13 months ago, # ^ |

why

→ Reply

13 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

13 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

13 months ago, # ^ |

Wow that's nice

→ Reply

13 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

13 months ago, # ^ |

+29

Your solution for E is very cute

→ Reply

puspendra_09

13 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

13 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

13 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

13 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

13 months ago, # ^ |

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

→ Reply

NerfThis

13 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

13 months ago, # ^ |

That's by the defination of k-flower.

→ Reply

NerfThis

13 months ago, # ^ |

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

→ Reply

ayush_n

13 months ago, # |

How to solve Problem D

→ Reply

becaido

13 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

13 months ago, # ^ |

you'd better show your generator.

→ Reply

K-423

13 months ago, # |

← Rev. 2 →

+93

What the fucking description of F!

→ Reply

13 months ago, # ^ |

It's not thaat bad tbh)

→ Reply

K-423

13 months ago, # ^ |

← Rev. 2 →

+44

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

→ Reply

Chimpanzee

13 months ago, # ^ |

-34

then most of your friends aren't very bright

→ Reply

K-423

13 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/

13 months ago, # ^ |

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

→ Reply

L1gma

13 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

13 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

13 months ago, # ^ |

+22

3rd party code posted before contest is allowed

→ Reply

vaibhavsinghz

13 months ago, # ^ |

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

→ Reply

Valenz

13 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

13 months ago, # ^ |

← Rev. 2 →

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

→ Reply

anosh21

13 months ago, # |

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

→ Reply

_Hridoy

13 months ago, # |

+20

F is quiet confusing.

→ Reply

13 months ago, # |

-21

make it unrated

→ Reply

harshbutani01

13 months ago, # |

Can someone provide a counter example for this submission?

→ Reply

vgtcross

13 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

13 months ago, # ^ |

Thanks for the counter example!

→ Reply

ASHWANTH_K

13 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

13 months ago, # |

+17

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

→ Reply

procoderomk

13 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

13 months ago, # ^ |

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

→ Reply

jeal0uspengu1n

13 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

13 months ago, # ^ |

same issue i am facing

→ Reply

raghavmangla04

13 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

13 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

13 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

13 months ago, # ^ |

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

→ Reply

Nokemono

13 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

13 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://codeforces.com/contest/1811/submission/200724266

→ Reply

ID3

13 months ago, # |

+11

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

→ Reply

aqua4

13 months ago, # |

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

→ Reply

jackylova_fan_fan_fan

13 months ago, # ^ |

Yes

→ Reply

jackylova_fan_fan_fan

13 months ago, # |

So hard div3，(sad).

→ Reply

13 months ago, # |

seems that few people will pass F

→ Reply

ballpoint_pen

13 months ago, # |

I wonder when can rating changes be calculated,though I'm unrated :)

→ Reply

ballpoint_pen

13 months ago, # ^ |

Great contest! I found E much more interesting than I thought.

→ Reply

daoquanglinh2k7

13 months ago, # |

← Rev. 2 →

When do the ratings update??

→ Reply

pra1hamgup1a

13 months ago, # |

← Rev. 2 →

It is just sad to know Problem E’s code was available on the Internet and many people have copied directly from there. First time downvoting any post on CF.

→ Reply

Lwchicky0

13 months ago, # |

← Rev. 2 →

toooooooooooooooooooooooooooooo hard 4 div3

→ Reply

daoquanglinh2k7

13 months ago, # |

When will the system testing perform???

→ Reply

I_love_GSNQK

13 months ago, # ^ |

it's performed

→ Reply

daoquanglinh2k7

13 months ago, # ^ |

No, I think that you're joking.

→ Reply

WangTianzhuo

13 months ago, # ^ |

I think you are joking too.

→ Reply

WangTianzhuo

13 months ago, # |

← Rev. 2 →

-10

This round is hard for me.

→ Reply

Vishalk91_4

13 months ago, # |

Can anyone explain it to me, yesterday I solved 5 questions in Div 3, cf predictor showed an increase in rating, but now when I go and see the contest page it shows 1 solution submitted wrong and a decrease of -24 in my rating

→ Reply

haohaoh4

13 months ago, # ^ |

← Rev. 4 →

It's currently performing System Testing and all accepted submits need to be rejudged with stricter testcases. So the information on the contest page might be not correct until all tests are finished.

→ Reply

sybsyb

13 months ago, # |

In problem A, why the maximum $$$n$$$ in pretests is less than $$$10^5$$$? I don't think pretests should be like this.

→ Reply

1xx55

13 months ago, # ^ |

So it's a chance for you to hack. I'm too late to realize this ...

→ Reply

ItzDesert

13 months ago, # |

Can someone explain to me why in Problem G,the output of example(fifth example) "n=5,k=1 1 2 3 4 5" is 1?I thought the maximum length is 1,and 1,2,3,4,5 are both nice paths.So I think the answer of it should be 5.

→ Reply

onlyerror

13 months ago, # ^ |

maximum length is 5

take the whole sequence and count of it is 1

→ Reply

ItzDesert

13 months ago, # ^ |

oh thank u I got it,k=1 is really special case.

→ Reply

Vishalk91_4

13 months ago, # |

Was this round rated, i have accepted submission but my rating haven't been updated yet

→ Reply

animish01

13 months ago, # ^ |

It'll take some time bro

→ Reply

12 months ago, # |

Recently,I have got the message saying that i have cheated in the contest while i have not and the coincidence may have occur due to the template that i use and it is publicly available already before the contest and also i recieved the violation message on the problem d of this contest which was used by finding the ficconaci numbers which is done using the same code as everyone still i got the message which is not true.Please look after my solution and i request u to make my submissions again rated for this contest and take me in the contest. Hope the codeforces team will surely look after my request and soon investigate on the same .

→ Reply

12 months ago, # ^ |

Any updates MikeMirzayanov??

→ Reply

12 months ago, # ^ |

have you looked after it MikeMirzayanov

→ Reply