Codeforces Round #676 (Div. 2)

4 years ago, # |

+30

Auto comment: topic has been updated by flaviu2001 (previous revision, new revision, compare).

→ Reply

AmShZ

4 years ago, # |

+81

i lost the rated contest again :weary:

→ Reply

Tet

4 years ago, # ^ |

← Rev. 2 →

+47

look on the bright side, you participated in another unrated contest ^o^

→ Reply

RetiredPlayer

4 years ago, # |

+224

As a tester, you know ... what I want :)

→ Reply

Trump_Constructs_China

4 years ago, # ^ |

Meet your needs.Thank you for your efforts！

→ Reply

kclee2172

4 years ago, # |

+79

As a tester, I would like to say "Good Luck everyone. Have Fun!!"

→ Reply

kpw29

4 years ago, # |

+137

As a tester, I would like to say that I haven't seen the problem yet.

→ Reply

Imran_Farid

4 years ago, # ^ |

How did you test the round then?

→ Reply

kpw29

4 years ago, # ^ |

+41

flaviu2001 just wrote my name before I actually tested the round. But I did that yesterday :)

→ Reply

Imran_Farid

4 years ago, # ^ |

Oh, I see. Thanks for the clarification! :)

→ Reply

RD_TheCoder

4 years ago, # |

+17

Notice the unusual time !
Good luck for your maiden contest !!

→ Reply

rotavirus

4 years ago, # |

← Rev. 2 →

-235

The blog is written $$$4$$$ days before the contest -> bad contest

→ Reply

di4s

4 years ago, # ^ |

← Rev. 2 →

+11

deleted

→ Reply

rotavirus

4 years ago, # ^ |

-144

lifetime experience

→ Reply

atharv

4 years ago, # |

+17

As a tester, I would like to say, good luck and have fun!

→ Reply

1_Hypex_

4 years ago, # |

+11

What time is it? 18:35 or 21:05?

→ Reply

RD_TheCoder

4 years ago, # ^ |

← Rev. 3 →

+10

Now author fixed it.. But people why downoting ??

→ Reply

1_Hypex_

4 years ago, # ^ |

+11

Ok... thanks

→ Reply

4 years ago, # |

Auto comment: topic has been updated by flaviu2001 (previous revision, new revision, compare).

→ Reply

4 years ago, # |

Auto comment: topic has been updated by flaviu2001 (previous revision, new revision, compare).

→ Reply

4 years ago, # |

It seems the blog text does not use the "Contest time" feature of the blog editor, like [contest_time:1421]

→ Reply

4 years ago, # ^ |

+60

Oops, let's say I'm worse at writing blogs than problems.

→ Reply

jiangbowen_

4 years ago, # |

I expect that this contest can be held smoothly.

→ Reply

PurpleThinker

4 years ago, # |

← Rev. 5 →

+42

As a Romanian, I am excited to participate in a round made by Romanians!

→ Reply

traviscott

4 years ago, # ^ |

+18

"With" ?

→ Reply

PurpleThinker

4 years ago, # ^ |

← Rev. 2 →

Yeah, good point. I've edited the original comment.

→ Reply

v_v__devill

4 years ago, # |

Good luck to everyone

→ Reply

Nurda

4 years ago, # |

← Rev. 2 →

if someone knows why there is no announcement of the Codeforces Raif Round 1??

→ Reply

jiangbowen_

4 years ago, # ^ |

← Rev. 2 →

Now there's an announcement of the Codeforces Raif Round 1.

→ Reply

ayush_nishad

4 years ago, # |

← Rev. 2 →

What is "Raif" in Codeforces Raif Round 1 (Div. 1 + Div. 2)?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

-20

I would hope it is in honor of Raif Badawi who unfortunatly is still in prison for being a blogger and activist.

→ Reply

PurpleThinker

4 years ago, # ^ |

← Rev. 6 →

Deleted

→ Reply

4 years ago, # ^ |

-26

The problemsetters seem to be all from Singapore

→ Reply

CodAR

4 years ago, # |

+11

Clash with codechef cook-off, but do we even care?

→ Reply

codemastercpp

4 years ago, # ^ |

I do, cook-offs are decent and it's always better to have more contests to participate in.

