715 - Substitution Cipher

Moderator: Board moderators

turingcomplete
New poster
Posts: 11
Joined: Wed Oct 09, 2002 7:31 pm
Contact:

715 - Substitution Cipher

I can't figure out what was wrong with my submission, but the judge gives "Wrong Answer". Frustrated and suspicious that the judge was broken I found a solution posted for the 1998 European Contest (C - the exact same question). The judge gave a "Wrong Answer" for that as well.

http://contest.mff.cuni.cz/archive/cerc1998

What's up? What specification isn't spelled out in the question that I have to watch out for?

turingcomplete
New poster
Posts: 11
Joined: Wed Oct 09, 2002 7:31 pm
Contact:
///////////////////////////////////////////////////////////////////////////////
// solution to http://acm.uva.es/p/v7/715.html
// problem 715
///////////////////////////////////////////////////////////////////////////////

// @BEGIN_OF_SOURCE_CODE
// @JUDGE_ID: xxxxxx 715 C++

// if you only use TRACE and printVector for debugging output then defining this
// will remove the output for submitting.
#define NDEBUG

#include <iostream>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>

#ifdef WIN32
#include <sstream>
#else
#include <strstream>
typedef strstream stringstream;
#endif

#ifdef NDEBUG
#define TRACE(x) ((void)0)
#else
#define TRACE(x) cout<< #x ": '"<<( x )<<"'" << endl
#endif

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;

// will create a segment vilolation
void segVilolation() {
vector<double> v;
for(int i = 0; i < 10000; ++i) {
v[i] *= v[i * 5];
}
}

//-----------------------------------------------------------------------------
// Reads a line of input, and adds each value in the line to the vector
// Returns false when it reads EOF
// Returns an empty vector if the line is empty
// Lines with invalid terms are ignored after the first invalid term.
// Vector is cleared before values are added.
//
template<class T>
bool getInputLine(vector<T>& vec)
{
vec.clear();

if (cin.eof()) {
return false;
}

stringstream inLine;

cin.clear();
cin.get(*inLine.rdbuf());
if (cin.fail() && !cin.eof()) {
cin.clear();
}
cin.get(); // get rid of delimiter
while(!inLine.eof())
{
T field;
#ifdef WIN32
inLine >> noskipws >> field;
#else
inLine.unsetf(ios::skipws);
inLine >> field;
#endif
if(!inLine.fail()) {
vec.push_back(field);
}
}

return true;
}

template <class T>
void displayVec(vector< vector <T> > vec) {
#ifndef NDEBUG
for (int i = 0; i < vec.size(); ++i) {
for (int j = 0; j < vec[i].size(); ++j) {
cout << vec[i][j];
}
cout << endl;
}

#endif
}

char gBefore, gAfter; // a rule, set by getRule
vector< vector< char > > gPossibilities; // all the possible alphabets, determined by rules

bool getRule(const string& a, const string& b) {
int len = MIN(a.size(), b.size());
for (int i = 0; i < len; ++i) {
if (a[i] != b[i]) {
gBefore = a[i];
gAfter = b[i];
return true;
}
}
return false;
}

bool isLetterTaken(char c) {
if (gPossibilities.empty()) {
return false;
}
for (int i = 0; i < gPossibilities[0].size(); ++i) {
if (gPossibilities[0][i] == c) {
return true;
}
}
return false;
}

// for all the letters that come after gBefore (including gBefore) in all gPossibilities
// add a new possibility with gAfter after that letter
void addPossibilityBefore(char there, char notThere) {
vector< vector<char> > newPossibilities;
for (int i = 0; i < gPossibilities.size(); ++i) {
for (int j = 0; j < gPossibilities[i].size(); ++j) {
if (gPossibilities[i][j] == there || added) {
vector<char> possibility;
for (int k = 0; k < gPossibilities[i].size(); ++k) {
possibility.push_back(gPossibilities[i][k]);
if (k == j) {
possibility.push_back(notThere);
}
}
newPossibilities.push_back(possibility);
}
}
}
gPossibilities = newPossibilities;
}

void addPossibilityAfter(char there, char notThere) {
vector< vector<char> > newPossibilities;
for (int i = 0; i < gPossibilities.size(); ++i) {
bool seenThere = false;
for (int j = 0; j < gPossibilities[i].size(); ++j) {
if (gPossibilities[i][j] == there || !seenThere) {
vector<char> possibility;
for (int k = 0; k < gPossibilities[i].size(); ++k) {
if (k == j) {
possibility.push_back(notThere);
}
possibility.push_back(gPossibilities[i][k]);
}
newPossibilities.push_back(possibility);
if (gPossibilities[i][j] == there) {
seenThere = true;
}
}
}
}
gPossibilities = newPossibilities;
}

