EDIT - Edit Distance Again

As any experienced programmer must know the famous problem of "Edit Distance", however this problem is considered an “alternating chain” if you have alternately made case sensitive.

Example: "AaAaAbB" "B" "a" "aBaCdEf"

Alternating chains are considered in our problem.

We only have one operation that is permitted in exchange for a lower or upper case Latin letter.

Given a string giving the minimum number of changes to be considered an alternating chain.


A string with no spaces line containing only uppercase and lowercase letters, one for each line of maximum length 10^3 until end of file


For each line print the minimum number of changes to the chain is a "chain alternately"




hide comments
dwij28: 2016-06-27 00:10:35

This is not even remotely a DP problem. Pure Ad-hoc.

epsilon: 2016-02-27 17:36:45

it's an insult to dp if this belongs to dp category !!! :P

vedang: 2015-12-01 12:52:40

Why is this problem even tagged as DP? It's should be ad-hoc.

Karun : 2015-10-22 23:34:51

dont know why using toupper/tolower is giving WA... but comparing by ASCII value works... wierd

sharad mahajan: 2015-09-17 21:00:26

give syntax of eof

SangKuan: 2015-07-11 11:59:25

every test right,but still got ac

Sayak Haldar: 2015-06-23 15:14:23

I aggree with Avinash...I have to read the problem statement of codechef problem to understand the problem. Problem setter, from next time onwards, explain one good test case to make problem statement more clear.

sai krishna: 2015-05-20 10:08:11

similar problem

Avinash: 2012-04-17 12:44:50

the problem description is not clear and why is it even named "Edit Distance Again"?

Last edit: 2012-04-17 12:45:39
fitcat: 2012-02-26 06:06:25

For those getting WA, note that "exchange" here means "toggle". The only operation allowed is toggling the case of the letters. The resultant string has the same length of the original's.

Added by:Paulo Costa
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)