→ Reply

4 years ago, # |

+21

What a great way to promote a youtube channel :D, JK,

→ Reply

FelixArg

4 years ago, # |

stefdasca orz

→ Reply

4 years ago, # |

← Rev. 2 →

I am a newbie so should i participate in div2 or div3 contests Please help. i want to increase my rating seriously

→ Reply

akhileshsirohi

4 years ago, # ^ |

Participate in both.

→ Reply

4 years ago, # ^ |

I only get notifications of div1 and div2 contests. till now i have not got even one div3 contest notification so that i can participate

→ Reply

akhileshsirohi

4 years ago, # ^ |

Frequency of Div3 contests is lesser than Div2 so you should try to participate in every Div2 and Educational Rounds. Educational Rounds are good too.

→ Reply

4 years ago, # ^ |

oh thanks for the info, btw i saw some participants graph starting from 1200 and for some it was below 1200 , what is this method of starting and rating further

→ Reply

m.szeliga

4 years ago, # ^ |

Starting rating changed some time ago. You can learn more about it here -> https://codeforces.net/blog/entry/77890

→ Reply

4 years ago, # ^ |

hey today i gave a div 2 contest , i was only able to do the first problem(this was my first contest ever). the soln got accepted but in my account ,contest section its showing nothing

→ Reply

m.szeliga

4 years ago, # ^ |

Rating changes happen some time after the contest (usually few hours). That's when your profile page section will be updated. If you want to know rating changes as soon as possible, there are some pretty accurate CF Predictors, that you can find just by googling them.

→ Reply

Harsh1610

4 years ago, # |

-33

This contest clash with the cook-off.....They should prepone or postpone the contest whichever is possible

→ Reply

kira201

4 years ago, # |

A lots of thanks to MikeMirzayanov and other involved organisers for rescheduling the round:)

→ Reply

skittles1412

4 years ago, # |

+17

Why can't CodeChef reschedule for CodeForces?

→ Reply

alamkhan

4 years ago, # ^ |

+17

Cause codechef scheduled the contest before codeforces

→ Reply

sam000013

4 years ago, # ^ |

In that case, CodeChef two monthly short contest are always prescheduled... So does that mean CodeForces will always have to keep that in mind.. Only a bit unfair, But this also shows how considerate Codeforces is for all of us..

→ Reply

chuka231

4 years ago, # |

Great another 2AM contest

→ Reply

Stelutzu

4 years ago, # |

+13

As a tester, I can say that the problems are really interesting!

→ Reply

its_Atrap

4 years ago, # ^ |

Really interesting and a hard jump from C->D? Usually I have noticed Div-2 contests with five problems have a large jump in difficulties from C to D, hopefully this round is more balanced.

→ Reply

https://www.youtube.com/watch?v=ebgjlXyH9s8

4 years ago, # ^ |

+16

You see the thing is not that simple, say the author wants to have a difficult problem D (say rating of atleast 2000), for an average participant it requires 40-60 min atleast, so if C is also medium difficult most of them won't have to time solve D or even read E.So they generally make C a bit easy and make D and E kinda difficult, so though there is a huge gap in difficulty but still you will be able to attempt it properly. Though no idea how this contest is gonna be

→ Reply

yesnomaybe

4 years ago, # |

← Rev. 3 →

+28

stefdasca Can you leave a dot in comment section? So that we can upvote :p

→ Reply

FOOLISH_JUSTIN

4 years ago, # |

That's a good time for Chinese competitor!Thanks flaviu2001!

→ Reply

john_smith_vip

4 years ago, # |

what will be the scoring distribution? or is there a fixed scoring distribution for div2 rounds and I'm just not aware of it?

→ Reply

Saket1612

4 years ago, # ^ |

The scoring distribution is standard 500 — 1000 — 1500 — 2000 — 2500.

→ Reply

iamgqr

4 years ago, # |

Whoah that's really early round, gives me no time to have dinner. Anyways glhf

→ Reply

Leonardo_Paes

4 years ago, # ^ |

LOL its 6AM in Brazil glhf

→ Reply

Ahmed_Solyman

4 years ago, # |