void addPossibilities(vector< vector<char> >& newPossibilities, const vector<char>& possibility, int index) {
for (int i = index; i < possibility.size() + 1; ++i) {
vector<char> newPossibility = possibility;
newPossibility.insert(newPossibility.begin() + index, gBefore);
newPossibility.insert(newPossibility.begin() + i + 1, gAfter);
newPossibilities.push_back(newPossibility);
}
}

vector< vector<char> > newPossibilities;
for (int i = 0; i < gPossibilities.size(); ++i) {
for (int j = 0; j < gPossibilities[i].size() + 1; ++j) {
}
}
gPossibilities = newPossibilities;
}

// remove any inconsitent possibilities based on the new rule
void removeInconsistent() {
vector< vector <char> > consistent;
for (int i = 0; i < gPossibilities.size(); ++i) {
bool foundBefore = false;
for (int j = 0; j < gPossibilities[i].size(); ++j) {
if (gPossibilities[i][j] == gBefore) {
foundBefore = true;
} else if (gPossibilities[i][j] == gAfter && foundBefore) {
consistent.push_back(gPossibilities[i]);
break;
}
}
}
gPossibilities = consistent;
}

int main()
{
TRACE("started");

vector<long> input;
getInputLine(input);
assert(input.size() == 1);
int totalCases = input[0];
for (int numCases = 0; numCases < totalCases; ++numCases) {
getInputLine(input);
if (input.empty()) {
break;
}
assert(input.size() == 2);
gPossibilities.clear();
string previousWord;
TRACE(input[1]);
for (int numWords = 0; numWords < input[1]; ++numWords) {
vector<string> word;
getInputLine(word);
if (numWords == 0) {
previousWord = word[0];
continue;
}
if (!getRule(previousWord, word[0])) {
/// TRACE("no rule");
/// TRACE(previousWord);
/// TRACE(word[0]);
previousWord = word[0];
continue;
}
previousWord = word[0];
TRACE(gBefore);
TRACE(gAfter);
if (gPossibilities.empty()) {
vector <char> start;
start.push_back(gBefore);
gPossibilities.push_back(start);
}
// TRACE(1);
// displayVec(gPossibilities);
bool isBeforeTaken = isLetterTaken(gBefore);
bool isAfterTaken = isLetterTaken(gAfter);
if (isBeforeTaken && !isAfterTaken) {
} else if (isAfterTaken && !isBeforeTaken) {
} else if (isAfterTaken && isBeforeTaken) {
removeInconsistent();
} else { // !isAfterTaken && !isBeforeTaken
}
// TRACE(2);
displayVec(gPossibilities);
}
TRACE(numCases);
//displayVec(gPossibilities);
vector<char> encrypted;
getInputLine(encrypted);
bool isDifferent = false;
for (int i = 1; i < gPossibilities.size(); ++i) {
for (int j = 0; j < gPossibilities[0].size(); ++j) {
if (gPossibilities[0][j] != gPossibilities[i][j]) {
isDifferent = true;
break;
}
}
}
if (gPossibilities[0].size() > input[0]) {
segVilolation();
}
if (!isDifferent && gPossibilities.size() > 0 && gPossibilities[0].size() == input[0] || input[0] < 2) {
for (int i = 0; i < encrypted.size(); ++i) {
bool found = false;
for (int j = 0; j < gPossibilities[0].size(); ++j) {
if (toupper(gPossibilities[0][j]) == toupper(encrypted[i])) {
if (isupper(encrypted[i])) {
cout << ((char) toupper('a' + j));
} else {
cout << ((char) ('a' + j));
}
found = true;
}
}
if (!found) {
cout << encrypted[i];
}
}
cout << endl;
} else {
cout << "Message cannot be decrypted." << endl;
}
}

TRACE("end of run");
return 0;
}

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
Sometimes it is possible to decrypt the message even if not all the substitutions are known.

turingcomplete
New poster
Posts: 11
Joined: Wed Oct 09, 2002 7:31 pm
Contact:

thanks that was it

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

715 - Substitution cipher

Hello,

I wonder why judges did not include input like this:

1
26 50
a
z
zb
zz
zzc
zzz
zzzd
zzzz
zzzze
zzzzz
zzzzzf
zzzzzz
zzzzzzg
zzzzzzz
zzzzzzzh
zzzzzzzz
zzzzzzzzi
zzzzzzzzz
zzzzzzzzzj
zzzzzzzzzz
zzzzzzzzzzk
zzzzzzzzzzz
zzzzzzzzzzzl
zzzzzzzzzzzz
zzzzzzzzzzzzm
zzzzzzzzzzzzz
zzzzzzzzzzzzzn
zzzzzzzzzzzzzz
zzzzzzzzzzzzzzo
zzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzp
zzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzq
zzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzr
zzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzs
zzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzt
zzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzu
zzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzv
zzzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzzw
zzzzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzzzx
zzzzzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzzzzy
zzzzzzzzzzzzzzzzzzzzzzzzz
z

Which says, that every letter is smaller than 'z', but we do not explicitly know anything about relation between other letters.

My backtrack would definitely TLE on this input, but it got accepted in 0.002s

