include

2 недели назад, # ^ |

As a contribution farmer, I disagree

→ Ответить

Pirate_King

2 недели назад, # ^ |

I saw that you have one piece pfp and got curious. Did you name yourself after wapol ?

→ Ответить

waipoli

2 недели назад, # ^ |

no, the story with waipoli is more strange than you think)

→ Ответить

Im_Gonna_Be_King_Of_Reds

13 дней назад, # ^ |

Did anybody say one piece :)

→ Ответить

Umanity

13 дней назад, # ^ |

Yes)

→ Ответить

heavenly_principles

11 дней назад, # ^ |

yess!

→ Ответить

Kolyanchick

2 недели назад, # ^ |

Hi bro :)

→ Ответить

waipoli

2 недели назад, # ^ |

Hi)

→ Ответить

2 недели назад, # ^ |

+13

As a tester, I want some contribution!

→ Ответить

hasanovr

13 дней назад, # ^ |

As a participant I also want some.

→ Ответить

_yo_boii

13 дней назад, # ^ |

as a regular comment reader, I also want

→ Ответить

andreifilimon

2 недели назад, # |

Good luck to everyone! Enjoy thi Div3 :) Hope to have a good time in this round.

→ Ответить

Abel51

2 недели назад, # |

I wish you all good rankings!

→ Ответить

2 недели назад, # |

I hope I can solve ABCDE after having exam in the morning. Good luck to everyone!

→ Ответить

andreifilimon

2 недели назад, # ^ |

Good luck in your exam and in the round!

→ Ответить

2 недели назад, # ^ |

+26

Good luck with the exam! (Actually Ill also have one in the morning so Im supposed to be studying)

→ Ответить

2 недели назад, # ^ |

+18

I overslept.

→ Ответить

2 недели назад, # ^ |

so you skipped the exam or what?

→ Ответить

2 недели назад, # ^ |

+12

Basically yeah.... I think I'll be able to rewrite it.

→ Ответить

My planned post contest discussion stream

2 недели назад, # ^ |

lol. i accidently wrote that my exam is today as i thought contest is on 3rd but its tomorrow morning. so no contest for me :sob

→ Ответить

aryanc403

2 недели назад, # |

→ Ответить

2 недели назад, # ^ |

+11

It is a sarcastic comment!!!

As a tester, I can already discuss the problems. So you can start your stream rn and don't waste any time.

→ Ответить

OAleksa

2 недели назад, # |

+10

As a tester I don’t know what to say.

→ Ответить

Mehdi_Ba

2 недели назад, # |

Yeey another round!

→ Ответить

Physical

2 недели назад, # |

Wish you Rating+=♾️

→ Ответить

Rushdi

2 недели назад, # |

← Rev. 3 →

I'm out of competition

Spoiler

→ Ответить

2 недели назад, # ^ |

I forgot the name of this meme what’s the name??

→ Ответить

2 недели назад, # |

Time to reclaim my title as specialist.

→ Ответить

2 недели назад, # ^ |

+12

Summon Mahoraga and get him to adapt to all the problems.

→ Ответить

2 недели назад, # ^ |

Oh I wish. But first he's gonna have to adapt to my massive skill issue , and that will kill him like a 200% hollow purple.

→ Ответить

2 недели назад, # ^ |

Nah You'd win

→ Ответить

2 недели назад, # ^ |

Always bet on ABC.

→ Ответить

LordLouis04

13 дней назад, # ^ |

you'll need more than only ABC in div 3 to reach specialist.

→ Ответить

13 дней назад, # ^ |

Oh yeah I forgot its Div 3 , either way it doesnt matter , I wasnt able to participate.

→ Ответить

Norp

2 недели назад, # |

Hope to the best div3 ever

→ Ответить

2 недели назад, # |

I hope to be a good div3. <3 But,I wonder how can i solve at least 3 problems? Consider that I practise continuously about div3.

→ Ответить

13 дней назад, # ^ |

The problems from Div.3 rounds and Educational rounds are classical (= common) and useful. It means that you can always easily utilize the skills and techniques you learned from these rounds, and there are numerous problems are just derived by such classical problems. In contrast, there are creative and mathematics-required problems in those non-educational rounds and Div.1 rounds from time to time, so I believe that it is hard to earn higher rating since 2100.

So what you need to do is just to try your best to learn more techiniques (including how to analyse the problem and how to bug-free code). The amount of those traditional techiniques is limited, you can eventually complete that in 30 days if you try to solve the first 4-5 problems in one Div.3 Round everyday.

→ Ответить

13 дней назад, # ^ |

Thanks for your usefull feedback Im so grateful for ur comment <3 <3 . I actually do that I'm trying everyday to solve atleast 2-3 problems div3 but I think that the progress is very slow and I see my friends are climbing so fast and that makes me disappointed. I have a question : "Is there any yt channel that give tips how to be faster and how to be better at greedy problems . I consider your tip to solve 4 problems every day <33

→ Ответить

13 дней назад, # ^ |

if you want to be your friend I'm grateful for that :DD(In general, for ur great character <3)

→ Ответить

13 дней назад, # ^ |