15 min to be ready (:

→ Reply

The_Apurv_Rathore

4 years ago, # |

-6

Good time for a participant from India. Just after lunch full of Energy.

→ Reply

ayushj121

4 years ago, # ^ |

Was that sarcastic? I feel Sleepy tbh XD

→ Reply

ayushj121

4 years ago, # |

In question B what does "adjacent by side" means does that exclude diagonal cells?

→ Reply

stefdasca

4 years ago, # ^ |

ask via round questions, not here

→ Reply

Sabamak

4 years ago, # |

all problems have nice music :) thanks <3

→ Reply

Aloncf

4 years ago, # |

Well, cool round! Problem C was sickkkk

→ Reply

sanchitgupta456

4 years ago, # |

-11

Do watch the video editorial here

→ Reply

garbart

4 years ago, # |

← Rev. 2 →

-43

Sorry, but it was a very stupid problem B.

→ Reply

michao

4 years ago, # ^ |

don't comment during ongoing contest.

→ Reply

garbart

4 years ago, # ^ |

Sorry. I edited the comment and left only the assessment.

→ Reply

katana_handler

4 years ago, # |

← Rev. 2 →

+21

The Kind of day i want to wake up to almost everyday during lockdown!!!

Afternoon — CF round

Evening — Kickstart

Night — CC round Cook Off

HAPPPYYYYYYYYYYYY!!!!!!!!!!!!!!!!!!!!!!!!!

→ Reply

Jaydeep999997

4 years ago, # |

+41

Gap between D and E is very Huggggggggge.

→ Reply

astroash

4 years ago, # |

stefdasca, flaviu2001, koala_bear00 You guys surely have a great taste in music:) I had never imagined that I would be introduced to new music via a contest!

→ Reply

ashkANOn

4 years ago, # |

← Rev. 2 →

Am i the only person who find C much easier than B and regret for wasting too much time on B instead of solve C. Or i overcomplicated B?

Solution for C is simply,

R n-1

L n

L 2

Which takes about 15 minutes to come with idea and solve.

For B my idea is

Let b1 and b2 two adjacent cell of F and c1,c2,c3 be adjacent cell of b1 and b2.

Then i checked condition for possible cases which takes 1 hour to implement.

→ Reply

4 years ago, # ^ |

Actually it was reverse for me,It took 20 min for B and an hour for C.

→ Reply

Leonardo_Paes

4 years ago, # ^ |

For me B was much much easier than C, I think it depends

→ Reply

Ahmad45123

4 years ago, # ^ |

← Rev. 2 →

C wasn't obvious at all, at least not for me. I wasted 1 hour 45 minutes in it and no AC xD

→ Reply

SakuraiMomoka

4 years ago, # ^ |

For B it will be easier if you check two adjacent cells of S and two adjacent cells of F.

→ Reply

ashkANOn

4 years ago, # ^ |

My badness. I really over complicated

→ Reply

vineetjai

4 years ago, # ^ |

Just make both the two cells at one end 0 or both the two cells at another end 1 or vice versa. check this condition I was first tried to implements bfs and got confused with conditions then I got this one. Though ~50 minutes are wasted. Here is my submission.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

It took me more time to understand C than solve B lol, So many misunderstandings in C for me

→ Reply

4 years ago, # |

