algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

submission-wa.cpp (2714B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <unordered_set>
      4 #include <unordered_map>
      5 #include <algorithm>
      6 #include <queue>
      7 
      8 #define ll long long
      9 
     10 using namespace std;
     11 
     12 // NOTE: This got a contest WA on held out set. I think this is just excessively complex.
     13 
     14 //- p, q strings
     15 //- p as product of variables written in the numerator of a fraction
     16 //- q as product of variables written in the denominator of a fraction
     17 //- can we mutate this such that the numerator simplified to "six" and denominator is cleared?
     18 //    - return YES / NO
     19 
     20 int main() {
     21 
     22     int testCases, current, pSize, qSize;
     23     string p, q = "";
     24 
     25     cin >> testCases;
     26 
     27     // idea:
     28         // put into hashmap, count numbers, ensure sDelta = 1, iDelta = 1, xDelta = 1, all rest = 0
     29 
     30     for(int z = 0; z < testCases; ++z) {
     31         cin >> pSize;
     32         cin >> qSize;
     33         cin >> p;
     34         cin >> q;
     35         
     36         unordered_map<char,int> pCounts {};
     37 
     38         for(int i = 0; i < pSize; ++i) {
     39             pCounts[p[i]] += 1;
     40         }
     41 
     42         unordered_map<char,int> qCounts {};
     43         bool ctn = false;
     44 
     45         for(int i = 0; i < qSize; ++i) {
     46             if(!pCounts.contains(q[i])) {
     47                 cout << "NO" << endl;
     48                 ctn = true;
     49                 break;
     50             }
     51             qCounts[q[i]] += 1;
     52         }
     53 
     54         if(ctn) {
     55             continue;
     56         }
     57 
     58 
     59         bool fs = false;
     60         bool fi = false;
     61         bool fx = false;
     62         bool bad = false;
     63 
     64         for(auto& ele : pCounts) {
     65 
     66             if(ele.second > qCounts[ele.first]) {
     67                 int delta = ele.second - qCounts[ele.first];
     68 
     69                 if(delta >= 2) {
     70                     bad = true;
     71                     break;
     72                 }
     73 
     74                 if(ele.first == 's') {
     75                     if(fs) {
     76                         bad = true;
     77                         break;
     78                     }
     79                     fs = true;
     80                 }
     81                 else if(ele.first == 'i') {
     82                     if(fi) {
     83                         bad = true;
     84                         break;
     85                     }
     86                     fi = true;
     87                 }
     88                 else if(ele.first == 'x') {
     89                     if(fx) {
     90                         bad = true;
     91                         break;
     92                     }
     93                     fx = true;
     94                 } 
     95                 else {
     96                     bad = true;
     97                     break;
     98                 }
     99             }
    100         }
    101         if(fs && fi && fx) {
    102             if(!bad) {
    103                 cout << "YES" << endl;
    104             } else {
    105                 cout << "NO" << endl;
    106             }
    107         } else {
    108             cout << "NO" << endl;
    109         }
    110     }
    111 
    112 }