To be honest, I learned how to solve greedy problems by reading some textbooks written in Chinese. Maybe I can give you some keywords to help you to search for those materials.

Observe which is constant: after doing some operation, some numbers/relationships remain unchanged. For example, to minimize the amount of pair (i, j) that satisfies certain condition (e.g. i < j and a_i > a_j). You can switch the adjacent elements, and only the relationship between the two elements will change. It means that you can do the swap operation to optimize each pair of adjacent elements to reach the goal. This thinking method may also be called as "Swapping adjacent"?
Do it first, and regret in the future: You can do the operation first, and record the operations you have done in some data structures (e.g. a heap/priority_queue), when you meet a better choice to do a operation, you just delete the worst operation recorded by the data structures (e.g. priority_queue.top()) and replace the old operation with the new and better one.
Try to predict whether can make a greed operation: Just like a lot of binary-search-liked methods (e.g. to find the k-th element in a data structure) which are common-used in data structures like SegmentTree or BBST. You can also learn the skill in 01-Trie (to greed from the most significant bit, check that whether can take a 0 or an 1 in the next, until the lowest bit)

The aboving are the common idea in greedy solutions. Besides you can also just improve your mathematical skills and instinct.

→ Ответить

13 дней назад, # ^ |

I think that skills come with just practice and consistency (I will focus on your tips that are really new for me)

→ Ответить

2 недели назад, # |

-8

Looks like its time for another Speedforces round.

→ Ответить

2 недели назад, # ^ |

KEKWW

→ Ответить

2 недели назад, # ^ |

During our previous round you solved 3 tasks out of 8, lol.

→ Ответить

2 недели назад, # ^ |

-8

Hehe, I was only newbie back then . Hope to do better this time.

→ Ответить

2 недели назад, # ^ |

Good luck!

→ Ответить

2 недели назад, # ^ |

Thank you sir!

→ Ответить

13 дней назад, # ^ |

-9

This didn't age well.

→ Ответить

AvaraKedavra

2 недели назад, # |

← Rev. 2 →

+23

Meme

→ Ответить

Omar_

2 недели назад, # ^ |

→ Ответить

Murad134

2 недели назад, # |

hoping to return back the blue handle

→ Ответить

Arcane_ikigai11

2 недели назад, # |

Does anyone have guesses what kind of round it would be? I mean what kind of problem is contained in the problem set?

→ Ответить

2 недели назад, # ^ |

problems will be all solvable in a programming language. I can bet on that if you want.

→ Ответить

andreifilimon

2 недели назад, # ^ |

Yeah there is always a solution that will be accepted. This if there won't be a problem that is mission impossible :)

→ Ответить

2 недели назад, # ^ |

It is a sarcasm!!!

As a tester, I would say that there will 10 output only tasks, and it will be a heuristic contest.

→ Ответить

jonnnnnsinaga

2 недели назад, # ^ |

What's output only tasks?

→ Ответить

2 недели назад, # ^ |

nothing better than that could be said by Mr. Tester. XD

→ Ответить

2 недели назад, # ^ |