ConstructiveForces...xD....nice problems. Here are my submissions..hope to pass ST. Still 20 short of Specialist tho :(

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const ll maxn=100005;
const ll mod=1e9+7;

int main(){
	fast;
	ll t,a,b,x;
	cin >> t;
	while(t--){
		cin >> a >> b;
		ll x = (a^b);
		cout<<x<<"\n";
	}

}

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
const ll maxn=100005;
const ll mod=1e9+7;


int main(){
    fast;
	int t,n,i,j,k;
	cin >> t;
	while(t--){
		cin >> n;
		vector<vector<char>> gr(n,vector<char>(n));
		for(i=0;i<n;i++){
			for(j=0;j<n;j++)
				cin >> gr[i][j];
		}
		int n1 = gr[0][1]-'0';
		int n2 = gr[1][0]-'0';
		int n3 = gr[n-1][n-2]-'0';
		int n4 = gr[n-2][n-1]-'0';

		if(n1==n2 && n3==n4){
			if((n1==0 && n3==1) || (n1==1 && n3==0)){
				cout<<"0"<<"\n";
			}
			else{
				cout<<"2"<<"\n";
				cout<<"1 2"<<"\n";
				cout<<"2 1"<<"\n";
			}
		}
		else{
			if(n1!=n2 && n3==n4){
				if(n3==1){
					cout<<"1"<<"\n";
					if(n1==1)cout<<"1 2"<<"\n";
					else if(n2==1)cout<<"2 1"<<"\n";
				}
				else if(n3==0){
					cout<<"1"<<"\n";
					if(n1==0)cout<<"1 2"<<"\n";
					else if(n2==0)cout<<"2 1"<<"\n";
				}
			}
			else if(n3!=n4 && n1==n2){
				if(n2==1){
					cout<<"1"<<"\n";
					if(n3==1)cout<<n<<" "<<n-1<<"\n";
					else if(n4==1)cout<<n-1<<" "<<n<<"\n";
				}
				else if(n2==0){
					cout<<"1"<<"\n";
					if(n3==0)cout<<n<<" "<<n-1<<"\n";
					else if(n4==0)cout<<n-1<<" "<<n<<"\n";
				}

			}
			else{
				cout<<"2"<<"\n";
				if(n1==0)cout<<"1 2"<<"\n";
				else if(n2==0)cout<<"2 1"<<"\n";
				if(n3==1)cout<<n<<" "<<n-1<<"\n";
				else if(n4==1)cout<<n-1<<" "<<n<<"\n";
			}
		}
	}
	
}

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const ll maxn=100010;
const ll mod=998244353;


int main(){
	fast;
	string s;
	cin >> s;
	int n = s.length();

	cout<<4<<endl;
	cout<<"L"<<" "<<2<<endl;
	cout<<"L"<<" "<<2<<endl;
	cout<<"R"<<" "<<2<<endl;
	cout<<"R"<<" "<<2*n+1<<endl;
}

Any ideas on D?

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Think about an alternative way of going to a neighboring cell.

Path C6 == Path C1 + Path C5

So, the cost of C6 = minimum of the cost of C6 and (cost of C1 + cost of C5)

A similar approach for all other paths.

→ Reply

vineetjai

4 years ago, # ^ |

How did you got all possible ways of going from one cell to another?

→ Reply

4 years ago, # ^ |

First, compute the optimal cost to all the directions, Then you need to do basic math to get the optimal answer.

→ Reply

vineetjai

4 years ago, # ^ |

And how did you get that maximum only addition of two paths will give minimum cost? Why not three or more?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I don't think there exists any other optimal way except those two. You should try to observe the figure given in the problem.

→ Reply

kmyiu

4 years ago, # ^ |

← Rev. 2 →

For simplicity consider $$$C2$$$(pure right), only $$$C1,C2,C3$$$ can give some right component. If you include any of $$$C4,C5,C6$$$ then you must need extra $$$C1,C2,C3$$$. Say if you want to use $$$C6$$$ then your path will be sth like $$$C6,C2,C3 > C2$$$ or $$$C6,C1,C3,C3>C1+C3$$$.

Therefore minimum cost of $$$C2$$$ will be $$$C2$$$ itself, or optimal $$$C1$$$ + optimal $$$C3$$$. In fact, the minimum cost of $$$C2$$$ will be $$$C2$$$ itself, or the original $$$C1$$$ + original $$$C3$$$.

The proof based on no two consecutive directions are not optimal. Assume $$$C1,C2$$$ are not optimal, then $$$C1>C2+C6$$$ and $$$C2>C1+C3$$$. Adding two inequalities gives $$$C1+C2>C1+C2+C3+C6 \implies 0>C3+C6$$$. Contradiction. If minimum cost of $$$C2$$$ is optimal $$$C1$$$ + optimal $$$C3$$$, then optimal $$$C1$$$ must be itself, the original cost of $$$C1$$$.

→ Reply

Jaydeep999997

4 years ago, # ^ |

After applying Floyd Warshall's Algorithm, you may use Greedy approach to find the answer.

→ Reply

4 years ago, # ^ |

Target cell can have huge coordinates, so how is a graph algorithm feasible here? Is there some trick to compress the graph or just some O(1) thing?

→ Reply

Jaydeep999997

4 years ago, # ^ |

I mean considering a graph with only seven vertices. Essentially to find the minimum cost to reach from $$$ (x,y) $$$ to $$$ (x+dx,y+dy) $$$.

→ Reply

4 years ago, # ^ |

Ok will try to upsolve...thanks!

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Optimal right move = min(c[2],c[3]+c[1]) and Optimal left move = min(c[5], c[4]+c[6])

For positive x: You just gotta find where y lies w.r.t x. There will be 2 choices of movement if (y>x or y<0), and if 0<=y<=x there are 3 possible choices of movement, try to figure them out.

for negative x: just put x=-x, y=-y and swap opposite Cs and do the same as positive x

→ Reply

4 years ago, # ^ |

I see will try to upsolve...thanks!

→ Reply

hakr_2104

4 years ago, # ^ |

I did exactly same but got WA. Might have missed something

→ Reply

codesniper99

4 years ago, # |

ppl solved D with O(1)?? I keep getting wrong answer on testcase 3 too. Is O(1) method correct way? find enclosing axis then max three ways to reach point??

→ Reply

WitchOfTruth

4 years ago, # ^ |

I guess it is possible, but it seemed so troublesome to correctly consider all cases that I abandoned this idea

→ Reply

WitchOfTruth

4 years ago, # ^ |

← Rev. 2 →

I guess you need to consider also max cases

say you need to get to (7, 5)

You can go 7 up-right and 2 down and this can also be optimal

→ Reply

4 years ago, # ^ |

Yup thats how I did it, but among those 3 ways to reach a point, left and right movement have 2 ways each, I missed that part initially

→ Reply

SkyDreams

4 years ago, # |

-25

I just dont get why authors dont get it .. Giving such stories just confuses us ... It does not make any thing "cool about your set". It makes it worse.

Man on a serious note, I know coming up with a interesting plot is definetly tough but I dont want to know that what the hell your character wants to achieve then first grab the info of what is doing what .. and not to mention the names u come up on

→ Reply

4 years ago, # |

← Rev. 5 →

I tried to hack the following solution for A by generating 1e4 test cases where 1e8<=a, b<=1e9. This solution should time out but I wasn't able to hack it. Can someone please help me why it didn't TLE ?

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int min=0;
        long long a,b,temp;
        cin>>a>>b;
        for(int i=0; i<=b; i++){
            temp = (a^i)+(b^i);
            if(temp>min){
                min=temp;
            }
        }
        cout<<temp<<endl;
    }