Marian

jholman
New poster
Posts: 1
Joined: Sun Mar 14, 2004 7:57 am
That's a lot more input than you need to demonstrate that. May I suggest(using a smaller alphabet):

1
5 5
a
eb
eec
eeed
eeee
e

As in your example, the correct answer is to echo the ciphertext, not to say "Undecipherable".

Are you sure this isn't in the test data? I don't know about your backtrack, but my algorithm checks for this type of "incomplete-but-adequate knowledge" in cubic time.

Anyway, checked for that, made sure it works. Still getting WA. Not pleased. Thoughts?

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
From the problem statement:
The plain message can contain any symbol, but only the letters of the substitution alphabet are encrypted.
In particular the message can contain spaces. The encrypted words however don't.
I'm always willing to help, if you do the same.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I think the input data is quite weak, otherwise backtracking should definitely TLE. There is a way of doing it using the dependency matrix.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

Re: 715 - Substitution Cipher

I don't know why I am getting wrong answer. I used dependency matrix and the running time is O(n^3). Can anyone verify the cases?

Input:

Code: Select all

``````13
4 6
a
bc
bd
bdbbc
bdbbb
d
bd
4 6
a
bc
bd
bdbbc
bdbbb
d
b       d
4 7
a
bc
bd
bdbbc
bdbba
bdbbb
d
abcd
4 4
a
bc
bd
d
abc
4 4
a
bc
bd
d
d
4 4
a
bc
bd
c
abc
5 5
a
eb
eec
eeed
eeee
e
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
5 6
cebdbac
cac
ecd
dca
aba
bac
cedab
4 4
cca
aac
bca
bdac
3 3
a
c
b
abc
26 50
a
z
zb
zz
zzc
zzz
zzzd
zzzz
zzzze
zzzzz
zzzzzf
zzzzzz
zzzzzzg
zzzzzzz
zzzzzzzh
zzzzzzzz
zzzzzzzzi
zzzzzzzzz
zzzzzzzzzj
zzzzzzzzzz
zzzzzzzzzzk
zzzzzzzzzzz
zzzzzzzzzzzl
zzzzzzzzzzzz
zzzzzzzzzzzzm
zzzzzzzzzzzzz
zzzzzzzzzzzzzn
zzzzzzzzzzzzzz
zzzzzzzzzzzzzzo
zzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzp
zzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzq
zzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzr
zzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzs
zzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzt
zzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzu
zzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzv
zzzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzzw
zzzzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzzzx
zzzzzzzzzzzzzzzzzzzzzzzz
zzzzzzzzzzzzzzzzzzzzzzzzy
zzzzzzzzzzzzzzzzzzzzzzzzz
z
10 83
dffaheebbbbccce
dffafijhgghbce
dffafijb
dffafihhbei
dba
behdgijigigcfb
behdgijii
befciigceiae
beffhfcch
bebhfgeb
bebhfgb
bjafggbbhicidc
bjafggbbi
bjfcd
icbdeccijdfcif
icbdeccijdfddf
icbdebcbecb
ibfjbf
ibba
iidhg
iidhge
iidhh
iidhhbi
iif
iifj
iifjd
iifgeg
iifgegf
iibdafgdihef
iibdafgh
iibdafghf
iibdafb
iibdafbb
iibdab
iibdabbggh
iibdabbgfaf
iibdabicgjfjiic
iibdabicgjfgeaj
iibdc
iibdch
iibjhcibbibejhf
iii
iiiiejhceafjdg
iiiiejhceafjdb
iiiiejhceafjdbe
iiiiejhci
iiiiejhcif
iiiiejhcifjab
iiiibfiaea
iiiibfiaeai
iiiii
iiiiid
iiiiidg
iiiiidgifbf
iiiiidgifbbe
iiiiidfjbbfecab
iiiiidfjbbfecab
iiiiidfjbbfecab
iiiiidfjbbfecab
iiiiidfjbbfecai
iiiiidfjbbfi
iiiiidfjbbfijdh
iiiiidbffacfcba
iiiiidbffacfcba
iiiiidbffacfcba
iiiiidbffaj
iiiiidbffab
iiiiidi
iiiiidij
iiiiidijh
iiiiidijhdfccbg
iiiiidijhdfcci
iiiiie
iiiiieh
iiiiiehgaicgbgh
iiiiief
iiiiiijghcc
iiiiiijghcch
iiiiiijghccha
``````
Output:

Code: Select all

``````cd
c       d
Message cannot be decrypted.
d
abc
e
abcde
abcde
Message cannot be decrypted.
acb
z
jjjjjjefgbbga``````
Edit : Got accepted. The above cases are correct.
Ami ekhono shopno dekhi...
HomePage

HARIS
New poster
Posts: 1
Joined: Sat Jun 18, 2011 9:05 am

Re: 715 - Substitution Cipher

i don't know why teachers put students in trouble by assigning these kind of problems as "final project", this literally means they wanna fail you......