Sure, I think that my guesses are correct, but we`ll see.

→ Ответить

2 недели назад, # ^ |

You can never be sure for 100%

→ Ответить

2 недели назад, # ^ |

Yeah,like that time when I got ill because we couldn't choose a place where to eat,lol.

→ Ответить

AHMADUL

2 недели назад, # |

Both Setters: Expert, Both Max: Candidate Master, Both From: Ukraine, Both Authored: 891 Div-3, All Setters(891): Expert, Rated till: !Expert;

→ Ответить

2 недели назад, # ^ |

Both setters: UOI medalists. One of the setters: codechef 2198. Both setters: UJGOI problemsetters.

→ Ответить

Ghulam_Junaid

2 недели назад, # ^ |

Congratulations for the medals! I really liked UOI 2023 problems.

→ Ответить

AHMADUL

2 недели назад, # ^ |

Congratulations to both of you. Specially for the medals.

→ Ответить

SEKAINOHAKAISHA

12 дней назад, # ^ |

What is UOI?

→ Ответить

Md-Merazul-Islam

2 недели назад, # |

Hope for high-quality problems! ^_~

→ Ответить

Allen123

2 недели назад, # |

Hope I can reach 1550

→ Ответить

2 недели назад, # ^ |

Hope to solve 5 problems

→ Ответить

2 недели назад, # ^ |

Good luck!

→ Ответить

S.A.Y.E.D

13 дней назад, # |

last round organized by SashaT9 i turned from gray to green I wish I can turn from cyan to blue today !

→ Ответить

kalpitdon7

13 дней назад, # |

+14

Hoping for a colour change ( to green)

→ Ответить

GavinCQTD

13 дней назад, # ^ |

Good luck

→ Ответить

TBPOTW

13 дней назад, # |

За него дают рейтинг?

→ Ответить

flamur2

13 дней назад, # |

ICPC rules with a penalty of 10 minutes for an incorrect submission;

what does this mean? Do i get time deducted if i submit an incorrect solution? and after i solve it do i get my minutes back.

Sorry im not really familiar on how the contests work here

→ Ответить

yeetholmes619

13 дней назад, # ^ |

So basically your final rank is based on comparing the number of problems you solved with everyone else. Now among the people who've solved the same number of problems as you, the ties are broken based on the sum of the submission times for each of your problems. Now if you submit say three incorrect solutions, but later submit the correct one for a particular problem then 10 * 3 mins are added to your total submission time for that problem.

Hope this clears things!

→ Ответить

flamur2

13 дней назад, # ^ |

Yep it does, thank you for the clarification!!!

→ Ответить

Mazen_eldar

13 дней назад, # |

Do not be afraid, but be careful.

→ Ответить

chenRenning

13 дней назад, # |

Hopefully this competition will be able to break through

→ Ответить

Md_Minhaj

13 дней назад, # |

Hope to solve A-E.

→ Ответить

yuaksoinocenow

13 дней назад, # |

I hope to reach at least 1450 in the contest

→ Ответить

13 дней назад, # |

one refresh costed me 10 mins ._.

→ Ответить

VitaliiV

13 дней назад, # |

+11

delayforces...

→ Ответить

Danyz777

13 дней назад, # ^ |

Might be a glitch or server prob

→ Ответить

DrRhaegal

13 дней назад, # |

→ Ответить

yuanzihan

13 дней назад, # |

Ten-minute delay in start time?

→ Ответить

crazycoder76

13 дней назад, # ^ |

Why are u using the same avatar as me? ~

→ Ответить

xsyxsyxsy

13 дней назад, # |

Why the time was delayed?

→ Ответить

DrRhaegal

13 дней назад, # ^ |

could be some server issues due to a lot of requests!

→ Ответить

Bruce.Wayne_19

13 дней назад, # |

I just hope this round does not come out as mathforces.

→ Ответить

SEKAINOHAKAISHA

13 дней назад, # ^ |

Spoilers, it kinda was

→ Ответить

idkao

13 дней назад, # |

-15

weak samples of B, literally passed it while misunderstanding statement of problem

→ Ответить

13 дней назад, # ^ |

not a chance. your solution was correct.

→ Ответить

ravi_kumar013030

13 дней назад, # |

Hope there will be plagiarism checking for this round

→ Ответить

w_izard

13 дней назад, # |

← Rev. 4 →

Unexpectedly solved A — F. Still don't know how i did, but i did. I am very proud of myself.

→ Ответить

SuperMo

13 дней назад, # ^ |

← Rev. 3 →

E needs pre knowledge or it can be solved even if you know nothing about Manhattan distance ?

→ Ответить

w_izard

13 дней назад, # ^ |

It is just observational problem. I spent quite a time to find the arrangment that will always work.

→ Ответить

x1f0cb32d3_

13 дней назад, # ^ |

Same here. Had to visualize potential arrangements for n up to 6 to spot a pattern.

→ Ответить

OMgL

13 дней назад, # ^ |

I saw that [1, 1] [1, 3] [1, 4] ... [1, n-1] [2, 1] [n, n] was an answer, and I have no idea what Manhattan distance is.

→ Ответить

13 дней назад, # ^ |

← Rev. 2 →

Maybe you can do better in the next time since that you already know what is Manhattan distance now.

→ Ответить

Sreedhar3210

13 дней назад, # |

what's testcase 2 for problem F.

spent almost an hour debugging it, still not able to find the mistake.

→ Ответить

w_izard

13 дней назад, # ^ |

look at my code bro — 259236083

→ Ответить

Sreedhar3210

13 дней назад, # ^ |

got it bro. forgot to initialize.

→ Ответить

khumayunabduraupov

13 дней назад, # |

Thanks for the contest! Problems were quite good!

→ Ответить

DonSilvio

13 дней назад, # |

After solving D for like 20 minutes, I realized that I was solving the wrong problem since I did not notice that the player may also stay in the current position and not move to p[i].

→ Ответить

defarias25

13 дней назад, # |

I will now try to understand why my solution for E works haha. Thanks for the great problem set authors!

→ Ответить

SuperMo

13 дней назад, # ^ |

I tried multiple random things still nothing worked

→ Ответить

Enmendurana

13 дней назад, # |

last minute i couldn't submit F, i am tilt :(

→ Ответить

bibimoni

13 дней назад, # ^ |

I submitted problem F on the last second. The server were very laggy

→ Ответить

13 дней назад, # |

E is very nice

→ Ответить

CEKPET

13 дней назад, # ^ |

Yes, I agree with you. The task is very interesting. I really like this kind of task. Unfortunately, I was unable to solve this problem during the competition, if you solve this problem, can you explain your solution?

Thanks!

→ Ответить

13 дней назад, # ^ |

← Rev. 7 →

explanation

code

def thing(n):
	print(1, 1)
	print(n, n)
 
	if n == 2:
		return
 
	for i in range(n - 3):
		print(1, i + 2)
	print(n - 1, 1)
 
 
testcases = range(int(input()))
 
for case in testcases:
	thing(int(input()))

→ Ответить

Stuck_On_Gray

13 дней назад, # |

← Rev. 2 →

I spent an hour while coding wrong codes on D :(

seriously code once Think twice

→ Ответить

rsFalse

13 дней назад, # |

-14

LOL. Why E was not an A problem? I read the task at the end of contest.

→ Ответить

Stuck_On_Gray

13 дней назад, # ^ |

How to do it?

→ Ответить

rsFalse

13 дней назад, # ^ |

← Rev. 2 →

+18

Solution spoiler

→ Ответить

N00bCode

13 дней назад, # ^ |

There are solutions and there are beautiful solutions.

→ Ответить

13 дней назад, # ^ |

Another Valid Construction

→ Ответить

13 дней назад, # ^ |

As a tester I reckon problem E is 1700-1900, because my solution to E is so complex. I believe that a 1700 problem can be placed on problem E. (Well, to be honest problem E is harder than G2 for me)

I used the Manhattan distance list to construct:

n = 1, [], [0, 0] // n = 1, Manhattan list is [] (empty), can represent all integers in range [0, 0] n = 2, [1], [0, 1] n = 3, [1, 2], [0, 3] n = 4, [1, 3, 2], [0, 6] n = 5, [1, 3, 2, 2], [0, 8] n = 6, [1, 3, 2, 2, 2], [0, 10]

I discovered this solution using 40 minutes, so I give it an 1700-1900 estimation. Why I used so much time because that I tried to represent the range [0, 2*n-2] by using the classical list [1, 2, 4, 8, 16, ...]. So I was far away from the right solution at the beginning.

The constructive problems require a really high-level math instinct. Maybe you are talented. I believe that some skillful competitors will also struggle with solving it.

→ Ответить

rsFalse

12 дней назад, # ^ |

Ye, I very much like constructive and pattern problems :)

P.S. A has also very simple solution, so I was wrong about difficulty comparison.

BTW E was nice problem.

→ Ответить

Aditya_Metkar

13 дней назад, # |

Managed to solve D after wracking my brain for 1hr
Feeling Good :)

→ Ответить

Aviral_Gupta

13 дней назад, # |

-44

I wish I could downvote this contest multiple times. Pathetic problem statement for E

→ Ответить

13 дней назад, # ^ |

welp, did you solve it? did you try to at least draw the matrices?)

→ Ответить

SuperMo

13 дней назад, # ^ |

+10

I couldn't solve it but I think statement was clear

→ Ответить

tenick

13 дней назад, # |

any hints for E?

→ Ответить

13 дней назад, # ^ |

← Rev. 3 →

Think about when you can have a set with all values from 1 to 2n — 2. When can you construct this? Is there a special case where you can't construct this?

→ Ответить

Siddarth_MSR

13 дней назад, # ^ |

The maximum distinct distances will always be <= min(n(n-1)/2,2n-2) since the possible distances are 1,2,...., 2n-2. So, for n>=4 its enough to find a construction such that |H|= 2n-2. Select (1,1) and (n,n) first and try to find this construction.

→ Ответить

tenick

13 дней назад, # ^ |

makes sense so I was thinking in the right direction after all. But wouldn't 0 also be a possible distance? so possible distance would be from 0 to 2n-2

→ Ответить

Siddarth_MSR

13 дней назад, # ^ |

Yup,doesnt really matter though

→ Ответить

frissky9

13 дней назад, # |

May be its just me but the reloading of this site is too slow, I had 2 minutes and I wanted to submit E, but couldn't as it got stuck on reloading page. Please do the need full please.

→ Ответить

Patta_gobhi_

13 дней назад, # |

Anyone did G1 with string hashing??

→ Ответить

Vladosiya

13 дней назад, # ^ |

+46

A good try, mister hash-hacker.

→ Ответить

Patta_gobhi_

13 дней назад, # ^ |

Got it right just the index to string was getting out of the length of string.

→ Ответить

vstiff

13 дней назад, # ^ |

+23

No need for hashing, just one line in rust:

bin_search(0, s.len() + 1, |lcp| s[lcp..].matches(&s[0..lcp]).count() + 1 < k)

→ Ответить

13 дней назад, # ^ |

Actually thats pretty impressive

→ Ответить

nskybytskyi

13 дней назад, # ^ |

btw you can solve G2 by caching binsearch results

→ Ответить

vstiff

13 дней назад, # ^ |

← Rev. 2 →

I wanted to, but wasted 1.5 hours debugging F and still messed up somewhere, barely got G1 at the last seconds.

In case anyone interested: 259263295

→ Ответить

theRealChainman

13 дней назад, # ^ |

This did work for me in C++, but not in python. Always get TLE in python.

→ Ответить

bibimoni

13 дней назад, # ^ |

looks nice!

→ Ответить

13 дней назад, # ^ |

I did)))) but random hashes.

→ Ответить

redcircle

13 дней назад, # ^ |

← Rev. 2 →

yes

upd: Hacked

→ Ответить

Tspectre

13 дней назад, # ^ |

Patta_gobhi_ Check this submission 259262278 (Hashing + Binary Search)

→ Ответить

aditya.pca.25

13 дней назад, # |

Why am I so bad at construction problems. I always get stuck at problems like E. Tips? Anyone??

→ Ответить

13 дней назад, # ^ |

← Rev. 2 →

i cant prove it, but

n = 1 => 1 1

n = 2 => 1 1, 1 2

n >= 3 => previous + (n, n)

→ Ответить

13 дней назад, # ^ |

oh, no

→ Ответить

13 дней назад, # ^ |

nice pfp with kings gambit)

→ Ответить

13 дней назад, # ^ |

thanks :)

→ Ответить

13 дней назад, # ^ |

n = 3 => 1 1, 1 2, 3 1

n >= 4 => previous + (n, n)

→ Ответить

Khaled93

13 дней назад, # ^ |

Well, I didn't solve it in the contest but this is correct.

The number of distinct possible distances in general is 2*n-1, you can generate Manhattan distances from 0 to 2*n-2, and for n = 4, you can get [0,1,2,3,4,5,6,7].

So the solution increases by 2 numbers for each increase in n, 2*n-2, and 2*n-3, by adding n,n you add 2*n-2 since that is the Manhattan distance of 1,1 and n,n and you get 2*n-3 since that is the Manhattan distance of 1,2 and n,n.

Retaining the previous solution you get Distances from 0 to 2*n-4 and by adding n,n you add 2*n-3 and 2*n-2.

→ Ответить

nicio9

13 дней назад, # ^ |

← Rev. 3 →

Proof:

The goal is to get every possible path distance. This is possible for all n>3. All the path distances are the range [0:2n-2] (shortest: they are at the same position, longest: two opposite corners).

Starting with (1,1) and (1,2) gets you the first 2 distances: d=0 and d=1.

Say we have solved for n=3. (It is given that a solution is (1,1), (1,2), (3,3) Now, everytime n goes up by 1, we need to find two more distances, but with only one new position.

Since we already have (1,1) and (1,2), we simply need to find a position that has manhattan distance 2n-3 and 2n-2 from these two points, at the same time.

This new position is the bottom right corner, a.k.a. (n,n): manhattan distance from (1,1) to (n,n) is 2n-2 manhattan distance from (1,2) to (n,n) is 2n-3

It is clear that we can simply repeat this process n-2 times, after having placed the original positions (1,1) and (1,2).

Hope this helps :)

→ Ответить

arnur3729

13 дней назад, # ^ |

Solve F.

→ Ответить

13 дней назад, # ^ |

practical advice

→ Ответить

13 дней назад, # ^ |

I totally agree with you! I got stuck at problem E when I tested it. And I even spend 40 minutes to solve it! Why I spent too much time on solving it, it was because that there is another classical problem: To express all the numbers in range [0, n], we can always choose [1, 2, 4, 8, ..., 2^(k-1)]. So I just tried this "solution" first. Well, I failed.

After a while, I noticed that I don't need to minimize the elements I use. What I mean is that by using [1, 2, 4, 8, ..., 2^(k-1)] there is just O(log(n)) elements. But for this problem, we can use O(n) elements. Then I notice that I can just contrust the solution for n = 7 by adding one more elements in the solution for n = 6.

That is the definite breakthrough, just add a new element in (n, n) is ok. This problem gave me the new idea that is not to solve the problem using the O(log(n)) thinking at first, just try to discover how to construct a new solution by the previous n. I think in constructive problem we should try to utilize different ways to analyse the same problem, and explore the protential solution by reading other users' code.

→ Ответить

OMgL

13 дней назад, # |

How does the 10minutes penalty work, does it only give penalty for problems that passed the first testcase cause I got a few wrong submissions but didnt get any penalty.

→ Ответить

https://codeforces.com/contest/1968/submission/259209395

13 дней назад, # ^ |

if you failed on tc 1 then it will not give penalty . but thats bad that you are not checking your code locally.

→ Ответить

N00bCode

13 дней назад, # ^ |

No penalty for wrong answer of testcase 1.

→ Ответить

pm2006

13 дней назад, # |

Why in problem e it was counting every cell with itself?

→ Ответить

Vivek_Dubey

13 дней назад, # |

← Rev. 7 →

-7

MY SUBMISSION

why I am getting garbage value in 1st sub TEST case of 1st ans? This is working on SUBLIME(The IDE I use) and also on CODECHEF IdE then why not in codeforces??

SINCE LAST 30 CONTEST trying to solve c and finally today its seems to happened but SEEMS UNlUCKY

"SashaT9" "FBI"

→ Ответить

sarthakswarnkar

13 дней назад, # |

← Rev. 2 →

in Problem F, any idea why this code is giving idleness limit exceeded?

P.S. IDLENESS LIMIT EXCEEDED, NOT TIME LIMIT EXCEEDED

→ Ответить

bruce_x001

13 дней назад, # ^ |

Same happening with me... Time complexity is O(n*(4logn)) That is acceptable but still I'm getting TLE

I have used segment tree to find the XOR of ranges

my Submission Link

→ Ответить

introxpert

13 дней назад, # ^ |

i had the same problem its probably because of using a map and copying a long vector which is O(n) so when there are a lot of similar prefix xors (like in test 17 where there is a lot of 1s and 0s) each of those vectors is gonna be long and cost a lot my solution is using compression to store the vectors in an array of vectors instead so there is no need for copying them for each query but didn't have enough time to implement it, might try it later

→ Ответить

bruce_x001

13 дней назад, # ^ |

← Rev. 3 →

Got your point bro...copying a vector will take O(n) time in worst case.. So overall complexity will become O(n*n) in the query processing loop

Taking it by reference will work !

Thanks for pointing this out

→ Ответить

matislu

13 дней назад, # ^ |

sarthakswarnkar, There is a version of your code that passes code.

→ Ответить

Vampire

13 дней назад, # |

FBI won't give me positive delta when he saw my pfp :sob:

→ Ответить

13 дней назад, # ^ |

nice pfp. but i prefer Makise)

→ Ответить

13 дней назад, # |

Hints For F , (when we have odd k ?(for even xor its 0))

→ Ответить

vstiff

13 дней назад, # ^ |

← Rev. 2 →

Let xor of block = Y, then pref[r] ^ pref[l-1] = Y. Look it inside l..r and check that after it comes even number of blocks.

→ Ответить

link: https://codeforces.com/contest/1968/submission/259244119

13 дней назад, # ^ |

← Rev. 2 →

what comes even times? How will we know its good if y!=0?

→ Ответить

x1f0cb32d3_

12 дней назад, # ^ |

← Rev. 2 →

Ended up with the correct solution soon after the round ended.

Take cumulative XORs at indices right before (p) and right after (q) the subarray. If equal, it can be split into 2 parts. If not, look for q and then p in between (sequence p...q...p...q). If found, it can be split into 3 parts.

Now, iterating through the subarray to find the q and p in the middle is worst case (edit: O(n) per query, O(nq) in total, where q = # of queries) and ended up TLE'ing. Had to use a dictionary (cumulative XOR value -> list of indices) and BS through the lists. The time it took to get the index calculation right was why I couldn't submit on time.

→ Ответить

m_nature

13 дней назад, # |

Didn't read E until the last minute but between any pair of cells is confusing when reading the notes, probably need something like between any pair of cells (including each cell with itself)

→ Ответить

N00bCode

13 дней назад, # ^ |

Even if we exclude pair containing a cell with itself, the answer stays the same. |H| will just be reduced by 1 for every n.

→ Ответить

m_nature

13 дней назад, # ^ |

Yeah but like if it doesn't even matter then I guess it's best to just not include each cell with itself in the notes lol.

→ Ответить

saquib2508

13 дней назад, # ^ |

"...confusing when reading the notes..." Well, I don't recommend what I'm about to say, but maybe don't read the notes when the problem statement is pretty clear and has almost no room for ambiguity? And even if you do and discover some extremely weird ambiguity (which happened in this case, I agree with you), maybe gather yourself and cancel out that thought quickly, like "well it doesn't matter cause if I generate any answer it will have the distance 0 anyways so let's ignore this bullsh* and solve normally"?

Also, the notes section of construction problems usually helps only to find any patterns. I "read" the notes, but only saw the figures and tried to understand what might a good strategy be. Really didn't look at the $$$\mathcal{H}$$$ set in the notes until I saw this comment.

→ Ответить

m_nature

13 дней назад, # ^ |

I mean I didn't complain because I didn't solve it

I only mentioned it in this comment, because well it literally is a comment for the problem statement itself that it shouldn't be confusing

→ Ответить

saquib2508

13 дней назад, # ^ |

Right, agreed. It shouldn't have been calculated or worded like this.

→ Ответить

hackerAman1729

13 дней назад, # |

-8

Problem C. Assembly via Remainders ***** this is my solution, it is correct i guess but the test case says failed . dunno why :

include

using namespace std;

void solve() { int n; cin >> n; int arr1[n-1]; for (int i = 0; i < n — 1; i++) { cin >> arr1[i]; }

int arr2[n];
arr2[0] =  arr1[0] + 1;

for (int i = 0; i < n - 1; i++) {
    arr2[i + 1] = arr2[i] + arr1[i];
}

for (int i = 0; i < n; i++) {
    cout << arr2[i] << " ";
}
cout << endl;

}

int main() { int t; cin >> t; while (t--) { solve(); } return 0; }

→ Ответить

JEdward

13 дней назад, # ^ |

example: 2 499 21

→ Ответить

JEdward

13 дней назад, # ^ |

you may try to fix your code by add another 505(for example), to make sure your arr2[i+1] is greater than arr[i+1]

→ Ответить

MkcAllen

13 дней назад, # ^ |

assuming arr2[0]=arr1[0] +1 might be causing the trouble here. What if arr1 has an element that is greater than greatest element while calculating arr2...let's say arr 2 while calculating got us 3 and arr1 has 5 in the next iteration? mod 3 has range 0-2 so getting 5 while be impossible.... best way to overcome this is to ensure arr2 has all elements greater than max element of arr1

→ Ответить

polsage

13 дней назад, # |

Why is my G1 fails on test case 2

→ Ответить

mzv

13 дней назад, # ^ |

s = "aaaaaabaaa"

s1 = "aaaaabaaa"

using your algorithm, s1 didn't exist as substring of s

→ Ответить

polsage

13 дней назад, # ^ |

got it thanks

→ Ответить

JEdward

13 дней назад, # |

+14

E is awesome, costing most of my time on it but still, stuck:( Nice Round indeed, but sad negative delta for me:((

→ Ответить

hundunlilun1

13 дней назад, # |

E Good Job. I live this.

→ Ответить

elseecay

13 дней назад, # |

tasks was nice

→ Ответить

kinitic013

13 дней назад, # |

any hint for F??

→ Ответить

Pirate_King

13 дней назад, # ^ |

if subarray xor is even it is always possible
for odd, if answer exists, then it is always possible to break subarray into exactly 3 segments , each one of them having the same xor as whole subarray

→ Ответить

hxano

13 дней назад, # ^ |

You only need to split the subarray into either 2 or 3 subsegments, since you can compress any way of splitting into 4, 5, ... into just these two cases.

If the subarray was to be split into 2, there must exist l<=i<r so that xor[l..i]==xor[i+1..r]. Doing some algebra magic, we get that xor[1..l-1]=xor[i..r]. So we just need to check the equivalence of these two prefix xors (O(1)), without any need for iterating!

If the subarray was to be split into 3, similarly, there must exist l<=i<j<r so that xor[l..i]==xor[i+1..j]==xor[j+1..r]. Using a bit of rearranging, we get xor[1..l-1]==xor[1..j] and xor[1..i]==xor[1..r]. We can maintain a map/unordered_map of sets to keep track of the indexes where each value appears and greedily choose i and j so that the two conditions above hold in O(log(n)) time.

→ Ответить

https://codeforces.com/contest/1968/submission/259246021

13 дней назад, # ^ |

Wow I was able to figure out we only need 2 / 3 splits but went nowhere from that. I am so stupid..

→ Ответить

kinitic013

13 дней назад, # ^ |

same couldn't figure out afterwards

→ Ответить

goodman

13 дней назад, # |

Просто хочу поблагодарить за хороший раунд! Удачи и счастья всем)

→ Ответить

Shoeib

13 дней назад, # |

wasted 10 mins in D thinking that each player k/2 turns

→ Ответить

sashshaikh12

13 дней назад, # |

could anyone please tell me a counter test case to my solution on G1, i could not find one by stress testing as well

→ Ответить

13 дней назад, # ^ |

unrelated but by selecting all code and pressing shift+tab you can delete the spaces at the start of the lines

→ Ответить

Danyz777

13 дней назад, # |

This was my first contest. I was able to solve only 2 questions. I am not running after rating but can someone tell me what rating will I get? I am really excited about it

→ Ответить

Six_Seconds

13 дней назад, # ^ |

+300 something

→ Ответить

Danyz777

12 дней назад, # ^ |

When will the rating get updated?

→ Ответить

Six_Seconds

12 дней назад, # ^ |

Got updated. Check it out

→ Ответить

VitaliiV

13 дней назад, # ^ |

I think approximately 300-400

→ Ответить

blackronaldo

13 дней назад, # ^ |

you can download codeforces predictor on google — it will show you your rating change

→ Ответить

MrPrince22

13 дней назад, # |

-20

Hope I will turn back green today. So bored of gray ..

→ Ответить

Astroflexx

13 дней назад, # |

Very nice contest with very nice problems :) Thanks a lot for the round FBI SashaT9 and all testers!

→ Ответить

13 дней назад, # |

-25

Weak tests again....

259139777

→ Ответить

Noobish_Monk

13 дней назад, # ^ |

+15

$$$N^3$$$ for $$$N = 1000$$$ works well if it has a small constant. Your solution doesn't have a big constant. Worst case is test t = 1000 x = 1000, your solution works well there

→ Ответить

13 дней назад, # ^ |

-20

unbelievable. so corrupt constraints. and for what? to give c++ coders another advantage. in div 3 round...

→ Ответить

13 дней назад, # ^ |

-13

Wow.... Weak tests.... For the easiest problem of the round.... For the problem where there are at most 1000 different possible tests... Wow....

→ Ответить

13 дней назад, # ^ |

← Rev. 2 →

Sure you guys did your best. But why it is 1000 but not 100 or not 10000 we will never know...

→ Ответить

13 дней назад, # ^ |

because x values can be only up to 1000 (actually because x is only in range [2,1000] there are not 1000 but 999 possible tests)

→ Ответить

DC17

13 дней назад, # |

← Rev. 2 →

+10

What is the intended solution for G2? I used string hashing and set to solve it in worst case O(N * (log N)^2), but average case would be better than this.

→ Ответить

Gwynbleidd_

13 дней назад, # ^ |

Do you have any proof for the upper bound when using hash? I did with zfunc worst case O(N* (logN)^2)

→ Ответить

DC17

13 дней назад, # ^ |

← Rev. 2 →

Yes I have proven it. My algorithm is that for every length of prefix I have a set called candidate that stores the starting indices which have the same substring as the prefix for until the previous length.

Now for the current length I can find the count in N log N/ len. So the complexity will be N log(N) ^ 2.

You can check this submission: 259254423

→ Ответить

Gwynbleidd_

13 дней назад, # ^ |

Ya got it, so you are removing the candidates which don't have prefix of length l same so they wont be checked ever again, and in the worst case if no candidate are removed then its the same as nlog^2n when all char are equal. Great!

→ Ответить

DC17

13 дней назад, # ^ |

Yes perfect! You described it better than I could :)

→ Ответить

tickbird

13 дней назад, # |

problem E be like WA on pretest 1 🤡

→ Ответить

F...

13 дней назад, # |

← Rev. 2 →

For Problem G1 I wrote this code


bool ok(int len,string &s,int k)
{
   int n = s.size();
   string t = s.substr(0,len);
   int cnt = 1,idx = 0;
   for(int i=len;i<n;i++)
   {
      if(s[i] == t[idx]) idx++;
      else 
      {
         idx = 0;
         if(s[i] == t[idx]) idx++;
      }
      if(idx == len)
      {
         idx = 0;
         cnt++;
      }
   }


   return cnt >= k;
}
void solve()
{
   int n,a,b;
   cin>>n>>a>>b;
   string s;
   cin>>s;
   int l = 0, r = n+1;

   while(r - l > 1)
   {
      int mid = (r+l)/2;
      if(ok(mid,s,b)) l = mid;
      else r = mid;
   }
   cout<<l<<endl;
}

Tried with many custom cases still couldn't figure what's wrong here. Can anyone please look and point out the mistake here.

Here i am just trying to find number of partitions where all partitions contains a string "t" (as declared in code) as prefix and check whether number of partitons is greater or equal to the asked partitions defined in question.

→ Ответить

polsage

13 дней назад, # ^ |

same i also applied the same logic but wrong answer on 2

→ Ответить

C : https://www.youtube.com/watch?v=oEx5rR4wAKw

13 дней назад, # ^ |

You can use KMP to check the condition instead of pointers.. Refer here:

Spoiler

Code:

Spoiler

auto good = [&](int val) {
        string tmp = ""; rep(i, val) tmp+=s[i];
        debug(tmp)
        string ita = tmp + "#" + s;
        debug(ita)
        vi pi = prefix_function(ita);
        ll cnt = 0;
        debug(pi)
        vi all; all.pb(-1);
        rep(i, sz(ita)) {
            if(pi[i]==sz(tmp)) {
                int id = i - 2 * sz(tmp);
                if(id>all.back())all.pb(id+val-1);
            }
        }
        debug(all)
        return sz(all)-1>=L;
    };

→ Ответить

F...

13 дней назад, # ^ |

← Rev. 3 →

Can you please tell a mistake here. I have been trying to find the counter case but not able to find one. This is eating me up now. Still couldn't figure out what's wrong here.

Here is my submission: https://codeforces.com/contest/1968/submission/259250481

→ Ответить

F...

13 дней назад, # ^ |

← Rev. 2 →

Update: Found one TC here


1
15 3 3
abacababacbabac

Here answer is 4 but above code will give 3.

→ Ответить

nutella2007

13 дней назад, # |

Thank you for tasty problems. I enjoyed.

→ Ответить

cheatingdetector

13 дней назад, # |

← Rev. 3 →

today's contest as expected as this was div3 so solutions to problem A,B,C,D all soon were available by 21:00 , i tried very much in finding the cheated ones which many tried modifying: the cheated solution readily available for problem D from 21:00(UTC+5.5) https://ibb.co/Rph74Qd https://ibb.co/f2rx42K . please ban these cheaters : i already mention about some of them before. 259222711 259219713 259230136 259217156 259228528 259227463 259228698 in fact some of them also tried the later problem solutions from some sources. like for problem F i will share what i find later . MikeMirzayanov Vladosiya

→ Ответить

cheatingdetector

13 дней назад, # ^ |

for E nothing can be told as that was very much same for most of them but for F some tried last moment cheated solutions acceptance to improve their rank . This was the cheated solution for problem F : https://ibb.co/wKPK3tH . in fact this user "jam_coder" tried submitting this cheated solution with some change in the variables exact same form of the solution : 259244079 luck was not in her/his side for this problem as her/his was run time errored Similarly user "kaminenisaisriram" cheated the G1 solution too but it got rte in last moment hurry if needed i can show the G1 cheated sol later. Similarly these too cheated submissions (for F) which got accepted: 259240705 259240389 259239867 259238933 259238439 MikeMirzayanov Vladosiya

→ Ответить

Bruce.Wayne_19

13 дней назад, # |

Thanks for this round. enjoyed solving.

→ Ответить

formidablechief27

13 дней назад, # |

← Rev. 3 →

-12

Video Editorials for Questions C, D, E

D : https://www.youtube.com/watch?v=XBUN4LwolEM

E : https://www.youtube.com/watch?v=DObsk_Rlhg8

language => Hindi

→ Ответить

rawatnikhil

13 дней назад, # ^ |

in problem G1, isn't your check function running in O(n^2). How is it passing the test cases

→ Ответить

13 дней назад, # ^ |

-9

As a tester, I was only sending the correct solutions and not the wrong ones.

→ Ответить