return 0;
}

→ Reply

dapingguo8

4 years ago, # ^ |

Actually the valuable $$$min$$$ and the loop doesn't do anything. After the loop, $$$temp$$$ is always set to $$$a\oplus b + b\oplus b = a\oplus b$$$, so the compiler ignored the loop.

Unluckily, $$$a\oplus b$$$ is just the correct answer.

→ Reply

4 years ago, # ^ |

So the compiler after few test cases realized that temp is being set to a^b and hence ignored thousands of other test cases ? Can you please elaborate a bit more ?

→ Reply

dapingguo8

4 years ago, # ^ |

It's called as O2-optimization, you can google for more information.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I got -150 for this ;-; . I will definitely check for -O2 optimization.

→ Reply

Night_Lord

4 years ago, # ^ |

← Rev. 2 →

Hello I did exactly same code but get TLE why?

        cin>>a>>b;
	mi=inf;//9e18
	ans=0;
	lp1(i,0,b)//for(ll i=0;i<=b;++i)
	{
		mi=min(mi,((a^i)+(b^i)));
	}
	cout<<mi<<endl;

Submission

→ Reply

smitpatel1010

4 years ago, # ^ |

← Rev. 2 →

b can be upto 1e9. you can not traverse to 1e9. You need to optimise your code.

You can read about O2 optimisation here

→ Reply

ffao

4 years ago, # ^ |

← Rev. 2 →

This is not the same code. The code that gets optimized above is roughly equivalent to

cin>>a>>b;
mi=inf;//9e18
ans=0;
lp1(i,0,b)//for(ll i=0;i<=b;++i)
{
    mi=(a^i)+(b^i);
}
cout<<mi<<endl;

So you can see that in the code above, mi is always overwritten in every iteration. This makes it easy for the compiler to realize that only the final iteration of the loop needs to be performed. (The submitter got lucky that this apparently incorrect code always gives the correct answer.)

→ Reply

ALT__

4 years ago, # |

← Rev. 2 →

+14

B was so stupid because it was all about typing, annoying question imo.

Unless there's a better way of solving it..

→ Reply

AdHocMan

4 years ago, # |

C was just solving this test case — "abc"

→ Reply

4 years ago, # ^ |

How to convert this to a palindrome ?

→ Reply

4 years ago, # ^ |

← Rev. 3 →

3 operations

L 2 ==> babc

R 2 ==> babcba

R 5 ==> babcbab

'babcbab' is a palindrome.

→ Reply

LimitBreaker

4 years ago, # ^ |

exactly

→ Reply

ExplodingFreeze

4 years ago, # ^ |

abc

Perform R 2

abcb

Perform L 3

cbabcb

Perform L 2

bcbabcb

Now just generalize this to a being the first character of the string, c being the last and b being all the ones in-between. This is actually how I solved it during contest as well.

→ Reply

dryice

4 years ago, # |

Is it only me, who did B in 15 mins but struggled in C for an hour? C definitely was a good problem, but required some thinking, and took me an hour to come up with a 4 line solution :(

→ Reply

Ahmad45123

4 years ago, # ^ |

You're not alone. And the sad thing is I didn't get it in contest but after it.

→ Reply

4 years ago, # ^ |

I first did D, then looked again into C.

→ Reply

nmnsharma007

4 years ago, # |

I missed C by one second. As soon as I submitted, the contest ended:(

→ Reply

dblark

4 years ago, # |

+15

we got speedforces again lol

→ Reply

keywet06

4 years ago, # ^ |

← Rev. 2 →

I coded D earlier than C

So my rank is low (ノ￣ー￣)ノノ(º_ºノ)

The 55-minute-long D makes me down. ╮(╯﹏╰）╭

→ Reply

30_percent_off

4 years ago, # |

Ohhhhhhh as a rock fan I looooove these discription! C and D were so cute！hard E,really. Like this contest!

→ Reply

4 years ago, # |

← Rev. 2 →

-35

C is one of the worst Adhoc ever, you have to keep trying combinations until you get it, no clever obervation, no analysis, just have pattern aSb and keep trying.

B is equally annoying problem, so many if conditions, pure implementation

Really dissappointed

→ Reply

AM_I_Learning

4 years ago, # ^ |

There is a clever observation to make first and last characters same and then apply both the operations one at a time . I dont know if this is clever or not but I was not clever!

→ Reply

4 years ago, # ^ |

Can you arrive at it without trying a zillion samples ?

→ Reply

ExplodingFreeze

4 years ago, # ^ |

← Rev. 2 →

Yes? Clearly distinct characters will be the most difficult case and 3 is the smallest n, so try 3 random distinct characters. This gets an easily generalizable answer. As for solving this case, I just checked for a sample with a distinct character at the end (sample 2) and used it as the basis.

→ Reply

4 years ago, # ^ |

I can propose solns that will work for abcde but not for abcdef

→ Reply

AM_I_Learning

4 years ago, # ^ |

Exactly what I did just by seeing the problem but I was trying to do it int three operations. I thought there is a way since "abc" can be done in just 3 operations. but bad luck went in wrong direction earlier!

→ Reply

30_percent_off

4 years ago, # ^ |

L2 R2 R 2*n-1 would be clever lol .Yes just by thinking

→ Reply

4 years ago, # ^ |

It would have been, if you arrive at it with a proper algorithm,instead of noticing pattern in a few examples

→ Reply

ExplodingFreeze

4 years ago, # ^ |

← Rev. 2 →

And what is a "proper algorithm" for solving a problem?

In my experience, nearly all problems break down to analyzing it (possibly with some small cases or simplifications or maybe just writing a brute force), noticing interesting properties and then getting some intuition about how to proceed.

Even most problems requiring formal algorithms or some data structures usually require you to realize that some properties hold which makes you think of that approach.

→ Reply

martins

4 years ago, # ^ |

Test case 1 makes you realize that you can always do it in two moves if the first and third characters are the same. The rest is thinking if you can obtain such a string in a few moves.

→ Reply

4 years ago, # ^ |

Nah, C had a very nice observation. You don't need to try many samples, just take a string where all characters are distict. If that works, everything else will work. After that its just a bit of thinking and 3 lines of code

→ Reply

Nuwaisir_Rabi

4 years ago, # ^ |

Firstly, $$$type 1$$$ operation will make a prefix of the string a palindrome and $$$type 2$$$ operation will make a suffix of the string a palindrome. A palindrome can have at most $$$1$$$ element having frequency $$$1$$$. Here in the given string, you cannot change the frequency of the first and the last element at the first operation. But if the first and the last element are different, then you must have one of them in some operation. So, first, you do $$$R \ n-1$$$, and then to double the frequency of the last element of the given input string, you do $$$L \ n$$$. Now, it is easy to see that, doing another operation will result in a palindrome.

→ Reply

codesniper99

4 years ago, # ^ |

I will give you best answer

Consider a non palindrome of two parts X|Y

where | is middle point ok?

lets take for example initital string => X1.X2.X3|Y1.Y2.Y3

This must be worst case right?

Now do L,'2'

-> X2 .X1.X2.X3|Y1.Y2.Y3

Now Do, R,'2'

-> X2.X1.X2.X3.Y1.Y2.Y3. Y2.Y1.X3.X2.X1 (length be sz)

Now Do R, (sz-1) where** sz** is length of string reached above

-> X2.X1.X2.X3.Y1.Y2.Y3. Y2.Y1.X3.X2.X1. X2

This is palindrome. Just use induction for all lengths of X and Y

ez clap

→ Reply

iMurat

4 years ago, # ^ |

wqwrd ewerd qwerd

→ Reply

mahade31

4 years ago, # |

I did two bfs on B. smh

→ Reply

I_Love_You_Tzuyu_Chou

4 years ago, # |

Thanks for Tzuyu's reference in Problem A

→ Reply

stefdasca

4 years ago, # ^ |

→ Reply

john_smith_vip

4 years ago, # |

← Rev. 2 →

+50

Is it just me or was this contest too much ad-hoc?? A,B,C,D all can be implemented in O(1), it was only about solving various test cases until you can see the pattern. I may be very wrong here but I think not much real programming or barely any Data structures and algos were used in this contest :/

→ Reply

ScotchOnTheRocks

4 years ago, # |

+13

Damn man, why all Constructive. Imma lose a 100 rating points, where gaining 14 would've put me over to CM. It was so hit or miss.

→ Reply

SpaceIndex

4 years ago, # |

+55

→ Reply

4 years ago, # ^ |

+10

Speaking of patterns did you notice 676 is also a palindrome?

→ Reply

Keshi

4 years ago, # ^ |

+98

did you notice 1421 % 676 = 69?

→ Reply

4 years ago, # ^ |

-13

bruh

→ Reply

akshatbhutra

4 years ago, # |

In problem B, is diagonal movement allowed?

→ Reply

kmyiu

4 years ago, # ^ |

no, adjacent by a side, not a corner

→ Reply

4 years ago, # ^ |

No, as neighbors in the grid are those who share an edge.

→ Reply

Aloncf

4 years ago, # |

Well... Instead of CM i I failed system test for problem B.
Granted, I did implement it in a disgusting way, bit it passes pretests :/

→ Reply

garbart

4 years ago, # |

Solution for C was so easy :(

crying

→ Reply

ay21

4 years ago, # |

Ad-hoc Missiles. I'm not complaining though :))

→ Reply

akshatbhutra

4 years ago, # |

Problem B: Consider the grid as:

A B C ...
D E F ...
G H I ...

A = Start Case 1. if B=D=0 and C=E=G=1 then STUCK. Case 2. if B=D=1 and C=E=G=0 then STUCK.

We have to make anyone of the two cases in atmost two steps.

Is this logic correct?

→ Reply

starboy_jb

4 years ago, # ^ |

Logic only depends on, BD and HF.

→ Reply

akshatbhutra

4 years ago, # ^ |

Yes, this is also mentioned in editorial and I understood it. But why the above logic did not work? Am I missing something? Any idea.

→ Reply

Vintarel

4 years ago, # ^ |

I don't see any counter example for this strategy, i guess this should work well !

→ Reply

ay21

4 years ago, # ^ |

Yeah, this works, I have implemented something similar.

→ Reply

kmyiu

4 years ago, # ^ |

Your logic is correct. If $$$C=E=G$$$ then at most two steps. Otherwise there will be one of 0/1 appear two times, let's denote if by $$$x$$$. If at least one of $$$B,D$$$ is $$$y$$$ then set $$$C=E=G=x$$$ and $$$B=D=y$$$ which requires at most two steps. Else both $$$B,D$$$ are $$$x$$$, set the two $$$C,E,G$$$ with x to y.

→ Reply

TheVan

4 years ago, # |

+19

I think the Problem BCD are boring

→ Reply

Mohsin_Bantu_cf

4 years ago, # ^ |

Agreed. Just if-else needed, LoL.

→ Reply

MartyByrde

4 years ago, # |

+10

Great contest, great songs. However, I should not have listened to them during the contest.

→ Reply

vraj95soni

4 years ago, # |

This was a total disappointment since every question was a case work, I came here to solve the problems hoping to use my implementation and coding skills and not using my case work skills. I don't know about problem E but other 4 questions were total case work. Were you guys expecting us to write only if-else statements rather than using some great concepts out there?

→ Reply

cyborg_7459

4 years ago, # |

-22

Was this contest unrated??

→ Reply

Mohsin_Bantu_cf

4 years ago, # ^ |

LoL, you shouldn't have asked it, Downvotes coming.

→ Reply

cyborg_7459

4 years ago, # ^ |

-11

Why?? I don't understand XD

→ Reply

Trump_Constructs_China

4 years ago, # |

+25

Problem E is so hard, so interesting, so mysterious. Thanks for the author's ideas and efforts!

→ Reply

Legend_of_Azkaban

4 years ago, # |

As soon as I read the first line of problem A, I was like — Aaaah... Imma kill this round... sad not all the problems had "twice" background.

→ Reply

MavrosOplarxigos

4 years ago, # |

← Rev. 2 →

-19

Note for C/C++ users: I lost problem D because I was doing negative % positive in the indexes of the c[] array. We know that (-1) % (6) should give 5 but in C/C++ when you do that you will get -1. So I wrote my own modulo to overcome this and I said it would be good to share it with you people:

#define mmod(a,b) ( (a >= 0) ? ((a%b)%b) : ( ( ( a + ( ((abs(a)+b)/b) * b ) ) % b ) % b ) )

Hope it help you and myself get out of Gold Nova! I mean Expert!

→ Reply

Mohsin_Bantu_cf

4 years ago, # |

-7

Problems B, C, and D were just if-else...Not so great round, Should rather call it speedforces, implementationforces, etc.

→ Reply

ishandutta0098

4 years ago, # |

I have a Rating of 369 and I had solved 1 problem in this contest. Will my rating change as this is a Div 2 contest?

→ Reply

cyborg_7459

4 years ago, # ^ |

Yes it will increase

→ Reply

shekabhi1208

4 years ago, # |

-9

hello there, in the first question of Codeforces Round #676 (Div. 2) some test cases are wrong for the sake of understanding ..in one of the examples given in that question ..if we take a=28 and b=14 the output according to your code is 18 but

minimum possible answer is 10 if we take x as 4 28^4+14^4=10

→ Reply

Yuvraj_Sharma

4 years ago, # ^ |

← Rev. 2 →

28^4+14^4==34 not 10 don't write like this in code because priority of '+' is greater than '^' so 28^4+14^4 will become 28^18^4 which is equal to 10 so write in code like this (28^4)+(14^4)

→ Reply

himadri765

4 years ago, # |

I was the first contestant to solve 1421C - Palindromifier, why didn't you put in the announcement people who were the first to solve each problem?

→ Reply

dranjohn

4 years ago, # |

I found this because of your contest. Thank you :)

→ Reply

pg199

4 years ago, # |

I gave the contest and used ideone.com to write my code. Someone stole my code, because of which I was marked a violater. But I haven't done any type of cheating. How can I get my rating back??

→ Reply